51 N 皇后

题目链接

51. N 皇后

分析

经典的回溯法问题

可以发现，对于左对角线，行列相减均相等；对于右对角线，行列相加均相等

所以我们使用 $col, d1,d2$ 分别记录列和两条对角线是否有皇后

回溯计算即可

代码实现

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ans;
        vector<bool> col(n, false), d1(n * 2 - 1, false), d2(n * 2 - 1, false);
        vector<int> queenidx(n);
        auto dfs = [&](auto&& dfs, int r) {
            if(r == n)
            {
                vector<string> board(n);
                for(int i = 0; i < n; ++i) {
                    board[i] = string(n, '.');
                    board[i][queenidx[i]] = 'Q';
                }
                ans.push_back(board);
                return ;
            }

            for(int c = 0; c < n; c++)
            {
                int t = r - c + n - 1;
                if(!col[c] && !d1[r + c] && !d2[t])
                {
                    queenidx[r] = c;
                    col[c] = d1[r + c] = d2[t] = true;
                    dfs(dfs, r + 1);
                    col[c] = d1[r + c] = d2[t] = false; 
                }
            }
        };
        dfs(dfs, 0);
        return ans;
    }
};

复杂度分析

• 时间复杂度：$O(N!)$
• 空间复杂度：$O(n)$