如何使用C++中的八皇后問題演算法

#include <iostream>
#include <vector>

using namespace std;

const int n = 8;  // 棋盘大小

// 棋盘
int chessboard[n][n];

// 保存解法的容器
vector<vector<int>> solutions;

// 检查当前格子上是否可以放置皇后
bool isValid(int row, int col) {
    // 检查同一列上是否有皇后
    for (int i = 0; i < row; i++) {
        if (chessboard[i][col] == 1)
            return false;
    }
    
    // 检查左上对角线上是否有皇后
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (chessboard[i][j] == 1)
            return false;
    }
    
    // 检查右上对角线上是否有皇后
    for (int i = row, j = col; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 1)
            return false;
    }
    
    return true;
}

// 解决八皇后问题的递归函数
bool solveNQueens(int row) {
    // 如果已经遍历到最后一行，表示找到了一种解法，将当前棋盘状态保存下来
    if (row == n) {
        vector<int> solution;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (chessboard[i][j] == 1)
                    solution.push_back(j);
            }
        }
        solutions.push_back(solution);
        return true;
    }

    // 遍历当前行的每一个格子，尝试放置皇后
    for (int col = 0; col < n; col++) {
        // 如果当前格子满足放置皇后的条件，标记该格子为已占用
        if (isValid(row, col)) {
            chessboard[row][col] = 1;

            // 递归调用函数，遍历下一行
            solveNQueens(row + 1);

            // 如果递归调用的结果返回false，表示当前格子的放置方式不满足解法要求，回溯到上一步
            chessboard[row][col] = 0;
        }
    }

    return false;
}

// 打印解法
void printSolutions() {
    for (auto solution : solutions) {
        cout << "Solution:" << endl;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j == solution[i])
                    cout << "Q ";
                else
                    cout << ". ";
            }
            cout << endl;
        }
        cout << endl;
    }
}

int main() {
    solveNQueens(0);
    printSolutions();
    return 0;
}