LeetCode 52困难回溯
N 皇后 II 图解题解
这道题到底在问什么
给定整数 n,在 n×n 棋盘上放置 n 个皇后,使任意两个皇后不能处于同一行、同一列或同一斜线。返回不同的合法方案数量。
- 输入
- n = 4
- 输出
- 2(两种经典摆法)
- 输入
- n = 1
- 输出
- 1(单格直接放)
- 输入
- n = 8
- 输出
- 92
先想最直接的笨办法
记住「每行枚举列 → 三集合判冲突 → 落子递归 → 撤销回退」,下面对着 4×4 棋盘逐帧套。（动画第 3 步）
最优解：一步一步想明白
- 3记住「每行枚举列 → 三集合判冲突 → 落子递归 → 撤销回退」,下面对着 4×4 棋盘逐帧套。
- 4第 0 行的列 0(橙格)不在任何冲突集合里,安全!把皇后落在这里。
- 5落子 (0, 0),同时把列 0、主对角 r-c=0、副对角 r+c=0 三个值记进集合,挡住后面行的同列、同斜线。下探第 1 行。
- 6在第 1 行尝试列 0(红格):列 0 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 7在第 1 行尝试列 1(红格):主对角线(r-c=0)已有皇后,会被已有皇后攻击,跳过,看下一列。
- 8第 1 行的列 2(橙格)不在任何冲突集合里,安全!把皇后落在这里。
- 9落子 (1, 2),同时把列 2、主对角 r-c=-1、副对角 r+c=3 三个值记进集合,挡住后面行的同列、同斜线。下探第 2 行。
- 10在第 2 行尝试列 0(红格):列 0 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 11在第 2 行尝试列 1(红格):副对角线(r+c=3)已有皇后,会被已有皇后攻击,跳过,看下一列。
- 12在第 2 行尝试列 2(红格):列 2 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 13在第 2 行尝试列 3(红格):主对角线(r-c=-1)已有皇后,会被已有皇后攻击,跳过,看下一列。
- 14第 2 行那一支已经探完,回溯:把 (1, 2) 的皇后拿走,撤销列 2、主对角 -1、副对角 3 的记录,腾出空间去试第 1 行的下一列。
- 15第 1 行的列 3(橙格)不在任何冲突集合里,安全!把皇后落在这里。
- 16落子 (1, 3),同时把列 3、主对角 r-c=-2、副对角 r+c=4 三个值记进集合,挡住后面行的同列、同斜线。下探第 2 行。
- 17在第 2 行尝试列 0(红格):列 0 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 18第 2 行的列 1(橙格)不在任何冲突集合里,安全!把皇后落在这里。
- 19落子 (2, 1),同时把列 1、主对角 r-c=1、副对角 r+c=3 三个值记进集合,挡住后面行的同列、同斜线。下探第 3 行。
- 20在第 3 行尝试列 0(红格):列 0 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 21在第 3 行尝试列 1(红格):列 1 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 22在第 3 行尝试列 2(红格):主对角线(r-c=1)已有皇后,会被已有皇后攻击,跳过,看下一列。
- 23在第 3 行尝试列 3(红格):列 3 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 24第 3 行那一支已经探完,回溯:把 (2, 1) 的皇后拿走,撤销列 1、主对角 1、副对角 3 的记录,腾出空间去试第 2 行的下一列。
- 25在第 2 行尝试列 2(红格):主对角线(r-c=0)已有皇后,会被已有皇后攻击,跳过,看下一列。
- 26在第 2 行尝试列 3(红格):列 3 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 27第 2 行那一支已经探完,回溯:把 (1, 3) 的皇后拿走,撤销列 3、主对角 -2、副对角 4 的记录,腾出空间去试第 1 行的下一列。
- 28第 1 行那一支已经探完,回溯:把 (0, 0) 的皇后拿走,撤销列 0、主对角 0、副对角 0 的记录,腾出空间去试第 0 行的下一列。
- 29第 0 行的列 1(橙格)不在任何冲突集合里,安全!把皇后落在这里。
- 30落子 (0, 1),同时把列 1、主对角 r-c=-1、副对角 r+c=1 三个值记进集合,挡住后面行的同列、同斜线。下探第 1 行。
- 31在第 1 行尝试列 0(红格):副对角线(r+c=1)已有皇后,会被已有皇后攻击,跳过,看下一列。
- 32在第 1 行尝试列 1(红格):列 1 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 33在第 1 行尝试列 2(红格):主对角线(r-c=-1)已有皇后,会被已有皇后攻击,跳过,看下一列。
- 34第 1 行的列 3(橙格)不在任何冲突集合里,安全!把皇后落在这里。
- 35落子 (1, 3),同时把列 3、主对角 r-c=-2、副对角 r+c=4 三个值记进集合,挡住后面行的同列、同斜线。下探第 2 行。
- 36第 2 行的列 0(橙格)不在任何冲突集合里,安全!把皇后落在这里。
- 37落子 (2, 0),同时把列 0、主对角 r-c=2、副对角 r+c=2 三个值记进集合,挡住后面行的同列、同斜线。下探第 3 行。
- 38在第 3 行尝试列 0(红格):列 0 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 39在第 3 行尝试列 1(红格):列 1 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 40第 3 行的列 2(橙格)不在任何冲突集合里,安全!把皇后落在这里。
- 41落子 (3, 2),同时把列 2、主对角 r-c=1、副对角 r+c=5 三个值记进集合,挡住后面行的同列、同斜线。下探第 4 行。
- 42走到第 4 行,意味着 4 个皇后全部安全落位,任两个都不互相攻击。这是第 1 种合法摆法,方案数 ans 加到 1。记下它,然后回头继续找别的摆法。
- 43第 4 行那一支已经探完,回溯:把 (3, 2) 的皇后拿走,撤销列 2、主对角 1、副对角 5 的记录,腾出空间去试第 3 行的下一列。
- 44在第 3 行尝试列 3(红格):列 3 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 45第 3 行那一支已经探完,回溯:把 (2, 0) 的皇后拿走,撤销列 0、主对角 2、副对角 2 的记录,腾出空间去试第 2 行的下一列。
- 46在第 2 行尝试列 1(红格):列 1 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 47在第 2 行尝试列 2(红格):副对角线(r+c=4)已有皇后,会被已有皇后攻击,跳过,看下一列。
- 48在第 2 行尝试列 3(红格):列 3 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 49第 2 行那一支已经探完,回溯:把 (1, 3) 的皇后拿走,撤销列 3、主对角 -2、副对角 4 的记录,腾出空间去试第 1 行的下一列。
- 50第 1 行那一支已经探完,回溯:把 (0, 1) 的皇后拿走,撤销列 1、主对角 -1、副对角 1 的记录,腾出空间去试第 0 行的下一列。
- 51第 0 行的列 2(橙格)不在任何冲突集合里,安全!把皇后落在这里。
- 52落子 (0, 2),同时把列 2、主对角 r-c=-2、副对角 r+c=2 三个值记进集合,挡住后面行的同列、同斜线。下探第 1 行。
- 53第 1 行的列 0(橙格)不在任何冲突集合里,安全!把皇后落在这里。
- 54落子 (1, 0),同时把列 0、主对角 r-c=1、副对角 r+c=1 三个值记进集合,挡住后面行的同列、同斜线。下探第 2 行。
- 55在第 2 行尝试列 0(红格):列 0 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 56在第 2 行尝试列 1(红格):主对角线(r-c=1)已有皇后,会被已有皇后攻击,跳过,看下一列。
- 57在第 2 行尝试列 2(红格):列 2 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 58第 2 行的列 3(橙格)不在任何冲突集合里,安全!把皇后落在这里。
- 59落子 (2, 3),同时把列 3、主对角 r-c=-1、副对角 r+c=5 三个值记进集合,挡住后面行的同列、同斜线。下探第 3 行。
- 60在第 3 行尝试列 0(红格):列 0 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 61第 3 行的列 1(橙格)不在任何冲突集合里,安全!把皇后落在这里。
- 62落子 (3, 1),同时把列 1、主对角 r-c=2、副对角 r+c=4 三个值记进集合,挡住后面行的同列、同斜线。下探第 4 行。
- 63走到第 4 行,意味着 4 个皇后全部安全落位,任两个都不互相攻击。这是第 2 种合法摆法,方案数 ans 加到 2。记下它,然后回头继续找别的摆法。
- 64第 4 行那一支已经探完,回溯:把 (3, 1) 的皇后拿走,撤销列 1、主对角 2、副对角 4 的记录,腾出空间去试第 3 行的下一列。
- 65在第 3 行尝试列 2(红格):列 2 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 66在第 3 行尝试列 3(红格):列 3 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 67第 3 行那一支已经探完,回溯:把 (2, 3) 的皇后拿走,撤销列 3、主对角 -1、副对角 5 的记录,腾出空间去试第 2 行的下一列。
- 68第 2 行那一支已经探完,回溯:把 (1, 0) 的皇后拿走,撤销列 0、主对角 1、副对角 1 的记录,腾出空间去试第 1 行的下一列。
- 69在第 1 行尝试列 1(红格):副对角线(r+c=2)已有皇后,会被已有皇后攻击,跳过,看下一列。
- 70在第 1 行尝试列 2(红格):列 2 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 71在第 1 行尝试列 3(红格):主对角线(r-c=-2)已有皇后,会被已有皇后攻击,跳过,看下一列。
- 72第 1 行那一支已经探完,回溯:把 (0, 2) 的皇后拿走,撤销列 2、主对角 -2、副对角 2 的记录,腾出空间去试第 0 行的下一列。
- 73第 0 行的列 3(橙格)不在任何冲突集合里,安全!把皇后落在这里。
- 74落子 (0, 3),同时把列 3、主对角 r-c=-3、副对角 r+c=3 三个值记进集合,挡住后面行的同列、同斜线。下探第 1 行。
- 75第 1 行的列 0(橙格)不在任何冲突集合里,安全!把皇后落在这里。
- 76落子 (1, 0),同时把列 0、主对角 r-c=1、副对角 r+c=1 三个值记进集合,挡住后面行的同列、同斜线。下探第 2 行。
- 77在第 2 行尝试列 0(红格):列 0 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 78在第 2 行尝试列 1(红格):主对角线(r-c=1)已有皇后,会被已有皇后攻击,跳过,看下一列。
- 79第 2 行的列 2(橙格)不在任何冲突集合里,安全!把皇后落在这里。
- 80落子 (2, 2),同时把列 2、主对角 r-c=0、副对角 r+c=4 三个值记进集合,挡住后面行的同列、同斜线。下探第 3 行。
- 81在第 3 行尝试列 0(红格):列 0 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 82在第 3 行尝试列 1(红格):副对角线(r+c=4)已有皇后,会被已有皇后攻击,跳过,看下一列。
- 83在第 3 行尝试列 2(红格):列 2 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 84在第 3 行尝试列 3(红格):列 3 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 85第 3 行那一支已经探完,回溯:把 (2, 2) 的皇后拿走,撤销列 2、主对角 0、副对角 4 的记录,腾出空间去试第 2 行的下一列。
- 86在第 2 行尝试列 3(红格):列 3 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 87第 2 行那一支已经探完,回溯:把 (1, 0) 的皇后拿走,撤销列 0、主对角 1、副对角 1 的记录,腾出空间去试第 1 行的下一列。
- 88第 1 行的列 1(橙格)不在任何冲突集合里,安全!把皇后落在这里。
- 89落子 (1, 1),同时把列 1、主对角 r-c=0、副对角 r+c=2 三个值记进集合,挡住后面行的同列、同斜线。下探第 2 行。
- 90在第 2 行尝试列 0(红格):副对角线(r+c=2)已有皇后,会被已有皇后攻击,跳过,看下一列。
- 91在第 2 行尝试列 1(红格):列 1 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 92在第 2 行尝试列 2(红格):主对角线(r-c=0)已有皇后,会被已有皇后攻击,跳过,看下一列。
- 93在第 2 行尝试列 3(红格):列 3 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 94第 2 行那一支已经探完,回溯:把 (1, 1) 的皇后拿走,撤销列 1、主对角 0、副对角 2 的记录,腾出空间去试第 1 行的下一列。
- 95在第 1 行尝试列 2(红格):副对角线(r+c=3)已有皇后,会被已有皇后攻击,跳过,看下一列。
- 96在第 1 行尝试列 3(红格):列 3 已有皇后,会被已有皇后攻击,跳过,看下一列。
- 97第 1 行那一支已经探完,回溯:把 (0, 3) 的皇后拿走,撤销列 3、主对角 -3、副对角 3 的记录,腾出空间去试第 0 行的下一列。
- 98所有分支都试完了,4×4 棋盘一共找到 2 种合法摆法,返回 ans = 2。这就是 N 皇后 II 的答案:它只数方案个数,不用记录每个棋盘的具体样子。
⚠️ 容易写错的地方
✗ 错：对角线判断写错方向
✓ 对：主对角线用 r-c、副对角线用 r+c
同一条主对角线上 r-c 恒相等,同一条副对角线上 r+c 恒相等,记反了就漏判或误判斜线攻击
✗ 错：落子后忘记撤销三个集合
✓ 对：递归返回后把 c、r-c、r+c 都删掉
不回溯,这些占用会残留到兄弟分支,导致后续合法位置被误判成冲突、方案数算少
✗ 错：C++/Java 对角线下标越界或为负
✓ 对：主对角用 r-c+n 平移,副对角用 r+c
r-c 可能为负不能直接当数组下标,加 n 平移到 0 到 2n-1 区间才安全
完整代码（Python / C++ / Java）
Python
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 ansC++
#include <vector>
#include <functional>
using namespace std;
class Solution {
public:
int totalNQueens(int n) {
vector<int> cols(n), d1(2*n), d2(2*n);
int ans = 0;
function<void(int)> dfs = [&](int r) {
if (r == n) { ans++; return; }
for (int c = 0; c < n; ++c) {
if (cols[c] || d1[r-c+n] || d2[r+c]) continue;
cols[c] = d1[r-c+n] = d2[r+c] = 1;
dfs(r + 1);
cols[c] = d1[r-c+n] = d2[r+c] = 0;
}
};
dfs(0);
return ans;
}
};Java
import java.util.*;
class Solution {
int n, ans;
boolean[] cols, d1, d2;
public int totalNQueens(int n) {
this.n = n; ans = 0;
cols = new boolean[n]; d1 = new boolean[2 * n]; d2 = new boolean[2 * n];
dfs(0);
return ans;
}
private void dfs(int r) {
if (r == n) { ans++; return; }
for (int c = 0; c < n; c++) {
if (cols[c] || d1[r - c + n] || d2[r + c]) continue;
cols[c] = d1[r - c + n] = d2[r + c] = true;
dfs(r + 1);
cols[c] = d1[r - c + n] = d2[r + c] = false;
}
}
}复杂度
时间
O(n!)
第 0 行有 n 个候选列,第 1 行最多 n-1 个(同列被挡),依次递减,搜索树规模约 n!;每个结点判冲突 O(1)
空间
O(n)
递归深度最多 n 层;cols/d1/d2 三个集合各最多存 n 个元素,均为 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 N 皇后 II 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
N 皇后 I 要返回所有具体棋盘,和这道 II 题(只数数量)在实现上差在哪?+
搜索框架完全一样,都是逐行回溯。区别只在「到底行那一刻」:I 题要把当前 placed 数组翻译成 ". Q . ." 形式的棋盘字符串存进结果列表;II 题只把计数器加一即可,不必拼棋盘、更省内存。其余冲突判断、落子、回溯逻辑一模一样。
还能怎么进一步加速?+
经典优化有两类:一是位运算,用三个整数的二进制位分别表示列、主对角、副对角的占用情况,取可用位、lowbit 逐个枚举,常数极小,能算到较大的 n;二是对称性剪枝,第一行只枚举左半边,结果翻倍(n 为奇数时单独处理正中列),大约省一半搜索。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 N 皇后 II 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。