八皇后问题c++递归

八皇后问题在C++中通过递归方法可以直观地表示，递归的关键在于将大问题分解成小问题并逐层解决，直到达到基本情况。在这个问题中，基本情况是当我们在第`row`行放置了皇后并且没有冲突时，我们找到了一个有效的解决方案。

下面是一个简单的C++递归函数解决八皇后问题的例子：

#include <vector>
using namespace std;

// 判断当前位置是否安全，即检查该位置是否与其他位置的皇后有冲突
bool isSafe(vector<vector<int>>& board, int row, int col) {
    // 检查同一行和主对角线
    for (int i = 0; i < row; i++) {
        if (board[i][col] || board[row][i] == col)
            return false;
    }
    // 检查副对角线
    int di = row - col;
    for (int i = 0; i < di; i++) {
        if (board[i][n - 1 - i] == col)
            return false;
    }
    return true;
}

// 递归函数
vector<vector<int>> solveNQueens(int n) {
    vector<vector<int>> board(n, vector<int>(n, 0));
    vector<int> soln;
    
    // 从第一行开始，递归地尝试每列
    if (solveNQueensHelper(0, board, soln))
        return soln;  // 返回解

    return {};  // 如果所有可能都尝试过仍无解，则返回空
}

// 实际递归过程
bool solveNQueensHelper(int row, vector<vector<int>>& board, vector<int>& soln) {
    if (row == n)  // 边界条件：如果填满了一行
        return true;

    for (int col = 0; col < n; ++col) {
        if (isSafe(board, row, col)) {
            board[row][col] = 1;  // 放置皇后
            if (solveNQueensHelper(row + 1, board, soln)) {
                soln.push_back(col);  // 添加皇后位置到解中
                return true;
            }
            board[row][col] = 0;  // 未找到解，撤销操作
        }
    }
    return false;  // 无法继续，在这一行上找其他列
}