n皇后问题最快算法代码

n皇后问题是一个经典的回溯算法问题，其时间复杂度不可避免的是指数级别的，因此不存在快速解法。

下面给出一个常规的n皇后问题的回溯算法实现示例，该实现使用了一个大小为n的一维数组来记录每行所放置的皇后所在列的位置，具体实现如下：

#include <iostream>
#include <vector>

using namespace std;

void n_queens(int n, vector<int>& queens, vector<vector<int>>& result) {
    if (queens.size() == n) {
        result.push_back(queens);
        return;
    }
    for (int i = 0; i < n; i++) {
        bool flag = true;
        for (int j = 0; j < queens.size(); j++) {
            if (queens[j] == i || abs(queens[j] - i) == abs(j - queens.size())) {
                flag = false;
                break;
            }
        }
        if (flag) {
            queens.push_back(i);
            n_queens(n, queens, result);
            queens.pop_back();
        }
    }
}

int main() {
    int n = 8; // 设置棋盘大小n
    vector<int> queens;
    vector<vector<int>> result;
    n_queens(n, queens, result);
    cout << "Total solutions: " << result.size() << endl;
    for (int i = 0; i < result.size(); i++) {
        for (int j = 0; j < result[i].size(); j++) {
            cout << result[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

该实现中的`queens`数组记录了每行所放置的皇后所在列的位置，`result`数组用于存储所有的解。在`n_queens`函数中，首先判断当前行是否已经放置完毕，如果已经放置完毕，则将当前解存储到`result`数组中，然后返回上一层。如果当前行还没有放置完毕，那么就在当前行的所有列中依次尝试放置皇后，如果放置皇后后不会与之前的皇后冲突，则继续递归到下一行。如果当前行所有列都无法放置皇后，则返回上一层。

该实现的时间复杂度为O(n!)，空间复杂度为O(n)。