pta八皇后问题

八皇后问题是指在一个 8×8 的棋盘上放置 8 个皇后，使得任意两个皇后都不能处于同一行、同一列或同一斜线上。这是一个经典的回溯算法问题，可以通过 DFS（深度优先搜索）进行求解。

具体实现时，我们可以从第一行开始，尝试在每一列放置一个皇后，然后递归到下一行。如果在某一行中找不到合适的位置放置皇后，则回溯到上一行重新尝试。如果在第八行中成功放置了皇后，则表示找到了一组解。

下面是一个简单的 C++ 实现：

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> res;

bool isValid(vector<int>& pos, int row, int col) {
    for (int i = 0; i < row; i++) {
        if (pos[i] == col || abs(i - row) == abs(pos[i] - col)) {
            return false;
        }
    }
    return true;
}

void solveNQueens(vector<int>& pos, int row) {
    if (row == 8) {
        res.push_back(pos);
        return;
    }
    for (int col = 0; col < 8; col++) {
        if (isValid(pos, row, col)) {
            pos[row] = col;
            solveNQueens(pos, row + 1);
            pos[row] = -1;
        }
    }
}

int main() {
    vector<int> pos(8, -1);
    solveNQueens(pos, 0);
    for (auto& p : res) {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (j == p[i]) {
                    cout << "Q ";
                } else {
                    cout << ". ";
                }
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}

该算法的时间复杂度为 O(n!)，其中 n 为棋盘的大小。因此，当棋盘较大时，该算法的时间复杂度会非常高，需要进行优化。