Проблема N-Queens с использованием поиска с возвратом в Java/C++
Если вы любите играть в шахматы, вам понравится изучение проблемы N-ферзей. Это хорошая проблема, чтобы понять откат.
Что такое откат?
При возврате мы начинаем с одного возможного хода из многих доступных ходов. Затем мы пытаемся решить проблему.
Если мы сможем решить задачу с выбранным ходом, мы распечатаем решение. В противном случае мы отступим, выберем другой ход и попытаемся решить его.
Если ни один из ходов не сработал, мы утверждаем, что решения проблемы нет.
Что такое проблема N-ферзей?
How can N queens be placed on an NxN chessboard so that no two of them attack each other?
Эта проблема обычно наблюдается для N=4 и N=8.
Давайте рассмотрим пример, где N=4
Перед решением задачи нужно узнать о движении ферзя в шахматах.
Ферзь может двигаться на любое количество шагов в любом направлении. Единственным ограничением является то, что он не может изменить свое направление во время движения.
Одна вещь, которая становится ясной при взгляде на движение ферзя, заключается в том, что никакие два ферзя не могут находиться в одном ряду или столбце.
Это позволяет нам размещать только одну ферзя в каждой строке и в каждом столбце.
При N=4 решение выглядит так:
Но как нам добиться такого расположения?
Решение проблемы N ферзей
Мы пытаемся решить эту проблему, помещая ферзя в позицию и пытаясь исключить возможность атаки на нее. Мы помещаем одну королеву в каждую строку/столбец.
Если мы видим, что ферзь находится под атакой в выбранной позиции, мы пробуем следующую позицию.
Если ферзь находится под атакой на всех позициях подряд, мы возвращаемся назад и меняем позицию ферзя, стоящую перед текущей позицией.
Мы повторяем этот процесс размещения ферзя и возврата, пока все N ферзей не будут успешно размещены.
Пошаговый возврат показан следующим образом:
Красным крестом отмечены позиции, находящиеся под атакой ферзя. Всякий раз, когда мы достигаем состояния, когда у нас есть ферзь, но все позиции в рядах находятся под атакой, мы отступаем.
Это не единственное возможное решение проблемы. Если вы переместите каждого ферзя на один шаг вперед по часовой стрелке, вы получите другое решение.
В этом примере мы разместили ферзей по рядам, мы можем сделать то же самое и по столбцам. В этом случае каждый ферзь будет принадлежать столбцу.
Реализация проблемы N-ферзей на C++ и Java
Реализация задачи N-Queens на C++:
#define N 4
#include <stdbool.h>
#include <stdio.h>
//function to print the solution
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");
}
}
// function to check whether the position is safe or not
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;
}
// The function that solves the problem using backtracking
bool solveNQUtil(int board[N][N], int col)
{
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
//if it is safe to place the queen at position i,col -> place it
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQUtil(board, col + 1))
return true;
//backtrack if the above condition is false
board[i][col] = 0; // BACKTRACK
}
}
return false;
}
// driver program to test above function
int main()
{
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 0;
}
printSolution(board);
return true;
return 0;
}
Реализация проблемы N-ферзей в Java:
package com.JournalDev;
public class Main {
static final int N = 4;
// print the final solution matrix
static 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();
}
}
// function to check whether the position is safe or not
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;
}
// The function that solves the problem using backtracking
public static boolean solveNQueen(int board[][], int col)
{
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
//if it is safe to place the queen at position i,col -> place it
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQueen(board, col + 1))
return true;
//backtrack if the above condition is false
board[i][col] = 0;
}
}
return false;
}
public static void main(String args[])
{
int board[][] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };
if (!solveNQueen(board, 0)) {
System.out.print("Solution does not exist");
return;
}
printSolution(board);
}
}
Output :
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
Для N=8 вывод:
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
Понимание реализации кода
Чтобы проверить, атакована позиция или нет, мы создали функцию isSafe.
Функция возвращает true, если позиции защищены от любой атаки.
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;
}
Первый для проверки петель по столбику, второй и третий для проверки петель по двум диагоналям.
Следующий фрагмент кода отвечает за размещение ферзей на их позиции и возврат. Чтобы отметить положение ферзя, мы устанавливаем эту ячейку как 1 в матрице. Перед размещением ферзя мы вызываем isSafe, чтобы убедиться, что позиция безопасна.
public static boolean solveNQueen(int board[][], int col)
{
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
//if it is safe to place the queen at position i,col -> place it
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQueen(board, col + 1))
return true;
//backtrack if the above condition is false
board[i][col] = 0;
}
}
return false;
}
Рекурсивный вызов передает доску и устанавливает столбец в col+1. Если рекурсивный вызов возвращает false, мы возвращаемся назад, сбрасывая запись на 0.
Заключение
Вот как вы решаете проблему N-Queen, используя поиск с возвратом. Чтобы узнать больше об откате, попробуйте решить задачу судоку.