51. N 皇后

难度：🔴 Hard | 标签：回溯 | 状态：⬜ LeetCode 链接

思路

逐行放皇后。同一行只放一个，所以维护：

• col[]：列占用
• diag1[r-c+n-1]：主对角线
• diag2[r+c]：副对角线

代码

class Solution {
    vector<vector<string>> res;
    vector<string> board;
    vector<bool> col, d1, d2;
    int n_;
    void dfs(int r) {
        if (r == n_) { res.push_back(board); return; }
        for (int c = 0; c < n_; ++c) {
            int i1 = r - c + n_ - 1, i2 = r + c;
            if (col[c] || d1[i1] || d2[i2]) continue;
            col[c] = d1[i1] = d2[i2] = true;
            board[r][c] = 'Q';
            dfs(r + 1);
            board[r][c] = '.';
            col[c] = d1[i1] = d2[i2] = false;
        }
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        n_ = n;
        board.assign(n, string(n, '.'));
        col.assign(n, false); d1.assign(2 * n - 1, false); d2.assign(2 * n - 1, false);
        dfs(0);
        return res;
    }
};

复杂度

• 时间 O(n!)，空间 O(n)

易错 / 回顾

• 主对角 r - c、副对角 r + c 都是同对角线上的不变量
• 用 + n - 1 偏移使下标 ≥ 0
• 52 题（只数解的数量）同套路，只是不存 board