C++编程使用回溯法求N皇后问题

N皇后问题可以使用回溯法求解，下面是一个使用 C++ 编写的 N 皇后问题求解程序：

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> board(n, string(n, '.'));
        backtrack(res, board, 0);
        return res;
    }

private:
    void backtrack(vector<vector<string>>& res, vector<string>& board, int row) {
        int n = board.size();
        if (row == n) {
            res.push_back(board);
            return;
        }
        for (int col = 0; col < n; ++col) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                backtrack(res, board, row + 1);
                board[row][col] = '.';
            }
        }
    }

    bool isValid(vector<string>& board, int row, int col) {
        int n = board.size();
        // 检查列是否冲突
        for (int i = 0; i < row; ++i) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }
        // 检查左上方是否冲突
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        // 检查右上方是否冲突
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
};

int main() {
    Solution sol;
    int n = 4;
    vector<vector<string>> res = sol.solveNQueens(n);
    for (int i = 0; i < res.size(); ++i) {
        for (int j = 0; j < n; ++j) {
            cout << res[i][j] << endl;
        }
        cout << endl;
    }
    return 0;
}

在上面的程序中，我们使用了回溯算法来解决 N 皇后问题。在回溯的过程中，我们逐行放置皇后，对于每一行，我们枚举所有的列，找到一个合法的位置，然后递归到下一行继续放置皇后，如果无法找到合法的位置，则回溯到上一行重新放置皇后。

在检查是否合法的时候，我们需要检查当前列是否已经被占用，以及左上方和右上方是否有皇后。如果有任何一个条件不满足，则说明当前位置无法放置皇后。

最终，我们将所有合法的解保存在一个二维数组中，并输出到标准输出中。