八皇后问题

八皇后问题是一个经典的回溯算法问题，其描述为：在一个8×8的棋盘上，摆放8个皇后，使得任意两个皇后都不能在同一行、同一列或同一斜线上。如何求出所有满足条件的摆法？

解决这个问题的一种方法是使用回溯算法，即从第一行开始，依次尝试在每个列上放置一个皇后，并检查是否符合条件。如果符合条件，则继续到下一行进行尝试。如果所有行都尝试完成，就可以得到一种摆法。如果不能在某一行上找到一个合适的位置，则回溯到上一行，重新尝试其他的列，直到找到所有的摆法。

以下是一个C++代码示例：

#include <iostream>
#include <vector>

using namespace std;

// 检查在(row, col)位置上是否可以放置皇后
bool check(vector<int>& queens, int row, int col)
{
    for (int i = 0; i < row; i++) {
        int diff = abs(queens[i] - col);
        if (diff == 0 || diff == row - i) {   // 检查是否在同一列或同一斜线上
            return false;
        }
    }
    return true;
}

// 在第row行上尝试放置皇后
void backtrack(vector<vector<string>>& res, vector<int>& queens, int n, int row)
{
    if (row == n) {   // 找到了一种合法的摆法
        vector<string> board(n, string(n, '.'));
        for (int i = 0; i < n; i++) {
            board[i][queens[i]] = 'Q';
        }
        res.push_back(board);
    } else {
        for (int col = 0; col < n; col++) {
            if (check(queens, row, col)) {   // 检查是否符合条件
                queens[row] = col;
                backtrack(res, queens, n, row + 1);
                queens[row] = -1;
            }
        }
    }
}

// 求解N皇后问题
vector<vector<string>> solveNQueens(int n)
{
    vector<vector<string>> res;
    vector<int> queens(n, -1);   // queens[i]表示第i行上的皇后所在的列
    backtrack(res, queens, n, 0);
    return res;
}

int main()
{
    int n = 8;
    vector<vector<string>> res = solveNQueens(n);

    for (int i = 0; i < res.size(); i++) {
        cout << "Solution " << i + 1 << ":" << endl;
        for (int j = 0; j < res[i].size(); j++) {
            cout << res[i][j] << endl;
        }
        cout << endl;
    }
    return 0;
}

该算法的时间复杂度为O(n^n)，因为每一行都需要尝试n个位置，并且需要进行n次回溯。空间复杂度为O(n)，因为需要使用一个长度为n的数组来保存每行上皇后的位置。