在Java/C++中使用回溯法解决N皇后问题
如果你喜欢下棋，你会喜欢学习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的例子。
在解决问题之前，你需要了解国际象棋中皇后的移动方式。 (Zài jiějué wèntí zhīqián, nǐ xūyào liǎojiě guójì xiàngqí zhōng huáng hòu de yídòng fāngshì.)
一位皇后可以向任意方向移动任意数量的步骤。唯一的限制是，它在移动过程中不能改变方向。
通过观察皇后的移动可以清楚地看出一件事，即没有两个皇后可以位于同一行或同一列。
这使得我们只能在每一行和每一列上放置一个皇后。
当N等于4时，解决方案如下：
但是我们如何取得这个安排？
N-皇后问题的解决方案
我们解决这个问题的方式是在一个位置上放置一枚皇后，并试图排除其被攻击的可能性。我们在每一行/每一列都放置一个皇后。
如果我们发现女王在已选的位置受到攻击，我们尝试下一个位置。
如果一個皇后被攻擊在一排的所有位置上，我們將回溯並改變先前位置放置的皇后的位置。
我们不断重复放置皇后并进行回溯的过程，直到所有N个皇后都成功地放置完成。
以下是逐步回溯的步骤展示：
红色十字标志着在攻击中的位置，这些位置受到皇后的威胁。每当我们遇到一种情况，所有行中的位置都受到攻击，但我们又有一个要放置的皇后时，我们就会回溯。
这并不是问题的唯一解决方案。如果你按照顺时针的方式将每个皇后向前移动一步，就会得到另一个解决方案。
在这个例子中，我们按照行来摆放皇后，我们也可以按照列进行相同的操作。那样的话，每个皇后将属于一列。
使用C++和Java实现N皇后问题
在C++中实现N皇后问题。
#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;
}
在Java中实现N皇后问题。
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皇后问题的方法。要了解更多关于回溯法的知识，可以尝试解决数独问题。