§1

题目描述

在 N×N 棋盘上放 N 个皇后，使任意两个都不在同一行、同一列、同一条对角线上。返回所有摆法。

n = 4

输出 = 2 种摆法

§2

思路解析动画文字版

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

转折：既然每行必有且只有一个皇后，那就一行行来，把「选 N 个格子」变成「每行选一列」。在第 r 行放之前，先看这列、这两条对角线有没有被占——没占才放，撞了就跳过，整行都放不下就回退上一行。

逐行放，所以不用查行。只需查三样：同一列、主对角线（行−列相同）、副对角线（行+列相同）。三个集合 O(1) 判定。

第 0 行 · 试 (0,0)：先在第 0 行第 0 列放一个皇后(试探态)，记下列0、主对角线 0−0、副对角线 0+0 被占，试试这条路走不走得通。

第 1 行 · 前两列被攻击：进到第 1 行从左往右试：(1,0) 和上面的皇后同列、(1,1) 在主对角线上(行差1=列差1)，都被攻击(红格)，跳过。

第 1 行 · 落子 (1,2)：继续到 (1,2)：列 2 没占、两条对角线也没占 → 安全，放下。记列2、对角线 1−2、1+2 被占，再下探第 2 行。

第 2 行 · 无处可放：负例分支：第 2 行每个格子都被前两个皇后的列或斜线盯上——(2,0)同列、(2,1)在(1,2)的副对角线、(2,2)同列、(2,3)在(1,2)的主对角线。整行没安全列，这条路死了，回溯。

(1,2) 走死 → 改试 (1,3)，仍走死：(0,0) 开局的两个落点(列2、列3)往下都走死——不是 (1,3) 被攻击，是它的子树没有解。

退回第 0 行 · 换 (0,1)：(0,0) 这一整支开局失败，回到第 0 行换下一列 (0,1) 重新尝试。

第 1 行 · 推进到 (1,3)：新开局后第 1 行试列：列1同列、(1,0)和(1,2)分别在 (0,1) 的两条对角线上，只有 (1,3) 安全 → 放下，继续下探。

顺下来了 · 一个完整解：接着第 2 行只剩 (2,0)、第 3 行只剩 (3,2)，r 推到 4(== n) → 四个皇后互不攻击，第一个解到手。继续回溯还能找到它的镜像，凑齐 2 个解。

约束类回溯的范本：把限制（同列/对角线）变成 O(1) 的剪枝，逐行推进，死路立刻回退。

边界三连：本题真边界：n=1、n=2/3 无解、n=4。

面试官常追问：三个高频追问，回溯+对角线编码必背。

§3

参考代码

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

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间复杂度：O(N!)，第 r 行最多剩 N−r 个安全列，层层相乘逼近 N!，但剪枝砍掉大量死分支
空间复杂度：O(N)，三个集合各至多 N 项 + 递归栈深 N + 棋盘 N×N(可压成一维)

§5

可套用的代码模板

逐行递归、冲突就 continue、放下记占用、回溯清占用。对角线用 r−c 和 r+c 编号，是这题最妙的一笔。

Python

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

§6

易错点

✗ 错误写法：对角线只判一条

✓ 正确写法：主对角线 r−c、副对角线 r+c 都要判

皇后主、副两条斜线都能攻击。比如只判主对角 r−c：(0,3) 与 (3,0) 都在副对角线 r+c=3 上、会互相攻击，但它们 r−c 不同(−3 vs 3)，只判 r−c 抓不到 → 必须同时维护 r−c 和 r+c 两个集合。

✗ 错误写法：放下记了占用，回溯忘了清

✓ 正确写法：放下/撤回成对出现

不清占用，回退后那些列/对角线仍被误认为占着，后面分支会漏掉 (0,1) 这条合法解

✗ 错误写法：收解时存 board 引用

✓ 正确写法：存 board 每行的字符串快照

board 会被后续回溯改回 "."，存引用会让所有解都变成最后那个空棋盘

面试追问把动画讲成自己的话

追问核心思路是什么？

逐行回溯：第 r 行尝试每一列 c，若 c、r−c、r+c 都不在冲突集合里就放下皇后、加入三个集合、递归到 r+1；递归返回后撤销(回溯)、换下一列。放满 n 行得到一个解。

追问为什么复杂度是 O(N!)？

第一行有 N 个选择，第二行受列与对角约束后至多 N−1 个，依次递减，上界是 N!。实际有对角线剪枝，远小于 N!，但最坏上界仍记 O(N!)。

追问如果只要解的「个数」(LC52 N 皇后 II)怎么改？

不用存棋盘，把三个集合的逻辑保留，递归到 r==n 时计数 +1 即可，空间从 O(N²) 降到 O(N)。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：

下一题 · 回溯 10/11

解数独

LeetCode 37 · 困难 · 沿着回溯继续往下推进

→

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

299道动画图解

37节语音讲解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题

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