N 皇后问题
什么是 N 皇后问题？
在N 皇后问题中，我们给定一个 NxN 的棋盘，我们需要在棋盘上摆放 N 个皇后，并且保证两个皇后之间不会互相攻击。如果一个皇后以水平、垂直或对角线的方式摆放，它会攻击另一个皇后。解决 N 皇后难题最流行的方法是回溯法。
输入输出场景
假设给定的棋盘尺寸为 4x4，我们需要在其中摆放 4 个皇后。解决方案排列如下图所示：−
最终解决方案矩阵为 −
0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0
回溯法求解 N 皇后问题
在求解 N 皇后问题的朴素方法中，算法会生成所有可能的解。然后，它会逐一探索所有解。如果生成的解满足问题的约束条件，则会打印该解。
按照以下步骤使用回溯法 − 解决 n 皇后问题。
将第一个皇后放置在棋盘左上角的格子中。
将皇后放置在第一个格子中后，将该位置标记为解的一部分，然后递归检查这是否会导致解。
现在，如果放置皇后没有得到解，则返回第一步，将皇后放置在其他格子中。重复此操作，直到尝试所有单元格。
如果放置皇后后返回结果，则返回 TRUE。
如果所有皇后都已放置，则返回 TRUE。
如果尝试了所有行但未找到结果，则返回 FALSE。
示例
以下示例说明了如何使用各种编程语言解决包含 5 个皇后的 n 皇后问题。
#include<stdio.h>
#define BOARD_SIZE 5
void displayChess(int chBoard[BOARD_SIZE][BOARD_SIZE]) {
for (int row = 0; row < BOARD_SIZE; row++) {
for (int col = 0; col < BOARD_SIZE; col++)
printf("%d ", chBoard[row][col]);
printf("
");
}
}
int isQueenPlaceValid(int chBoard[BOARD_SIZE][BOARD_SIZE], int crntRow, int crntCol) {
// 检查皇后是否在左边
for (int i = 0; i < crntCol; i++)
if (chBoard[crntRow][i])
return 0;
for (int i = crntRow, j = crntCol; i >= 0 && j >= 0; i--, j--)
//检查皇后是否位于左上对角线
if (chBoard[i][j])
return 0;
for (int i = crntRow, j = crntCol; j >= 0 && i < BOARD_SIZE; i++, j--)
//检查皇后是否位于左下对角线
if (chBoard[i][j])
return 0;
return 1;
}
int solveProblem(int chBoard[BOARD_SIZE][BOARD_SIZE], int crntCol) {
//当 N 个皇后被成功摆放时
if (crntCol >= BOARD_SIZE)
return 1;
// 检查女王的放置是否可行
for (int i = 0; i < BOARD_SIZE; i++) {
if (isQueenPlaceValid(chBoard, i, crntCol)) {
//如果验证通过，则将皇后放置在位置 (i, col)
chBoard[i][crntCol] = 1;
//递归地查找其他列
if (solveProblem(chBoard, crntCol + 1))
return 1;
//当没有空位时，移除那个女王
chBoard[i][crntCol] = 0;
}
}
return 0;
}
int displaySolution() {
int chBoard[BOARD_SIZE][BOARD_SIZE];
for(int i = 0; i < BOARD_SIZE; i++)
for(int j = 0; j < BOARD_SIZE; j++)
//将所有元素设置为 0
chBoard[i][j] = 0;
//从第 0 列开始
if (solveProblem(chBoard, 0) == 0) {
printf("Solution does not exist");
return 0;
}
displayChess(chBoard);
return 1;
}
int main() {
displaySolution();
return 0;
}
#include<iostream>
using namespace std;
#define BOARD_SIZE 5
void displayChess(int chBoard[BOARD_SIZE][BOARD_SIZE]) {
for (int row = 0; row < BOARD_SIZE; row++) {
for (int col = 0; col < BOARD_SIZE; col++)
cout << chBoard[row][col] << " ";
cout << endl;
}
}
bool isQueenPlaceValid(int chBoard[BOARD_SIZE][BOARD_SIZE], int crntRow, int crntCol) {
// 检查皇后是否在左边
for (int i = 0; i < crntCol; i++)
if (chBoard[crntRow][i])
return false;
for (int i = crntRow, j = crntCol; i >= 0 && j >= 0; i--, j--)
//检查皇后是否位于左上对角线
if (chBoard[i][j])
return false;
for (int i = crntRow, j = crntCol; j >= 0 && i < BOARD_SIZE; i++, j--)
//检查皇后是否位于左下对角线
if (chBoard[i][j])
return false;
return true;
}
bool solveProblem(int chBoard[BOARD_SIZE][BOARD_SIZE], int crntCol) {
//当 N 个皇后被成功摆放时
if (crntCol >= BOARD_SIZE)
return true;
// 检查女王的放置是否可行
for (int i = 0; i < BOARD_SIZE; i++) {
if (isQueenPlaceValid(chBoard, i, crntCol)) {
//如果验证通过，则将皇后放置在位置 (i, col)
chBoard[i][crntCol] = 1;
//递归地查找其他列
if (solveProblem(chBoard, crntCol + 1))
return true;
//当没有空位时，移除那个女王
chBoard[i][crntCol] = 0;
}
}
return false;
}
bool displaySolution() {
int chBoard[BOARD_SIZE][BOARD_SIZE];
for(int i = 0; i < BOARD_SIZE; i++)
for(int j = 0; j < BOARD_SIZE; j++)
//将所有元素设置为 0
chBoard[i][j] = 0;
//从第 0 列开始
if (solveProblem(chBoard, 0) == false) {
cout << "Solution does not exist";
return false;
}
displayChess(chBoard);
return true;
}
int main() {
displaySolution();
}
public class Main {
static final int BOARD_SIZE = 5;
static void displayChess(int chBoard[][]) {
for (int row = 0; row < BOARD_SIZE; row++) {
for (int col = 0; col < BOARD_SIZE; col++)
System.out.print(chBoard[row][col] + " ");
System.out.println();
}
}
static boolean isQueenPlaceValid(int chBoard[][], int crntRow, int crntCol) {
// 检查皇后是否在左边
for (int i = 0; i < crntCol; i++)
if (chBoard[crntRow][i] == 1)
return false;
for (int i = crntRow, j = crntCol; i >= 0 && j >= 0; i--, j--)
//检查皇后是否位于左上对角线
if (chBoard[i][j] == 1)
return false;
for (int i = crntRow, j = crntCol; j >= 0 && i < BOARD_SIZE; i++, j--)
//检查皇后是否位于左下对角线
if (chBoard[i][j] == 1)
return false;
return true;
}
static boolean solveProblem(int chBoard[][], int crntCol) {
//当 N 个皇后被成功摆放时
if (crntCol >= BOARD_SIZE)
return true;
// 检查女王的放置是否可行
for (int i = 0; i < BOARD_SIZE; i++) {
if (isQueenPlaceValid(chBoard, i, crntCol)) {
//如果验证通过，则将皇后放置在位置 (i, col)
chBoard[i][crntCol] = 1;
//递归地查找其他列
if (solveProblem(chBoard, crntCol + 1))
return true;
//当没有空位时，移除那个女王
chBoard[i][crntCol] = 0;
}
}
return false;
}
static boolean displaySolution() {
int chBoard[][] = new int[BOARD_SIZE][BOARD_SIZE];
for(int i = 0; i < BOARD_SIZE; i++)
for(int j = 0; j < BOARD_SIZE; j++)
//将所有元素设置为 0
chBoard[i][j] = 0;
//从第 0 列开始
if (!solveProblem(chBoard, 0)) {
System.out.println("Solution does not exist");
return false;
}
displayChess(chBoard);
return true;
}
public static void main(String[] args) {
displaySolution();
}
}
BOARD_SIZE = 5
def displayChess(chBoard):
for row in range(BOARD_SIZE):
for col in range(BOARD_SIZE):
print(chBoard[row][col], end=" ")
print()
def isQueenPlaceValid(chBoard, crntRow, crntCol):
# 检查皇后是否在左边
for i in range(crntCol):
if chBoard[crntRow][i]:
return False
for i, j in zip(range(crntRow, -1, -1), range(crntCol, -1, -1)):
#检查皇后是否位于左上对角线
if chBoard[i][j]:
return False
for i, j in zip(range(crntRow, BOARD_SIZE), range(crntCol, -1, -1)):
#检查皇后是否位于左下对角线
if chBoard[i][j]:
return False
return True
def solveProblem(chBoard, crntCol):
#当 N 个皇后被成功摆放时
if crntCol >= BOARD_SIZE:
return True
# 检查女王的放置是否可行
for i in range(BOARD_SIZE):
if isQueenPlaceValid(chBoard, i, crntCol):
#如果验证通过，则将皇后放置在位置 (i, col)
chBoard[i][crntCol] = 1
#递归地查找其他列
if solveProblem(chBoard, crntCol + 1):
return True
#当没有空位时，移除那个女王
chBoard[i][crntCol] = 0
return False
def displaySolution():
chBoard = [[0 for _ in range(BOARD_SIZE)] for _ in range(BOARD_SIZE)]
#从第 0 列开始
if not solveProblem(chBoard, 0):
print("Solution does not exist")
return False
displayChess(chBoard)
return True
if __name__ == "__main__":
displaySolution()
输出
1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0
