Рубрики

N Queen Проблема | Откат-3

Мы обсудили экскурсию Найта и Крысу в задачах Лабиринта в Сете 1 и Сете 2 соответственно. Давайте обсудим N Queen как еще одну примерную проблему, которая может быть решена с помощью Backtracking.

N Queen — это проблема размещения N шахматных ферзей на N × N шахматной доске, чтобы две королевы не атаковали друг друга. Например, следующее является решением проблемы 4 Queen.

Ожидаемый результат — это двоичная матрица, которая имеет 1 для блоков, в которые помещены ферзи. Например, ниже приведена выходная матрица для решения с 4 ферзями.

              { 0,  1,  0,  0}
              { 0,  0,  0,  1}
              { 1,  0,  0,  0}
              { 0,  0,  1,  0}

Наивный Алгоритм
Создайте все возможные конфигурации королев на борту и распечатайте конфигурацию, которая удовлетворяет заданным ограничениям.

while there are untried configurations
{
   generate the next configuration
   if queens don't attack in this configuration then
   {
      print this configuration;
   }
}

Алгоритм возврата
Идея состоит в том, чтобы размещать ферзей одну за другой в разных столбцах, начиная с самого левого столбца. Когда мы помещаем ферзя в столбец, мы проверяем наличие конфликтов с уже размещенными ферзями. В текущем столбце, если мы находим строку, для которой нет конфликта, мы помечаем эту строку и столбец как часть решения. Если мы не найдем такой строки из-за столкновений, мы возвращаемся и возвращаем false.

1) Start in the leftmost column
2) If all queens are placed
    return true
3) Try all rows in the current column. 
   Do following for every tried row.
    a) If the queen can be placed safely in this row 
       then mark this [row, column] as part of the 
       solution and recursively check if placing
       queen here leads to a solution.
    b) If placing the queen in [row, column] leads to
       a solution then return true.
    c) If placing queen doesn't lead to a solution then
       unmark this [row, column] (Backtrack) and go to 
       step (a) to try other rows.
3) If all rows have been tried and nothing worked,
   return false to trigger backtracking.

Внедрение решения Backtracking

C / C ++

/ * C / C ++ программа для решения проблемы N Queen с помощью

   возвращение назад * /

#define N 4
#include <stdbool.h>
#include <stdio.h>

  
/ * Утилита для печати решения * /

void printSolution(int board[N][N])

{

    for (int i = 0; i < N; i++) {

        for (int j = 0; j < N; j++)

            printf(" %d ", board[i][j]);

        printf("\n");

    }

}

  
/ * Утилита для проверки, может ли ферзь

   быть помещенным на борту [ряд] [столб]. Обратите внимание, что это

   функция вызывается, когда королевы "col"

   уже размещены в столбцах от 0 до цв -1.

   Поэтому нам нужно проверить только левую сторону для

   атакующие королевы * /

bool isSafe(int board[N][N], int row, int col)

{

    int i, j;

  

    / * Проверьте этот ряд на левой стороне * /

    for (i = 0; i < col; i++)

        if (board[row][i])

            return false;

  

    / * Проверить верхнюю диагональ с левой стороны * /

    for (i = row, j = col; i >= 0 && j >= 0; i--, j--)

        if (board[i][j])

            return false;

  

    / * Проверить нижнюю диагональ с левой стороны * /

    for (i = row, j = col; j >= 0 && i < N; i++, j--)

        if (board[i][j])

            return false;

  

    return true;

}

  
/ * Рекурсивная функция полезности для решения N

   Королева проблема * /

bool solveNQUtil(int board[N][N], int col)

{

    / * базовый случай: если все королевы помещены

      затем верните true * /

    if (col >= N)

        return true;

  

    / * Рассмотрим этот столбец и попробуйте разместить

       эта королева во всех рядах по одному * /

    for (int i = 0; i < N; i++) {

        / * Проверьте, можно ли поместить королеву на

          доска [я] [цв] * /

        if (isSafe(board, i, col)) {

            / * Поместите эту королеву в доску [i] [col] * /

            board[i][col] = 1;

  

            / * повторить размещение остальных королев * /

            if (solveNQUtil(board, col + 1))

                return true;

  

            / * При размещении ферзя на доске [i] [col]

               не приводит к решению, то

               удалить королеву с доски [i] [col] * /

            board[i][col] = 0; // ОБРАТНАЯ СВЯЗЬ

        }

    }

  

    / * Если королева не может быть помещена ни в одну строку в

        этот столбец col затем вернуть false * /

    return false;

}

  
/ * Эта функция решает проблему N Queen, используя

   Откат. В основном он использует функцию executeNQUtil () для

   решать проблему. Возвращает ложь, если королевы

   не может быть помещен, в противном случае вернуть true и

   печатает размещение королев в виде 1с.

   Обратите внимание, что может быть более одного

   решения, эта функция печатает один из

   Возможные решения. * /

bool solveNQ()

{

    int board[N][N] = { { 0, 0, 0, 0 },

                        { 0, 0, 0, 0 },

                        { 0, 0, 0, 0 },

                        { 0, 0, 0, 0 } };

  

    if (solveNQUtil(board, 0) == false) {

        printf("Solution does not exist");

        return false;

    }

  

    printSolution(board);

    return true;

}

  
// программа драйвера для проверки вышеуказанной функции

int main()

{

    solveNQ();

    return 0;

}

Джава

/ * Java-программа для решения проблемы N Queen с помощью

   возвращение назад * /

public class NQueenProblem {

    final int N = 4;

  

    / * Утилита для печати решения * /

    void printSolution(int board[][])

    {

        for (int i = 0; i < N; i++) {

            for (int j = 0; j < N; j++)

                System.out.print(" " + board[i][j]

                                 + " ");

            System.out.println();

        }

    }

  

    / * Утилита для проверки, может ли ферзь

       быть помещенным на борту [ряд] [столб]. Обратите внимание, что это

       функция вызывается, когда королевы "col" уже

       размещается в столбцах от 0 до цв -1. Итак, нам нужно

       проверять только левую сторону на атакующие королевы * /

    boolean isSafe(int board[][], int row, int col)

    {

        int i, j;

  

        / * Проверьте этот ряд на левой стороне * /

        for (i = 0; i < col; i++)

            if (board[row][i] == 1)

                return false;

  

        / * Проверить верхнюю диагональ с левой стороны * /

        for (i = row, j = col; i >= 0 && j >= 0; i--, j--)

            if (board[i][j] == 1)

                return false;

  

        / * Проверить нижнюю диагональ с левой стороны * /

        for (i = row, j = col; j >= 0 && i < N; i++, j--)

            if (board[i][j] == 1)

                return false;

  

        return true;

    }

  

    / * Рекурсивная функция полезности для решения N

       Королева проблема * /

    boolean solveNQUtil(int board[][], int col)

    {

        / * базовый случай: если все королевы помещены

           затем верните true * /

        if (col >= N)

            return true;

  

        / * Рассмотрим этот столбец и попробуйте разместить

           эта королева во всех рядах по одному * /

        for (int i = 0; i < N; i++) {

            / * Проверьте, можно ли поместить королеву на

               доска [я] [цв] * /

            if (isSafe(board, i, col)) {

                / * Поместите эту королеву в доску [i] [col] * /

                board[i][col] = 1;

  

                / * повторить размещение остальных королев * /

                if (solveNQUtil(board, col + 1) == true)

                    return true;

  

                / * При размещении ферзя на доске [i] [col]

                   не приводит к решению тогда

                   удалить королеву с доски [i] [col] * /

                board[i][col] = 0; // ОБРАТНАЯ СВЯЗЬ

            }

        }

  

        / * Если королева не может быть помещена ни в одну строку в

           этот столбец col, затем верните false * /

        return false;

    }

  

    / * Эта функция решает проблему N Queen, используя

       Откат. В основном он использует функцию executeNQUtil () для

       решать проблему. Возвращает ложь, если королевы

       не может быть помещен, в противном случае вернуть true и

       печатает размещение королев в виде 1с.

       Обратите внимание, что может быть более одного

       решения, эта функция печатает один из

       Возможные решения. * /

    boolean solveNQ()

    {

        int board[][] = { { 0, 0, 0, 0 },

                          { 0, 0, 0, 0 },

                          { 0, 0, 0, 0 },

                          { 0, 0, 0, 0 } };

  

        if (solveNQUtil(board, 0) == false) {

            System.out.print("Solution does not exist");

            return false;

        }

  

        printSolution(board);

        return true;

    }

  

    // программа драйвера для проверки вышеуказанной функции

    public static void main(String args[])

    {

        NQueenProblem Queen = new NQueenProblem();

        Queen.solveNQ();

    }

}
// Этот код предоставлен Abhishek Shankhadhar

python3

# Python3 программа для решения N Queen
# Проблема с использованием возврата

global N

N = 4

  

def printSolution(board):

    for i in range(N):

        for j in range(N):

            print (board[i][j], end = " ")

        print()

  
# Полезная функция, чтобы проверить, может ли королева
# быть размещенным на доске [row] [col]. Обратите внимание, что это
Функция # вызывается, когда королевы "col"
# уже размещены в столбцах от 0 до цв -1.
# Так что нам нужно проверить только левую сторону для
# атакующие королевы

def isSafe(board, row, col):

  

    # Проверьте этот ряд на левой стороне

    for i in range(col):

        if board[row][i] == 1:

            return False

  

    # Проверьте верхнюю диагональ с левой стороны

    for i, j in zip(range(row, -1, -1), 

                    range(col, -1, -1)):

        if board[i][j] == 1:

            return False

  

    # Проверьте нижнюю диагональ с левой стороны

    for i, j in zip(range(row, N, 1), 

                    range(col, -1, -1)):

        if board[i][j] == 1:

            return False

  

    return True

  

def solveNQUtil(board, col):

      

    # базовый случай: если все королевы размещены

    # затем верните true

    if col >= N:

        return True

  

    # Рассмотрим этот столбец и попробуйте разместить

    # эта королева во всех рядах по одному

    for i in range(N):

  

        if isSafe(board, i, col):

              

            # Поместите эту королеву в доску [i] [col]

            board[i][col] = 1

  

            # повторить размещение остальных королев

            if solveNQUtil(board, col + 1) == True:

                return True

  

            # При размещении ферзя на доске [i] [col

            # не приводит к решению, тогда

            # королева с доски [я] [кол]

            board[i][col] = 0

  

    # если королева не может быть помещена ни в одну строку в

    # этот столбец col затем вернуть false

    return False

  
# Эта функция решает проблему N Queen, используя
Отступление. В основном он использует функцию executeNQUtil () для
# решать проблему. Возвращает ложь, если королевы
# не может быть размещен, иначе верните true и
# размещение королев в виде 1с.
# обратите внимание, что может быть более одного
# решения, эта функция печатает один из
# выполнимые решения.

def solveNQ():

    board = [ [0, 0, 0, 0],

              [0, 0, 0, 0],

              [0, 0, 0, 0],

              [0, 0, 0, 0] ]

  

    if solveNQUtil(board, 0) == False:

        print ("Solution does not exist")

        return False

  

    printSolution(board)

    return True

  
Код водителя
solveNQ()

  
# Этот код предоставлен Divyanshu Mehta

C #

// C # программа для решения проблемы N Queen
// используя возврат

using System;

      

class GFG 

{

    readonly int N = 4;

  

    / * Утилита для печати решения * /

    void printSolution(int [,]board)

    {

        for (int i = 0; i < N; i++) 

        {

            for (int j = 0; j < N; j++)

                Console.Write(" " + board[i, j]

                                  + " ");

            Console.WriteLine();

        }

    }

  

    / * Утилита для проверки, может ли ферзь

    быть размещены на борту [ряд, столб]. Обратите внимание, что это

    функция вызывается, когда королевы "col" уже

    размещается в столбцах от 0 до цв -1. Итак, нам нужно

    проверять только левую сторону на атакующие королевы * /

    bool isSafe(int [,]board, int row, int col)

    {

        int i, j;

  

        / * Проверьте этот ряд на левой стороне * /

        for (i = 0; i < col; i++)

            if (board[row,i] == 1)

                return false;

  

        / * Проверить верхнюю диагональ с левой стороны * /

        for (i = row, j = col; i >= 0 && 

             j >= 0; i--, j--)

            if (board[i,j] == 1)

                return false;

  

        / * Проверить нижнюю диагональ с левой стороны * /

        for (i = row, j = col; j >= 0 && 

                      i < N; i++, j--)

            if (board[i, j] == 1)

                return false;

  

        return true;

    }

  

    / * Рекурсивная функция полезности для решения N

    Королева проблема * /

    bool solveNQUtil(int [,]board, int col)

    {

        / * базовый случай: если все королевы помещены

        затем верните true * /

        if (col >= N)

            return true;

  

        / * Рассмотрим этот столбец и попробуйте разместить

        эта королева во всех рядах по одному * /

        for (int i = 0; i < N; i++) 

        {

            / * Проверьте, можно ли поместить королеву на

            доска [i, col] * /

            if (isSafe(board, i, col))

            {

                / * Поместите эту королеву в доску [i, col] * /

                board[i, col] = 1;

  

                / * повторить размещение остальных королев * /

                if (solveNQUtil(board, col + 1) == true)

                    return true;

  

                / * При размещении ферзя на доске [i, col]

                не приводит к решению тогда

                удалить королеву с доски [i, col] * /

                board[i, col] = 0; // ОБРАТНАЯ СВЯЗЬ

            }

        }

  

        / * Если королева не может быть помещена ни в одну строку в

        этот столбец col, затем верните false * /

        return false;

    }

  

    / * Эта функция решает проблему N Queen, используя

    Откат. В основном он использует функцию executeNQUtil () для

    решать проблему. Возвращает ложь, если королевы

    не может быть помещен, в противном случае вернуть true и

    печатает размещение королев в виде 1с.

    Обратите внимание, что может быть более одного

    решения, эта функция печатает один из

    Возможные решения. * /

    bool solveNQ()

    {

        int [,]board = {{ 0, 0, 0, 0 },

                        { 0, 0, 0, 0 },

                        { 0, 0, 0, 0 },

                        { 0, 0, 0, 0 }};

  

        if (solveNQUtil(board, 0) == false)

        {

            Console.Write("Solution does not exist");

            return false;

        }

  

        printSolution(board);

        return true;

    }

  

    // Код драйвера

    public static void Main(String []args)

    {

        GFG Queen = new GFG();

        Queen.solveNQ();

    }

}

  
// Этот код предоставлен Принчи Сингхом


Вывод: 1 значения указывают на размещение королев

 0  0  1  0 
 1  0  0  0 
 0  0  0  1 
 0  1  0  0 

Оптимизация в функции is_safe ()
Идея не в том, чтобы проверять каждый элемент в правой и левой диагонали, вместо этого использовать свойство диагоналей:
1. Сумма i и j является постоянной и уникальной для каждой правой диагонали, где i — строка элемента, а j —
столбец элемента.
2. Разница между i и j постоянна и уникальна для каждой левой диагонали, где i и j — строка и столбец элемента соответственно.

Внедрение решения Backtracking (с оптимизацией)

C / C ++

/ * C / C ++ программа для решения проблемы N Queen с помощью

   возвращение назад * /

#define N 4
#include <stdbool.h>
#include <stdio.h>
/ * ld - массив, индексы которого указывают на строку-столбец + N-1

 (N-1) для сдвига разницы, чтобы сохранить отрицательный

 индексы * /

int ld[30] = { 0 };

/ * rd - массив, индексы которого указывают на строку + столбец

   и используется для проверки возможности размещения королевы на

   правая диагональ или нет * /

int rd[30] = { 0 };

/ * массив столбцов, где его индексы указывают столбец и

  используется для проверки, может ли королева быть помещена в это

    строка или нет * /

int cl[30] = { 0 };

/ * Утилита для печати решения * /

void printSolution(int board[N][N])

{

    for (int i = 0; i < N; i++) {

        for (int j = 0; j < N; j++)

            printf(" %d ", board[i][j]);

        printf("\n");

    }

}

  
/ * Рекурсивная функция полезности для решения N

   Королева проблема * /

bool solveNQUtil(int board[N][N], int col)

{

    / * базовый случай: если все королевы помещены

      затем верните true * /

    if (col >= N)

        return true;

  

    / * Рассмотрим этот столбец и попробуйте разместить

       эта королева во всех рядах по одному * /

    for (int i = 0; i < N; i++) {

        / * Проверьте, можно ли поместить королеву на

          доска [я] [цв] * /

        / * Проверка возможности размещения королевы

           доска [row] [col]. Нам просто нужно проверить

           ld [row-col + n-1] и rd [row + coln] где

           лд и рд для левого и правого

           диагональ соответственно * /

        if ((ld[i - col + N - 1] != 1 &&

                  rd[i + col] != 1) && cl[i] != 1) {

            / * Поместите эту королеву в доску [i] [col] * /

            board[i][col] = 1;

            ld[i - col + N - 1] =

                          rd[i + col] = cl[i] = 1;

  

            / * повторить размещение остальных королев * /

            if (solveNQUtil(board, col + 1))

                return true;

  

            / * При размещении ферзя на доске [i] [col]

               не приводит к решению, то

               удалить королеву с доски [i] [col] * /

            board[i][col] = 0; // ОБРАТНАЯ СВЯЗЬ

            ld[i - col + N - 1] =

                         rd[i + col] = cl[i] = 0;

        }

    }

  

    / * Если королева не может быть помещена ни в одну строку в

        этот столбец col затем вернуть false * /

    return false;

}
/ * Эта функция решает проблему N Queen, используя

   Откат. В основном он использует функцию executeNQUtil () для

   решать проблему. Возвращает ложь, если королевы

   не может быть помещен, в противном случае вернуть true и

   печатает размещение королев в виде 1с.

   Обратите внимание, что может быть более одного

   решения, эта функция печатает один из

   Возможные решения. * /

bool solveNQ()

{

    int board[N][N] = { { 0, 0, 0, 0 },

                        { 0, 0, 0, 0 },

                        { 0, 0, 0, 0 },

                        { 0, 0, 0, 0 } };

  

    if (solveNQUtil(board, 0) == false) {

        printf("Solution does not exist");

        return false;

    }

  

    printSolution(board);

    return true;

}

  
// программа драйвера для проверки вышеуказанной функции

int main()

{

    solveNQ();

    return 0;

}

Джава

/ * Java-программа для решения проблемы N Queen
используя возврат * /

import java.util.*;

  

class GFG 

{

static int N = 4;

  
/ * ld - массив, индексы которого указывают на строку-столбец + N-1
(N-1) для сдвига разницы, чтобы сохранить отрицательный
индексы * /

static int []ld = new int[30];

  
/ * rd - массив, индексы которого указывают на строку + столбец
и используется для проверки возможности размещения королевы на
правая диагональ или нет * /

static int []rd = new int[30];

  
/ * массив столбцов, где его индексы указывают столбец и
используется для проверки, может ли королева быть помещена в это

    строка или нет * /

static int []cl = new int[30];

  
/ * Утилита для печати решения * /

static void printSolution(int board[][])

{

    for (int i = 0; i < N; i++)

    {

        for (int j = 0; j < N; j++)

            System.out.printf(" %d ", board[i][j]);

        System.out.printf("\n");

    }

}

  
/ * Рекурсивная функция полезности для решения N
Королева проблема * /

static boolean solveNQUtil(int board[][], int col)

{

    / * базовый случай: если все королевы помещены

    затем верните true * /

    if (col >= N)

        return true;

  

    / * Рассмотрим этот столбец и попробуйте разместить

    эта королева во всех рядах по одному * /

    for (int i = 0; i < N; i++)

    {

          

        / * Проверьте, можно ли поместить королеву на

        доска [я] [цв] * /

        / * Проверка возможности размещения королевы

        доска [row] [col]. Нам просто нужно проверить

        ld [row-col + n-1] и rd [row + coln] где

        лд и рд для левого и правого

        диагональ соответственно * /

        if ((ld[i - col + N - 1] != 1 &&

             rd[i + col] != 1) && cl[i] != 1)

        {

            / * Поместите эту королеву в доску [i] [col] * /

            board[i][col] = 1;

            ld[i - col + N - 1] =

            rd[i + col] = cl[i] = 1;

  

            / * повторить размещение остальных королев * /

            if (solveNQUtil(board, col + 1))

                return true;

  

            / * При размещении ферзя на доске [i] [col]

            не приводит к решению, то

            удалить королеву с доски [i] [col] * /

            board[i][col] = 0; // ОБРАТНАЯ СВЯЗЬ

            ld[i - col + N - 1] =

            rd[i + col] = cl[i] = 0;

        }

    }

  

    / * Если королева не может быть помещена ни в одну строку в

        этот столбец col затем вернуть false * /

    return false;

}
/ * Эта функция решает проблему N Queen, используя
Откат. В основном он использует функцию executeNQUtil () для
решать проблему. Возвращает ложь, если королевы
не может быть помещен, в противном случае вернуть true и
печатает размещение королев в виде 1с.
Обратите внимание, что может быть более одного
решения, эта функция печатает один из
Возможные решения. * /

static boolean solveNQ()

{

    int board[][] = {{ 0, 0, 0, 0 },

                     { 0, 0, 0, 0 },

                     { 0, 0, 0, 0 },

                     { 0, 0, 0, 0 }};

  

    if (solveNQUtil(board, 0) == false

    {

        System.out.printf("Solution does not exist");

        return false;

    }

  

    printSolution(board);

    return true;

}

  
// Код драйвера

public static void main(String[] args)

{

    solveNQ();

}
}

  
// Этот код предоставлен Принчи Сингхом

python3

"" "Программа Python3 для решения проблемы N Queen с помощью
возврат "" "

N = 4

  
"" "ld - это массив, где его индексы указывают на строку-столбец + N-1
(N-1) для сдвига разницы, чтобы сохранить отрицательный
индексы "" "

ld = [0] * 30

  
"" "rd - массив, индексы которого указывают на строку + столбец
и используется для проверки возможности размещения королевы на
правильная диагональ или нет "" "

rd = [0] * 30

  
"" "массив столбцов, где его индексы указывают столбец и
используется для проверки, может ли королева быть помещена в это

    строка или нет "" "

cl = [0] * 30

  
"" "Утилита для печати решения" ""

def printSolution(board): 

    for i in range(N):

        for j in range(N):

            print(board[i][j], end = " ")

        print() 

  
"" "Рекурсивная функция полезности для решения N
Королева проблема "" "

def solveNQUtil(board, col): 

      

    "" "базовый случай: если все королевы размещены

        затем верните True "" "

    if (col >= N):

        return True

          

    "" "Рассмотрите этот столбец и попробуйте разместить

        эта королева во всех рядах один за другим "" "

    for i in range(N):

          

        "" "Проверьте, может ли королева быть помещена на борт [i] [col]" ""

        "" "Проверка возможности размещения королевы на доске [row] [col].

        Нам просто нужно проверить ld [row-col + n-1] и rd [row + coln]

        где ld и rd для левой и правой диагонали соответственно "" "

        if ((ld[i - col + N - 1] != 1 and 

             rd[i + col] != 1) and cl[i] != 1):

                   

            "" "Поместите эту королеву в доску [i] [col]" ""

            board[i][col] = 1

            ld[i - col + N - 1] = rd[i + col] = cl[i] = 1

              

            "" "повторить размещение остальных королев" ""

            if (solveNQUtil(board, col + 1)):

                return True

                  

            "" "Если ставить королеву на доску [i] [col]

            не приводит к решению,

            затем удалите королеву с доски [i] [col] "" "

            board[i][col] = 0 # ОБРАТНАЯ СВЯЗЬ

            ld[i - col + N - 1] = rd[i + col] = cl[i] = 0

              

            "" "Если королева не может быть помещена в

            любая строка в этом столбце col затем возвращает False "" "

    return False

      
"" "Эта функция решает проблему N Queen, используя
Откат. В основном он использует функцию executeNQUtil () для
решать проблему. Возвращает False, если королевы
не может быть помещен, иначе верните True и
печатает размещение королев в виде 1с.
Обратите внимание, что может быть более одного
решения, эта функция печатает один из
возможные решения.

def solveNQ():

    board = [[0, 0, 0, 0], 

             [0, 0, 0, 0],

             [0, 0, 0, 0],

             [0, 0, 0, 0]]

    if (solveNQUtil(board, 0) == False):

        printf("Solution does not exist")

        return False

    printSolution(board)

    return True

      
Код водителя
solveNQ() 

  
# Этот код предоставлен SHUBHAMSINGH10

C #

/ * C # программа для решения проблемы N Queen
используя возврат * /

using System;

      

class GFG 

{

static int N = 4;

  
/ * ld - массив, индексы которого указывают на строку-столбец + N-1
(N-1) для сдвига разницы, чтобы сохранить отрицательный
индексы * /

static int []ld = new int[30];

  
/ * rd - массив, индексы которого указывают на строку + столбец
и используется для проверки возможности размещения королевы на
правая диагональ или нет * /

static int []rd = new int[30];

  
/ * массив столбцов, где его индексы указывают столбец и
используется для проверки, может ли королева быть помещена в это

    строка или нет * /

static int []cl = new int[30];

  
/ * Утилита для печати решения * /

static void printSolution(int [,]board)

{

    for (int i = 0; i < N; i++)

    {

        for (int j = 0; j < N; j++)

            Console.Write(" {0} ", board[i, j]);

        Console.Write("\n");

    }

}

  
/ * Рекурсивная функция полезности для решения N
Королева проблема * /

static bool solveNQUtil(int [,]board, int col)

{

    / * базовый случай: если все королевы помещены

    затем верните true * /

    if (col >= N)

        return true;

  

    / * Рассмотрим этот столбец и попробуйте разместить

    эта королева во всех рядах по одному * /

    for (int i = 0; i < N; i++)

    {

          

        / * Проверьте, можно ли поместить королеву на

        доска [i, col] * /

        / * Проверка возможности размещения королевы

        доска [row, col]. Нам просто нужно проверить

        ld [row-col + n-1] и rd [row + coln] где

        лд и рд для левого и правого

        диагональ соответственно * /

        if ((ld[i - col + N - 1] != 1 &&

             rd[i + col] != 1) && cl[i] != 1)

        {

            / * Поместите эту королеву в доску [i, col] * /

            board[i, col] = 1;

            ld[i - col + N - 1] =

            rd[i + col] = cl[i] = 1;

  

            / * повторить размещение остальных королев * /

            if (solveNQUtil(board, col + 1))

                return true;

  

            / * При размещении ферзя на доске [i, col]

            не приводит к решению, то

            удалить королеву с доски [i, col] * /

            board[i, col] = 0; // ОБРАТНАЯ СВЯЗЬ

            ld[i - col + N - 1] =

            rd[i + col] = cl[i] = 0;

        }

    }

  

    / * Если королева не может быть помещена ни в одну строку в

        этот столбец col затем вернуть false * /

    return false;

}

  
/ * Эта функция решает проблему N Queen, используя
Откат. В основном он использует функцию executeNQUtil () для
решать проблему. Возвращает ложь, если королевы
не может быть помещен, в противном случае вернуть true и
печатает размещение королев в виде 1с.
Обратите внимание, что может быть более одного
решения, эта функция печатает один из
Возможные решения. * /

static bool solveNQ()

{

    int [,]board = {{ 0, 0, 0, 0 },

                    { 0, 0, 0, 0 },

                    { 0, 0, 0, 0 },

                    { 0, 0, 0, 0 }};

  

    if (solveNQUtil(board, 0) == false

    {

        Console.Write("Solution does not exist");

        return false;

    }

  

    printSolution(board);

    return true;

}

  
// Код драйвера

public static void Main(String[] args)

{

    solveNQ();

}
}

  
// Этот код предоставлен Rajput-Ji


Вывод: 1 значения указывают на размещение королев

 0  0  1  0 
 1  0  0  0 
 0  0  0  1 
 0  1  0  0 

Печать всех решений в N-Queen Проблема

Источники:
http://see.stanford.edu/materials/icspacs106b/H19-RecBacktrackExamples.pdf
http://en.literateprograms.org/Eight_queens_puzzle_%28C%29
http://en.wikipedia.org/wiki/Eight_queens_puzzle

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

N Queen Проблема | Откат-3

0.00 (0%) 0 votes