c++递归求八皇后问题
时间: 2024-09-27 09:01:44 浏览: 24
八皇后问题是经典的回溯算法示例,它要在8x8的棋盘上放置8个皇后,使得任意两个皇后都不在同一行、同一列,以及同一条对角线上。在C++中,递归是一个常用的方法来解决这个问题。以下是递归函数的基本思路:
```cpp
#include <vector>
bool isSafe(int row, int col, std::vector<std::vector<int>>& board) {
// 检查当前列是否已经有皇后
for (int i = 0; i < row; ++i) {
if (board[i][col] == 1) {
return false;
}
}
// 检查左上方对角线是否有皇后
int-diag = row - col;
for (int i = 0; i < diag; ++i) {
if (board[i][i + diag] == 1) {
return false;
}
}
// 检查右上方对角线是否有皇后
int-diag = row + col;
for (int i = 0; i < diag; ++i) {
if (board[i][i + diag] == 1) {
return false;
}
}
return true;
}
std::vector<std::vector<int>> solveNQueens(int n) {
std::vector<std::vector<int>> board(n, std::vector<int>(n, 0));
std::vector<int> solution;
// 递归函数的核心部分
bool foundSolution = backtrack(row, &board, solution);
if (!foundSolution) {
return {}; // 如果找不到解,返回空向量
}
return solution;
}
// 递归搜索函数,row 表示当前行,board 是解决方案存储矩阵,solution 存储已找到的解
bool backtrack(int row, std::vector<std::vector<int>>& board, std::vector<int>& solution) {
if (row == n) { // 当行数等于棋盘大小时,找到一个解
solution.push_back(board[row][0]);
return true;
}
// 对于每一列尝试放置皇后
for (int col = 0; col < n; ++col) {
if (isSafe(row, col, board)) {
board[row][col] = 1; // 尝试放置
if (backtrack(row + 1, board, solution)) {
solution.push_back(col); // 添加皇后位置到解中
return true;
}
board[row][col] = 0; // 回溯,移除皇后
}
}
return false;
}
```