递归算法求解八皇后问题c++

下面是基于C++语言的递归算法求解八皇后问题的代码实现：

#include <iostream>
#include <vector>

using namespace std;

void queens(int n, int row, vector<bool>& col, vector<bool>& diagonal, vector<bool>& anti_diagonal, vector<string>& cur, vector<vector<string>>& res) {
    if (row == n) {
        res.push_back(cur);
        return;
    }
    for (int j = 0; j < n; j++) {
        if (col[j] || diagonal[row+j] || anti_diagonal[row-j+n-1]) {
            continue;
        }
        string cur_row(n, '.');
        cur_row[j] = 'Q';
        cur.push_back(cur_row);
        col[j] = true;
        diagonal[row+j] = true;
        anti_diagonal[row-j+n-1] = true;
        queens(n, row+1, col, diagonal, anti_diagonal, cur, res);
        cur.pop_back();
        col[j] = false;
        diagonal[row+j] = false;
        anti_diagonal[row-j+n-1] = false;
    }
}

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> res;
    vector<bool> col(n, false);
    vector<bool> diagonal(2*n-1, false);
    vector<bool> anti_diagonal(2*n-1, false);
    vector<string> cur;
    queens(n, 0, col, diagonal, anti_diagonal, cur, res);
    return res;
}

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

这里的 `queens` 函数用于递归求解八皇后问题，`solveNQueens` 函数用于返回所有的解决方案。