题目描述
思路解析动画文字版
记住「每行枚举列 → 三集合判冲突 → 落子递归 → 撤销回退」,下面对着 4×4 棋盘逐帧套。
N 皇后 · 4×4 棋盘：第 0 行的列 0(橙格)不在任何冲突集合里,安全!把皇后落在这里。
N 皇后 · 4×4 棋盘：落子 (0, 0),同时把列 0、主对角 r-c=0、副对角 r+c=0 三个值记进集合,挡住后面行的同列、同斜线。下探第 1 行。
N 皇后 · 4×4 棋盘：在第 1 行尝试列 0(红格):列 0 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 1 行尝试列 1(红格):主对角线(r-c=0)已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：第 1 行的列 2(橙格)不在任何冲突集合里,安全!把皇后落在这里。
N 皇后 · 4×4 棋盘：落子 (1, 2),同时把列 2、主对角 r-c=-1、副对角 r+c=3 三个值记进集合,挡住后面行的同列、同斜线。下探第 2 行。
N 皇后 · 4×4 棋盘：在第 2 行尝试列 0(红格):列 0 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 2 行尝试列 1(红格):副对角线(r+c=3)已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 2 行尝试列 2(红格):列 2 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 2 行尝试列 3(红格):主对角线(r-c=-1)已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：第 2 行那一支已经探完,回溯:把 (1, 2) 的皇后拿走,撤销列 2、主对角 -1、副对角 3 的记录,腾出空间去试第 1 行的下一列。
N 皇后 · 4×4 棋盘：第 1 行的列 3(橙格)不在任何冲突集合里,安全!把皇后落在这里。
N 皇后 · 4×4 棋盘：落子 (1, 3),同时把列 3、主对角 r-c=-2、副对角 r+c=4 三个值记进集合,挡住后面行的同列、同斜线。下探第 2 行。
N 皇后 · 4×4 棋盘：在第 2 行尝试列 0(红格):列 0 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：第 2 行的列 1(橙格)不在任何冲突集合里,安全!把皇后落在这里。
N 皇后 · 4×4 棋盘：落子 (2, 1),同时把列 1、主对角 r-c=1、副对角 r+c=3 三个值记进集合,挡住后面行的同列、同斜线。下探第 3 行。
N 皇后 · 4×4 棋盘：在第 3 行尝试列 0(红格):列 0 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 3 行尝试列 1(红格):列 1 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 3 行尝试列 2(红格):主对角线(r-c=1)已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 3 行尝试列 3(红格):列 3 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：第 3 行那一支已经探完,回溯:把 (2, 1) 的皇后拿走,撤销列 1、主对角 1、副对角 3 的记录,腾出空间去试第 2 行的下一列。
N 皇后 · 4×4 棋盘：在第 2 行尝试列 2(红格):主对角线(r-c=0)已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 2 行尝试列 3(红格):列 3 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：第 2 行那一支已经探完,回溯:把 (1, 3) 的皇后拿走,撤销列 3、主对角 -2、副对角 4 的记录,腾出空间去试第 1 行的下一列。
N 皇后 · 4×4 棋盘：第 1 行那一支已经探完,回溯:把 (0, 0) 的皇后拿走,撤销列 0、主对角 0、副对角 0 的记录,腾出空间去试第 0 行的下一列。
N 皇后 · 4×4 棋盘：第 0 行的列 1(橙格)不在任何冲突集合里,安全!把皇后落在这里。
N 皇后 · 4×4 棋盘：落子 (0, 1),同时把列 1、主对角 r-c=-1、副对角 r+c=1 三个值记进集合,挡住后面行的同列、同斜线。下探第 1 行。
N 皇后 · 4×4 棋盘：在第 1 行尝试列 0(红格):副对角线(r+c=1)已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 1 行尝试列 1(红格):列 1 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 1 行尝试列 2(红格):主对角线(r-c=-1)已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：第 1 行的列 3(橙格)不在任何冲突集合里,安全!把皇后落在这里。
N 皇后 · 4×4 棋盘：落子 (1, 3),同时把列 3、主对角 r-c=-2、副对角 r+c=4 三个值记进集合,挡住后面行的同列、同斜线。下探第 2 行。
N 皇后 · 4×4 棋盘：第 2 行的列 0(橙格)不在任何冲突集合里,安全!把皇后落在这里。
N 皇后 · 4×4 棋盘：落子 (2, 0),同时把列 0、主对角 r-c=2、副对角 r+c=2 三个值记进集合,挡住后面行的同列、同斜线。下探第 3 行。
N 皇后 · 4×4 棋盘：在第 3 行尝试列 0(红格):列 0 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 3 行尝试列 1(红格):列 1 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：第 3 行的列 2(橙格)不在任何冲突集合里,安全!把皇后落在这里。
N 皇后 · 4×4 棋盘：落子 (3, 2),同时把列 2、主对角 r-c=1、副对角 r+c=5 三个值记进集合,挡住后面行的同列、同斜线。下探第 4 行。
N 皇后 · 4×4 棋盘：走到第 4 行,意味着 4 个皇后全部安全落位,任两个都不互相攻击。这是第 1 种合法摆法,方案数 ans 加到 1。记下它,然后回头继续找别的摆法。
N 皇后 · 4×4 棋盘：第 4 行那一支已经探完,回溯:把 (3, 2) 的皇后拿走,撤销列 2、主对角 1、副对角 5 的记录,腾出空间去试第 3 行的下一列。
N 皇后 · 4×4 棋盘：在第 3 行尝试列 3(红格):列 3 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：第 3 行那一支已经探完,回溯:把 (2, 0) 的皇后拿走,撤销列 0、主对角 2、副对角 2 的记录,腾出空间去试第 2 行的下一列。
N 皇后 · 4×4 棋盘：在第 2 行尝试列 1(红格):列 1 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 2 行尝试列 2(红格):副对角线(r+c=4)已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 2 行尝试列 3(红格):列 3 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：第 2 行那一支已经探完,回溯:把 (1, 3) 的皇后拿走,撤销列 3、主对角 -2、副对角 4 的记录,腾出空间去试第 1 行的下一列。
N 皇后 · 4×4 棋盘：第 1 行那一支已经探完,回溯:把 (0, 1) 的皇后拿走,撤销列 1、主对角 -1、副对角 1 的记录,腾出空间去试第 0 行的下一列。
N 皇后 · 4×4 棋盘：第 0 行的列 2(橙格)不在任何冲突集合里,安全!把皇后落在这里。
N 皇后 · 4×4 棋盘：落子 (0, 2),同时把列 2、主对角 r-c=-2、副对角 r+c=2 三个值记进集合,挡住后面行的同列、同斜线。下探第 1 行。
N 皇后 · 4×4 棋盘：第 1 行的列 0(橙格)不在任何冲突集合里,安全!把皇后落在这里。
N 皇后 · 4×4 棋盘：落子 (1, 0),同时把列 0、主对角 r-c=1、副对角 r+c=1 三个值记进集合,挡住后面行的同列、同斜线。下探第 2 行。
N 皇后 · 4×4 棋盘：在第 2 行尝试列 0(红格):列 0 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 2 行尝试列 1(红格):主对角线(r-c=1)已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 2 行尝试列 2(红格):列 2 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：第 2 行的列 3(橙格)不在任何冲突集合里,安全!把皇后落在这里。
N 皇后 · 4×4 棋盘：落子 (2, 3),同时把列 3、主对角 r-c=-1、副对角 r+c=5 三个值记进集合,挡住后面行的同列、同斜线。下探第 3 行。
N 皇后 · 4×4 棋盘：在第 3 行尝试列 0(红格):列 0 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：第 3 行的列 1(橙格)不在任何冲突集合里,安全!把皇后落在这里。
N 皇后 · 4×4 棋盘：落子 (3, 1),同时把列 1、主对角 r-c=2、副对角 r+c=4 三个值记进集合,挡住后面行的同列、同斜线。下探第 4 行。
N 皇后 · 4×4 棋盘：走到第 4 行,意味着 4 个皇后全部安全落位,任两个都不互相攻击。这是第 2 种合法摆法,方案数 ans 加到 2。记下它,然后回头继续找别的摆法。
N 皇后 · 4×4 棋盘：第 4 行那一支已经探完,回溯:把 (3, 1) 的皇后拿走,撤销列 1、主对角 2、副对角 4 的记录,腾出空间去试第 3 行的下一列。
N 皇后 · 4×4 棋盘：在第 3 行尝试列 2(红格):列 2 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 3 行尝试列 3(红格):列 3 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：第 3 行那一支已经探完,回溯:把 (2, 3) 的皇后拿走,撤销列 3、主对角 -1、副对角 5 的记录,腾出空间去试第 2 行的下一列。
N 皇后 · 4×4 棋盘：第 2 行那一支已经探完,回溯:把 (1, 0) 的皇后拿走,撤销列 0、主对角 1、副对角 1 的记录,腾出空间去试第 1 行的下一列。
N 皇后 · 4×4 棋盘：在第 1 行尝试列 1(红格):副对角线(r+c=2)已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 1 行尝试列 2(红格):列 2 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 1 行尝试列 3(红格):主对角线(r-c=-2)已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：第 1 行那一支已经探完,回溯:把 (0, 2) 的皇后拿走,撤销列 2、主对角 -2、副对角 2 的记录,腾出空间去试第 0 行的下一列。
N 皇后 · 4×4 棋盘：第 0 行的列 3(橙格)不在任何冲突集合里,安全!把皇后落在这里。
N 皇后 · 4×4 棋盘：落子 (0, 3),同时把列 3、主对角 r-c=-3、副对角 r+c=3 三个值记进集合,挡住后面行的同列、同斜线。下探第 1 行。
N 皇后 · 4×4 棋盘：第 1 行的列 0(橙格)不在任何冲突集合里,安全!把皇后落在这里。
N 皇后 · 4×4 棋盘：落子 (1, 0),同时把列 0、主对角 r-c=1、副对角 r+c=1 三个值记进集合,挡住后面行的同列、同斜线。下探第 2 行。
N 皇后 · 4×4 棋盘：在第 2 行尝试列 0(红格):列 0 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 2 行尝试列 1(红格):主对角线(r-c=1)已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：第 2 行的列 2(橙格)不在任何冲突集合里,安全!把皇后落在这里。
N 皇后 · 4×4 棋盘：落子 (2, 2),同时把列 2、主对角 r-c=0、副对角 r+c=4 三个值记进集合,挡住后面行的同列、同斜线。下探第 3 行。
N 皇后 · 4×4 棋盘：在第 3 行尝试列 0(红格):列 0 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 3 行尝试列 1(红格):副对角线(r+c=4)已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 3 行尝试列 2(红格):列 2 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 3 行尝试列 3(红格):列 3 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：第 3 行那一支已经探完,回溯:把 (2, 2) 的皇后拿走,撤销列 2、主对角 0、副对角 4 的记录,腾出空间去试第 2 行的下一列。
N 皇后 · 4×4 棋盘：在第 2 行尝试列 3(红格):列 3 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：第 2 行那一支已经探完,回溯:把 (1, 0) 的皇后拿走,撤销列 0、主对角 1、副对角 1 的记录,腾出空间去试第 1 行的下一列。
N 皇后 · 4×4 棋盘：第 1 行的列 1(橙格)不在任何冲突集合里,安全!把皇后落在这里。
N 皇后 · 4×4 棋盘：落子 (1, 1),同时把列 1、主对角 r-c=0、副对角 r+c=2 三个值记进集合,挡住后面行的同列、同斜线。下探第 2 行。
N 皇后 · 4×4 棋盘：在第 2 行尝试列 0(红格):副对角线(r+c=2)已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 2 行尝试列 1(红格):列 1 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 2 行尝试列 2(红格):主对角线(r-c=0)已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 2 行尝试列 3(红格):列 3 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：第 2 行那一支已经探完,回溯:把 (1, 1) 的皇后拿走,撤销列 1、主对角 0、副对角 2 的记录,腾出空间去试第 1 行的下一列。
N 皇后 · 4×4 棋盘：在第 1 行尝试列 2(红格):副对角线(r+c=3)已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：在第 1 行尝试列 3(红格):列 3 已有皇后,会被已有皇后攻击,跳过,看下一列。
N 皇后 · 4×4 棋盘：第 1 行那一支已经探完,回溯:把 (0, 3) 的皇后拿走,撤销列 3、主对角 -3、副对角 3 的记录,腾出空间去试第 0 行的下一列。
N 皇后 · 4×4 棋盘：所有分支都试完了,4×4 棋盘一共找到 2 种合法摆法,返回 ans = 2。这就是 N 皇后 II 的答案:它只数方案个数,不用记录每个棋盘的具体样子。
边界:n=1 答 1;n=2、n=3 无解答 0;n=4 起才有合法摆法。
两个高频追问:I 题需拼棋盘、II 题只计数;进阶用位运算或对称剪枝提速。
参考代码
class Solution: def totalNQueens(self, n: int) -> int: ans = 0 cols, d1, d2 = set(), set(), set() def dfs(r): nonlocal ans if r == n: ans += 1 return for c in range(n): if c in cols or r - c in d1 or r + c in d2: continue cols.add(c); d1.add(r - c); d2.add(r + c) dfs(r + 1) cols.remove(c); d1.remove(r - c); d2.remove(r + c) dfs(0) return ans复杂度
- 时间：O(n!)，第 0 行有 n 个候选列,第 1 行最多 n-1 个(同列被挡),依次递减,搜索树规模约 n!;每个结点判冲突 O(1)
- 空间：O(n)，递归深度最多 n 层;cols/d1/d2 三个集合各最多存 n 个元素,均为 O(n)
易错点
面试追问把动画讲成自己的话
追问N 皇后 I 要返回所有具体棋盘,和这道 II 题(只数数量)在实现上差在哪?
追问还能怎么进一步加速?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
给表达式添加运算符
LeetCode 282 · 困难 · 沿着 回溯套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题