Печать всех решений в N-QUEEN проблема
#алгоритмN Queen — это проблема размещения N шахматных ферзей на N × N шахматной доске, чтобы две королевы не атаковали друг друга. Например, следующее является решением проблемы 4 Queen.
N Queen — это проблема размещения N шахматных ферзей на N × N шахматной доске, чтобы две королевы не атаковали друг друга. Например, ниже приведены два решения проблемы 4 Queen.
Задача состоит в том, чтобы напечатать все решения в N-Queen Problem.
Алгоритм возврата
Идея состоит в том, чтобы размещать ферзей одну за другой в разных столбцах, начиная с самого левого столбца. Когда мы помещаем ферзя в столбец, мы проверяем наличие конфликтов с уже размещенными ферзями. В текущем столбце, если мы находим строку, для которой нет конфликта, мы помечаем эту строку и столбец как часть решения. Если мы не найдем такой строки из-за столкновений, мы возвращаемся и возвращаем 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 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.
В приведенном выше алгоритме есть только небольшая модификация, которая выделена в коде.
C ++
/ * C / C ++ программа для решения проблемы N Queen с помощью
возвращение назад * /
#include<bits/stdc++.h>
#define N 4
/ * Утилита для печати решения * /
void printSolution(int board[N][N])
{
static int k = 1;
printf("%d-\n",k++);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
printf(" %d ", board[i][j]);
printf("\n");
}
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)
{
printSolution(board);
return true;
}
/ * Рассмотрим этот столбец и попробуйте разместить
эта королева во всех рядах по одному * /
bool res = false;
for (int i = 0; i < N; i++)
{
/ * Проверьте, может ли королева быть помещена на
доска [я] [цв] * /
if ( isSafe(board, i, col) )
{
/ * Поместите эту королеву в доску [i] [col] * /
board[i][col] = 1;
// Сделать результат истинным, если есть место размещения
// возможно
res = solveNQUtil(board, col + 1) || res;
/ * При размещении ферзя на доске [i] [col]
не приводит к решению, то
удалить королеву с доски [i] [col] * /
board[i][col] = 0; // ОБРАТНАЯ СВЯЗЬ
}
}
/ * Если королева не может быть в любой строке
этот столбец col затем возвращает false * /
return res;
}
/ * Эта функция решает проблему N Queen, используя
Откат. В основном он использует функцию executeNQUtil () для
решать проблему. Возвращает ложь, если королевы
не может быть размещен, иначе верните true и
печатает размещение королев в виде 1с.
Обратите внимание, что может быть более одного
решения, эта функция печатает один из
Возможные решения. * /
void solveNQ()
{
int board[N][N];
memset(board, 0, sizeof(board));
if (solveNQUtil(board, 0) == false)
{
printf("Solution does not exist");
return ;
}
return ;
}
// программа драйвера для проверки вышеуказанной функции
int main()
{
solveNQ();
return 0;
}
Джава
/ * Java-программа для решения N Queen
Проблема с возвратом * /
class GfG
{
static int N = 4;
static int k = 1;
/ * Утилита для печати решения * /
static void printSolution(int board[][])
{
System.out.printf("%d-\n", k++);
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");
}
System.out.printf("\n");
}
/ * Утилита для проверки, может ли ферзь
быть помещенным на борту [ряд] [столб]. Обратите внимание, что это
функция вызывается, когда королевы "col"
уже размещены в столбцах от 0 до цв -1.
Поэтому нам нужно проверить только левую сторону для
атакующие королевы * /
static 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 Queen * /
static boolean solveNQUtil(int board[][], int col)
{
/ * базовый случай: если все королевы помещены
затем верните true * /
if (col == N)
{
printSolution(board);
return true;
}
/ * Рассмотрим этот столбец и попробуйте разместить
эта королева во всех рядах по одному * /
boolean res = false;
for (int i = 0; i < N; i++)
{
/ * Проверьте, может ли королева быть помещена на
доска [я] [цв] * /
if ( isSafe(board, i, col) )
{
/ * Поместите эту королеву в доску [i] [col] * /
board[i][col] = 1;
// Сделать результат истинным, если есть место размещения
// возможно
res = solveNQUtil(board, col + 1) || res;
/ * При размещении ферзя на доске [i] [col]
не приводит к решению, то
удалить королеву с доски [i] [col] * /
board[i][col] = 0; // ОБРАТНАЯ СВЯЗЬ
}
}
/ * Если королева не может быть в любой строке
этот столбец col затем возвращает false * /
return res;
}
/ * Эта функция решает проблему N Queen, используя
Откат. В основном он использует функцию executeNQUtil () для
решать проблему. Возвращает ложь, если королевы
не может быть размещен, иначе верните true и
печатает размещение королев в виде 1с.
Обратите внимание, что может быть более одного
решения, эта функция печатает один из
Возможные решения. * /
static void solveNQ()
{
int board[][] = new int[N][N];
if (solveNQUtil(board, 0) == false)
{
System.out.printf("Solution does not exist");
return ;
}
return ;
}
// Код драйвера
public static void main(String[] args)
{
solveNQ();
}
}
// Этот код был добавлен
// от 29AjayKumar
python3
'' 'Программа Python3 для решения проблемы N Queen с помощью
возвращение назад '' '
k = 1
# Утилита для печати решения
def printSolution(board):
global k
print(k, "-\n")
k = k + 1
for i in range(4):
for j in range(4):
print(board[i][j], end = " ")
print("\n")
print("\n")
'' 'Полезная функция, чтобы проверить, может ли королева
быть помещенным на борту [ряд] [столб]. Обратите внимание, что это
функция вызывается, когда королевы "col"
уже размещены в столбцах от 0 до цв -1.
Поэтому нам нужно проверить только левую сторону для
атакующие королевы
def isSafe(board, row, col) :
# Проверьте этот ряд на левой стороне
for i in range(col):
if (board[row][i]):
return False
# Проверьте верхнюю диагональ с левой стороны
i = row
j = col
while i >= 0 and j >= 0:
if(board[i][j]):
return False;
i -= 1
j -= 1
# Проверьте нижнюю диагональ с левой стороны
i = row
j = col
while j >= 0 and i < 4:
if(board[i][j]):
return False
i = i + 1
j = j - 1
return True
'' 'Рекурсивная функция полезности для решения N
Королева проблема
def solveNQUtil(board, col) :
'' 'базовый случай: если все королевы размещены
затем верните true '' '
if (col == 4):
printSolution(board)
return True
'' 'Рассмотрите этот столбец и попробуйте разместить
эта королева во всех рядах один за другим '' '
res = False
for i in range(4):
'' 'Проверьте, может ли королева быть помещена на
доска [я] [кол] '' '
if (isSafe(board, i, col)):
# Поместите эту королеву в доску [i] [col]
board[i][col] = 1;
# Сделать результат истинным, если есть место размещения
# возможно
res = solveNQUtil(board, col + 1) or res;
'' 'Если ставить ферзь на доску [i] [col]
не приводит к решению, то
удалить королеву с доски [i] [col] '' '
board[i][col] = 0 # ОБРАТНАЯ СВЯЗЬ
'' 'Если королева не может быть в любой строке
этот столбец col затем возвращает false '' '
return res
'' 'Эта функция решает проблему N Queen, используя
Откат. В основном он использует функцию executeNQUtil () для
решать проблему. Возвращает ложь, если королевы
не может быть размещен, иначе верните true и
печатает размещение королев в виде 1с.
Обратите внимание, что может быть более одного
решения, эта функция печатает один из
Возможные решения.
def solveNQ() :
board = [[0 for j in range(10)]
for i in range(10)]
if (solveNQUtil(board, 0) == False):
print("Solution does not exist")
return
return
Код водителя
solveNQ()
# Этот код предоставлен YatinGupta
C #
/ * C # программа для решения N Queen
Проблема с возвратом * /
using System;
class GfG
{
static int N = 4;
static int k = 1;
/ * Утилита для печати решения * /
static void printSolution(int [,]board)
{
Console.Write("{0}-\n", k++);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
Console.Write(" {0} ", board[i, j]);
Console.Write("\n");
}
Console.Write("\n");
}
/ * Утилита для проверки, может ли ферзь
быть размещены на борту [ряд, столб]. Обратите внимание, что это
функция вызывается, когда королевы "col"
уже размещены в столбцах от 0 до цв -1.
Поэтому нам нужно проверить только левую сторону для
атакующие королевы * /
static 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 Queen * /
static bool solveNQUtil(int [,]board, int col)
{
/ * базовый случай: если все королевы помещены
затем верните true * /
if (col == N)
{
printSolution(board);
return true;
}
/ * Рассмотрим этот столбец и попробуйте разместить
эта королева во всех рядах по одному * /
bool res = false;
for (int i = 0; i < N; i++)
{
/ * Проверьте, может ли королева быть помещена на
доска [i, col] * /
if ( isSafe(board, i, col) )
{
/ * Поместите эту королеву в доску [i, col] * /
board[i,col] = 1;
// Сделать результат истинным, если есть место размещения
// возможно
res = solveNQUtil(board, col + 1) || res;
/ * При размещении ферзя на доске [i, col]
не приводит к решению, то
удалить королеву с доски [i, col] * /
board[i,col] = 0; // ОБРАТНАЯ СВЯЗЬ
}
}
/ * Если королева не может быть в любой строке
этот столбец col затем возвращает false * /
return res;
}
/ * Эта функция решает проблему N Queen, используя
Откат. В основном он использует функцию executeNQUtil () для
решать проблему. Возвращает ложь, если королевы
не может быть размещен, иначе верните true и
печатает размещение королев в виде 1с.
Обратите внимание, что может быть более одного
решения, эта функция печатает один из
Возможные решения. * /
static void solveNQ()
{
int [,]board = new int[N, N];
if (solveNQUtil(board, 0) == false)
{
Console.Write("Solution does not exist");
return ;
}
return ;
}
// Код драйвера
public static void Main()
{
solveNQ();
}
}
/ * Этот код предоставлен PrinciRaj1992 * /
Выход:
1- 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 2- 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 0