n皇后问题的回溯算法时间复杂性c代码

n皇后问题的回溯算法时间复杂性为O(n!)，即n的阶乘。这是因为在每一行中只能放置一个皇后，而每一列、每一行、每一条对角线上都只能有一个皇后，因此需要进行大量的搜索和回溯。以下是C++代码实现：

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

void backtrack(vector<vector<string>>& res, vector<string>& board, int row, int n, vector<int>& cols, vector<int>& diag1, vector<int>& diag2) {
    if (row == n) {
        res.push_back(board);
        return;
    }
    for (int col = 0; col < n; col++) {
        if (cols[col] || diag1[row + col] || diag2[row - col + n - 1]) {
            continue;
        }
        board[row][col] = 'Q';
        cols[col] = 1;
        diag1[row + col] = 1;
        diag2[row - col + n - 1] = 1;
        backtrack(res, board, row + 1, n, cols, diag1, diag2);
        board[row][col] = '.';
        cols[col] = 0;
        diag1[row + col] = 0;
        diag2[row - col + n - 1] = 0;
    }
}

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> res;
    vector<string> board(n, string(n, '.'));
    vector<int> cols(n, 0);
    vector<int> diag1(2 * n - 1, 0);
    vector<int> diag2(2 * n - 1, 0);
    backtrack(res, board, 0, n, cols, diag1, diag2);
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<vector<string>> res = solveNQueens(n);
    for (auto& board : res) {
        for (auto& row : board) {
            cout << row << endl;
        }
        cout << endl;
    }
    return 0;
}