c++递归实现棋盘覆盖

在C++中，递归可以用于解决棋盘覆盖的问题，比如著名的八皇后问题，即在一个8x8的国际象棋棋盘上放置八个皇后，使得任意两个皇后之间都没有在同一行、同一列或同一对角线上。以下是使用递归的一种简单思路：

#include <vector>

bool is_safe(int row, int col, std::vector<std::vector<int>>& board) {
    // 检查行冲突
    for (int i = 0; i < col; ++i)
        if (board[row][i] == 1)
            return false;

    // 检查左上方对角线冲突
    int di = row - col;
    while (di >= 0 && board[di][col] == 1)
        di--;

    // 检查右上方对角线冲突
    di = row + col;
    while (di < board.size() && board[di][col] == 1)
        di++;

    return true;
}

void solveNQueens(int n, int row, std::vector<std::vector<int>>& board) {
    if (row == n) {
        // 如果已经放置了所有皇后，打印结果
        for (const auto& line : board)
            for (int cell : line)
                std::cout << cell << " ";
        std::cout << "\n";
        return;
    }

    // 对每个空位置尝试放置皇后，然后递归地处理下一行
    for (int col = 0; col < n; ++col) {
        if (is_safe(row, col, board)) {
            board[row][col] = 1;
            solveNQueens(n, row + 1, board);
            board[row][col] = 0; // 回溯：如果当前放置失败，恢复状态并继续尝试其他位置
        }
    }
}

int main() {
    int n = 8;
    std::vector<std::vector<int>> board(n, std::vector<int>(n, 0));
    solveNQueens(n, 0, board);
    return 0;
}