n皇后问题c++

n 皇后问题可以用回溯算法来解决，以下是 C++ 代码实现：

#include <iostream>
#include <vector>

using namespace std;

void solveNQueens(int n, vector<vector<string>>& res, vector<string>& board, vector<int>& cols, vector<int>& diag1, vector<int>& diag2, int row) {
    if (row == n) {
        res.push_back(board);
        return;
    }
    for (int col = 0; col < n; col++) {
        if (cols[col] || diag1[row + col] || diag2[row - col + n - 1]) {
            continue;
        }
        board[row][col] = 'Q';
        cols[col] = 1;
        diag1[row + col] = 1;
        diag2[row - col + n - 1] = 1;
        solveNQueens(n, res, board, cols, diag1, diag2, row + 1);
        board[row][col] = '.';
        cols[col] = 0;
        diag1[row + col] = 0;
        diag2[row - col + n - 1] = 0;
    }
}

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> res;
    vector<string> board(n, string(n, '.'));
    vector<int> cols(n, 0);
    vector<int> diag1(2 * n - 1, 0);
    vector<int> diag2(2 * n - 1, 0);
    solveNQueens(n, res, board, cols, diag1, diag2, 0);
    return res;
}

int main() {
    int n = 4;
    vector<vector<string>> res = 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;
}

其中，solveNQueens 函数是主要的递归函数，cols 数组表示列是否被占用，diag1 和 diag2 数组则表示两个对角线是否被占用。一旦找到一个可行解，就将其保存在 res 中。最后输出所有的可行解即可。