N 皇后 图解题解

这道题到底在问什么

n

4

输出

2 种摆法

先想最直接的笨办法

N=8 时光「16 选 8」就上亿种摆法，绝大多数一眼就违规，全枚举出来再筛根本扛不住。（动画第 3 步）

最优解：一步一步想明白

1. 3N=8 时光「16 选 8」就上亿种摆法，绝大多数一眼就违规，全枚举出来再筛根本扛不住。
2. 4转折：既然每行必有且只有一个皇后，那就一行行来，把「选 N 个格子」变成「每行选一列」。在第 r 行放之前，先看这列、这两条对角线有没有被占——没占才放，撞了就跳过，整行都放不下就回退上一行。
3. 5逐行放，所以不用查行。只需查三样：同一列、主对角线（行−列 相同）、副对角线（行+列 相同）。三个集合 O(1) 判定。
4. 6r=0 放第 0 列先在第 0 行第 0 列放一个皇后(试探态)，记下 列0、主对角线 0−0、副对角线 0+0 被占，试试这条路走不走得通。
5. 7(1,0)同列 (1,1)同斜进到第 1 行从左往右试：(1,0) 和上面的皇后同列、(1,1) 在主对角线上(行差1=列差1)，都被攻击(红格)，跳过。
6. 8第一个安全列继续到 (1,2)：列 2 没占、两条对角线也没占 → 安全，放下。记列2、对角线 1−2、1+2 被占，再下探第 2 行。
7. 9四列全被攻击 → 回溯负例分支：第 2 行每个格子都被前两个皇后的列或斜线盯上——(2,0)同列、(2,1)在(1,2)的副对角线、(2,2)同列、(2,3)在(1,2)的主对角线。整行没安全列，这条路死了，回溯。
8. 10撤 (1,2)，本行也试完(0,0) 开局的两个落点(列2、列3)往下都走死——不是 (1,3) 被攻击，是它的子树没有解。
9. 11第 0 行改放第 1 列(0,0) 这一整支开局失败，回到第 0 行换下一列 (0,1) 重新尝试。
10. 12(0,1) 下唯一安全列新开局后第 1 行试列：列1同列、(1,0)和(1,2)分别在 (0,1) 的两条对角线上，只有 (1,3) 安全 → 放下，继续下探。
11. 13(0,1)(1,3)(2,0)(3,2)接着第 2 行只剩 (2,0)、第 3 行只剩 (3,2)，r 推到 4(== n) → 四个皇后互不攻击，第一个解到手。继续回溯还能找到它的镜像，凑齐 2 个解。
12. 16约束类回溯的范本：把限制（同列/对角线）变成 O(1) 的剪枝，逐行推进，死路立刻回退。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def solveNQueens(self, n):
        ans = []
        board = [["."]*n for _ in range(n)]
        cols, d1, d2 = set(), set(), set()   # d1=r-c(↘), d2=r+c(↙)
        def backtrack(r):
            if r == n:
                ans.append(["".join(row) for row in board]); return
            for c in range(n):
                if c in cols or (r-c) in d1 or (r+c) in d2:
                    continue                 # 列/两对角线 冲突则跳过
                board[r][c] = "Q"
                cols.add(c); d1.add(r-c); d2.add(r+c)
                backtrack(r + 1)             # 放下，进下一行
                board[r][c] = "."            # 撤销，换下一列
                cols.discard(c); d1.discard(r-c); d2.discard(r+c)
        backtrack(0)
        return ans

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> ans;
        vector<string> board(n, string(n, '.'));
        set<int> cols, d1, d2;               // d1=r-c, d2=r+c
        function<void(int)> bt = [&](int r) {
            if (r == n) { ans.push_back(board); return; }
            for (int c = 0; c < n; c++) {
                if (cols.count(c) || d1.count(r-c) || d2.count(r+c)) continue;
                board[r][c] = 'Q';
                cols.insert(c); d1.insert(r-c); d2.insert(r+c);
                bt(r + 1);
                board[r][c] = '.';            // 回溯撤销
                cols.erase(c); d1.erase(r-c); d2.erase(r+c);
            }
        };
        bt(0);
        return ans;
    }
};

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<>();
        char[][] b = new char[n][n];
        for (char[] row : b) Arrays.fill(row, '.');
        Set<Integer> cols = new HashSet<>(), d1 = new HashSet<>(), d2 = new HashSet<>();
        bt(0, n, b, cols, d1, d2, ans);
        return ans;
    }
    void bt(int r, int n, char[][] b, Set<Integer> cols, Set<Integer> d1, Set<Integer> d2, List<List<String>> ans) {
        if (r == n) {
            List<String> sol = new ArrayList<>();
            for (char[] row : b) sol.add(new String(row));
            ans.add(sol); return;
        }
        for (int c = 0; c < n; c++) {
            if (cols.contains(c) || d1.contains(r-c) || d2.contains(r+c)) continue;
            b[r][c] = 'Q'; cols.add(c); d1.add(r-c); d2.add(r+c);
            bt(r + 1, n, b, cols, d1, d2, ans);
            b[r][c] = '.'; cols.remove(c); d1.remove(r-c); d2.remove(r+c);
        }
    }
}

def bt(r):
    if r == n: 收集一个解; return
    for c in range(n):
        if 冲突(r, c): continue
        放下(r, c) + 记录占用
        bt(r + 1)
        撤回(r, c) + 清除占用

复杂度

面试官可能追问