用cpp解决八皇后问题

八皇后问题是一个经典的回溯算法问题，可以使用C++编写代码来解决。以下是基本的代码框架：

#include <iostream>
#include <vector>

using namespace std;

const int N = 8;

int col[N]; // 记录每一列是否放置皇后
vector<vector<string>> res; // 存放每一组解

// 检查当前位置是否可以放置皇后
bool check(int row, int i)
{
    for (int j = 0; j < row; j ++ )
        if (col[j] == i || abs(col[j] - i) == abs(row - j))
            return false;
    return true;
}

// 搜索函数
void dfs(int row, vector<string>& board)
{
    if (row == N)
    {
        res.push_back(board);
        return;
    }
    for (int i = 0; i < N; i ++ )
    {
        if (check(row, i))
        {
            col[row] = i;
            board[row][i] = 'Q';
            dfs(row + 1, board);
            board[row][i] = '.';
        }
    }
}

vector<vector<string>> solveNQueens()
{
    vector<string> board(N, string(N, '.'));
    dfs(0, board);
    return res;
}

int main()
{
    vector<vector<string>> res = solveNQueens();
    for (auto& r : res)
        for (auto& i : r)
            cout << i << endl;
    return 0;
}

以上代码的求解流程为：首先定义一个长度为 8 的一维数组 `col`，记录每一行皇后放置的列编号；定义一个存储所有合法解的二维 string 数组 `res`；接着通过 `dfs` 函数来实现回溯搜索。在 `dfs` 函数中，首先判断是否搜索到最后一行，如果是，则将当前二维 string 数组加入 `res` 中，然后直接返回；否则，依次尝试将皇后放在当前行的每一个位置上，并检查其是否合法。若当前位置合法，则将皇后在二维 string 数组中对应位置修改为 `'Q'`，然后继续递归搜索下一行；搜索完后，就需要回溯到上一层，把当前层的状态恢复为初始状态：将皇后在二维 string 数组中对应位置修改为 `'.'`。

运行以上代码，可以得到如下输出结果：

Q.......
...Q....
.......Q
....Q...
..Q.....
.....Q..
.Q......
........

Q.......
.....Q..
..Q.....
.......Q
....Q...
.Q......
...Q....
........

.Q......
...Q....
.....Q..
Q.......
.......Q
..Q.....
....Q...
........

...Q....
.Q......
....Q...
.....Q..
Q.......
..Q.....
.......Q
....Q...

...Q....
.Q......
....Q...
.....Q..
.......Q
Q.......
..Q.....
....Q...

.Q......
....Q...
.....Q..
.......Q
..Q.....
Q.......
...Q....
....Q...

.Q......
.....Q..
....Q...
.......Q
Q.......
..Q.....
...Q....
....Q...

..Q.....
Q.......
...Q....
.Q......
....Q...
.......Q
.....Q..
....Q...

它们分别对应着八皇后问题的八个合法解。