c++使用回溯法求解n皇后问题

回溯法是一种常用于求解深度优先搜索问题的算法，其中 n 皇后问题就是一种典型的深度优先搜索问题。n 皇后问题是指在一个 n × n 的棋盘上放置 n 个皇后，使得每行、每列和两条对角线上都只有一个皇后。实现该算法的具体过程如下：

1. 定义一个二维数组 chessBoard 存储棋盘状态。初始时所有元素都为 0，表示该位置没有放置皇后；

2. 定义一个函数 canPlaceQueen 判断当前位置能否放置皇后，判断方法为：当前位置所在行、列、以及两条对角线上都没有已放置的皇后；

3. 定义一个递归函数 backtrack，其参数为当前搜索到的行数 row。在函数中遍历当前行的每一列，如果该位置能够放置皇后，则更新棋盘状态，并递归搜索下一行。如果递归到最后一行，则表示找到了一组解，将其保存到结果列表中。递归结束后需要将棋盘状态回溯到之前的状态；

4. 在主函数中调用 backtrack 函数，从第一行开始搜索。

以下是 C++ 实现代码：

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> chessBoard(n, string(n, '.'));  // 初始化棋盘
        backtrack(res, chessBoard, 0);
        return res;
    }

private:
    void backtrack(vector<vector<string>>& res, vector<string>& chessBoard, int row) {
        if (row == chessBoard.size()) {  // 已经找到一组解
            res.push_back(chessBoard);
            return;
        }

        int n = chessBoard[row].size();
        for (int col = 0; col < n; col++) {  // 遍历当前行的每一列
            if (!canPlaceQueen(chessBoard, row, col)) {  // 判断该位置能否放置皇后
                continue;
            }

            chessBoard[row][col] = 'Q';  // 更新棋盘状态
            backtrack(res, chessBoard, row + 1);  // 递归搜索下一行
            chessBoard[row][col] = '.';  // 回溯棋盘状态
        }
    }

    bool canPlaceQueen(vector<string>& chessBoard, int row, int col) {
        int n = chessBoard.size();
        for (int i = 0; i < row; i++) {  // 判断同一列是否有皇后
            if (chessBoard[i][col] == 'Q') {
                return false;
            }
        }

        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {  // 判断左上方是否有皇后
            if (chessBoard[i][j] == 'Q') {
                return false;
            }
        }

        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {  // 判断右上方是否有皇后
            if (chessBoard[i][j] == 'Q') {
                return false;
            }
        }

        return true;
    }
};

int main() {
    Solution s;
    vector<vector<string>> res = s.solveNQueens(4);
    for (auto& board : res) {
        for (auto& row : board) {
            cout << row << endl;
        }
        cout << endl;
    }
    return 0;
}