八皇后问题是一个经典的问题，在棋盘上放置八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一对角线上。这个问题在计算机科学中常被用来教授和展示递归算法的原理与应用。在C++中，我们可以利用递归策略来解决这个问题。
我们需要一个二维数组来表示棋盘。每个元素代表棋盘上的一个位置，值为0表示该位置为空，值为1表示有皇后。棋盘大小通常设定为8x8，但此问题可扩展到任意大小的棋盘。
接下来，我们定义一个递归函数，用于尝试在当前位置放置皇后。该函数接收两个参数：当前行的索引和棋盘状态。在每一层递归中，我们尝试将皇后放在当前行的每一个列，检查是否符合规则。如果符合，就递归地处理下一行；如果不符合，回溯到上一列，尝试其他位置。
以下是用C++实现八皇后问题的基本步骤：
1. 初始化棋盘：创建一个8x8的二维数组，所有元素初始化为0。
2. 定义递归函数：函数接受行号作为参数。在函数内部，遍历当前行的所有列，尝试放置皇后。
3. 检查放置：对于当前行的每个列，检查在该位置放置皇后是否与已放置的皇后冲突。这包括检查同一行、同一列以及两个对角线是否有皇后。如果有冲突，则返回false。
4. 回溯：如果没有冲突，递归处理下一行。如果到达最后一行，说明找到了一种解决方案，记录并返回true。
5. 主函数调用：从第一行开始，调用递归函数。如果找到解决方案，输出并返回；如果没有找到，说明无解。
以下是一个简单的C++代码实现：
```cpp
#include <iostream>
using namespace std;
void printBoard(int board[8][8]) {
for (int i = 0; i < 8; ++i) {
for (int j = 0; j < 8; ++j)
cout << (board[i][j] ? "Q " : ". ");
cout << endl;
}
}
bool isSafe(int board[8][8], 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; i >= 0 && j < 8; --i, ++j)
if (board[i][j])
return false;
return true;
}
bool solveNQueens(int board[8][8], int col) {
if (col >= 8)
return true;
bool foundSolution = false;
for (int i = 0; i < 8 && !foundSolution; ++i) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
foundSolution = solveNQueens(board, col + 1);
if (!foundSolution)
board[i][col] = 0; // 回溯
}
}
return foundSolution;
}
int main() {
int board[8][8];
memset(board, 0, sizeof(board));
if (solveNQueens(board, 0)) {
cout << "解决方案之一：" << endl;
printBoard(board);
} else {
cout << "无解" << endl;
}
return 0;
}
```
这个程序首先定义了一个`isSafe`函数来检查在给定位置放置皇后是否安全，然后在`solveNQueens`函数中使用递归尝试所有可能的放置方式。如果找到解决方案，程序会输出棋盘布局；如果没有找到，表示无解。
通过递归，八皇后问题可以高效地找到所有可能的解决方案，体现了递归在解决复杂问题时的强大能力。同时，这个算法也展示了回溯法在处理约束满足问题中的应用，当一条路径无法达到目标时，会返回上一步寻找其他可能的路径。在实际编程中，这种解决问题的方式常用于解决各种组合优化问题。
八皇后递归.rar （1个子文件） 
八皇后递归.cpp 2KB
