C++ 程序解决 N 皇后问题
c++server side programmingprogramming更新于 2024/11/4 5:31:00
这个问题是在棋盘上找到 N 个皇后的排列，使得任何皇后都不能攻击棋盘上的其他皇后。
国际象棋皇后可以向水平、垂直、水平和对角线等任何方向攻击。
使用二进制矩阵显示 N 个皇后的位置，其中任何皇后都不能攻击其他皇后。这里，我们解决 8 个皇后的问题。
输入
棋盘的大小。这里是 8(8 x 8 是普通棋盘的大小)。
输出
表示 N 个皇后可以放在哪一行和哪一列的矩阵。
如果不存在解决方案，它将返回 false。
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
在此输出中，值 1 表示皇后的正确位置。
0 表示棋盘上的空白处。
算法
isValid(board, row, col)
Begin 如果当前列左侧有一个皇后，则 返回 false 如果左上对角线有一个皇后，则 返回 false 如果左下对角线有一个皇后，则 返回 false; 返回 true //否则它是有效位置 End
solveNQueen(board, col)
Begin 如果所有列都已填满，则 返回 true 对于棋盘的每一行，执行 如果 isValid(board, i, col)，则 将皇后设置在棋盘上的 (i, col) 位置 如果solveNQueen(board, col+1) = true，则 返回 true 否则从棋盘上的 (i, col) 位置移除皇后。 完成 返回 false End
示例
#include<iostream>
using namespace std;
#define N 4
void printBoard(int board[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
cout << board[i][j] << " ";
cout << endl;
}
}
bool isValid(int board[N][N], int row, int col) {
for (int i = 0; i < col; i++) //检查左边是否有皇后
if (board[row][i])
return false;
for (int i=row, j=col; i>=0 && j>=0; i--, j--)
if (board[i][j]) //检查左上对角线是否有皇后
return false;
for (int i=row, j=col; j>=0 && i<N; i++, j--)
if (board[i][j]) //检查左下对角线是否有皇后
return false;
return true;
}
bool resolveNQueen(int board[N][N], int col) {
if (col >= N) //当 N 个皇后成功摆放时
return true;
for (int i = 0; i < N; i++) { //对于每一行，检查是否可以摆放皇后
if (isValid(board, i, col) ) {
board[i][col] = 1; //如果有效，将皇后放置在位置 (i, col)
if (solveNQueen(board, col + 1)) //递归查找其他列
return true;
board[i][col] = 0; //当没有空位时，移除该皇后
}
}
return false; //当没有找到可能的顺序时
}
bool checkSolution() {
int board[N][N];
for(int i = 0; i<N; i++)
for(int j = 0; j<N; j++)
board[i][j] = 0; //将所有元素设置为 0
if (solveNQueen(board, 0) == false) { //从第 0 列开始
cout << "Solution does not exist";
return false;
}
printBoard(board);
return true;
}
int main() {
checkSolution();
}
输出
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
