LeetCode 52. N 皇后 II
目录
题目描述
题意分析
给定整数
n，在n × n的棋盘上放n个皇后，使它们两两不能互相攻击，返回不同摆法的数量。与 51 题不同，这里只要计数，不需要把棋盘还原出来。皇后的攻击范围是所在的行、列以及两条对角线。「
n个皇后放进n行且同行不能有两个」直接推出一个强约束：每一行恰好放一个皇后，一个不多一个不少。这把二维的「在棋盘上选n个格子」压缩成一维的「给每一行选一个列号」，搜索层数确定为n，行冲突自动消失。于是冲突判定只剩三类：列相同、主对角线相同（行列之差相等）、副对角线相同（行列之和相等）。这三类都是「某个编号是否已被占用」的集合成员判断，只需要查询和插入、不需要顺序，正是位集合最擅长的场景。
数据规模
1 <= n <= 9小得反常，这本身就是信号：答案没有多项式公式（n = 9时是352），必须把每个摆法枚举出来；同时一行的占用状态可以完整塞进一个int的低n位里。边界：
n = 1答案为1；n = 2与n = 3无解，答案为0。好的实现应该让这几种情况从主逻辑里自然落出来，不需要任何特判。
解法：位运算回溯
核心思路
朴素做法是逐行枚举列号，对每个候选位置回头扫描前面已放的所有皇后，检查列与对角线是否冲突，单次检查 $O(n)$。用三个布尔数组（
col[]、diag1[]、diag2[]）把检查降到 $O(1)$ 是第一步优化，但每层仍要遍历n个列号、逐个查表，绝大多数候选都会被否掉，这些遍历纯属浪费。于是问题变成：能不能一次性算出当前行所有合法的位置？把三个布尔数组换成三个整数的二进制位就可以——占用信息按位取并集，一条指令搞定。
状态定义：用
int的第j位（从低位起）表示第j列，三个参数含义如下。
columns：第j位为1表示第j列已被前面某个皇后占用。diagonals1：第j位为1表示当前行的第j列被某条「左上到右下」方向的对角线封锁。diagonals2：第j位为1表示当前行的第j列被某条「右上到左下」方向的对角线封锁。关键在于对角线状态如何随行推进。传统写法要给每条对角线单独编号（
row - col + n与row + col），共2n - 1条，管理起来啰嗦。这里换个视角：对角线的封锁位置随行号增加而平移。若某皇后在第r行第c列，它的主对角线在第r + 1行封锁第c + 1列、第r + 2行封锁第c + 2列，也就是每下一行封锁位向高位挪一格，恰好是<< 1；副对角线则每行向低位挪一格，恰好是>> 1。所以递归传参时写(diagonals1 | position) << 1与(diagonals2 | position) >> 1，对角线状态就自动完成了「随行平移」，不需要任何编号数组，也不需要显式撤销。有了三个集合，当前行的合法位置就是
available = mask & ~(columns | diagonals1 | diagonals2)，其中mask = (1 << n) - 1是低n位全为1的棋盘边界。并集是全部被封锁的列，取反得到未被封锁的列，再与mask相与，是为了抹掉取反产生的高位1——那些位对应棋盘外的列；同时左移也会把封锁位挤到棋盘外，必须靠mask统一裁掉，否则垃圾位会一路累积。逐个取出候选用
position = available & -available，这是补码的经典技巧：-available等于按位取反再加一，与原值相与只保留最低位的那个1。取完用available -= position移除它，循环到available为0，本行所有合法列就遍历完了。不变量：进入
backtrack(row, columns, diagonals1, diagonals2)时，第0到row - 1行各放了一个互不攻击的皇后，且三个参数已经把它们对第row行的全部封锁效果折算完毕。函数返回值是「在此局面下把剩余n - row行放完的方案数」。因此row == n说明n个皇后全部合法落子，本身就是一个完整方案，返回1；把各分支返回值累加即为总数。
解题步骤
- 构造边界掩码：
mask = (1 << n) - 1，低n位全为1，代表棋盘只有n列。它每一层都把移位溢出到棋盘外的封锁位裁掉，是这套位运算写法能成立的前提。- 从第
0行、三个空集合开始递归：初始columns = diagonals1 = diagonals2 = 0，表示尚未占用任何位置。- 递归出口：
row == n返回1。走到这里说明前n行都合法放置了皇后，即凑出一个完整方案；返回1而不是true，是因为上层要做累加而非短路。- 计算可用位置：
available = mask & ~(columns | diagonals1 | diagonals2)。available == 0时下面的循环体一次都不进，直接返回0，天然表达了「本行无处可放，此分支作废」，不必写额外的失败判断。- 逐位取出候选：
position = available & -available取最低位的1；available -= position把它从候选集中移除。这里用减法而非异或只是写法差异，因为该位确定为1，效果一致。- 递归下一行：
columns | position让该列永久占用；(diagonals1 | position) << 1与(diagonals2 | position) >> 1先把新皇后并入对角线集合、再整体移位，顺序不能颠倒——先移位后取并会漏掉当前这个皇后自己的对角线影响。- 累加返回值：
count += backtrack(...)。注意全程没有「撤销选择」的语句，因为所有状态都通过参数按值传递，子调用改不到上层的局部变量，回溯是自动完成的。- 返回
count，把本层所有分支的方案数汇总给上层。以
n = 4走一遍（mask = 0b1111，已知答案为2）。第 0 行：三个集合全为
0，available = 0b1111，四列都可放，从最低位开始逐个尝试。
取第 0 列（position = 0b0001）：传下去columns = 0b0001、diagonals1 = 0b0001 << 1 = 0b0010、diagonals2 = 0b0001 >> 1 = 0b0000。第 1 行封锁集为0b0011，available = 0b1100，即第 2、3 列。先试第 2 列，得到第 2 行的封锁集0b0101 | 0b1100 | 0b0010 = 0b1111，available = 0，返回0；改试第 3 列，第 2 行的diagonals1 = 0b10100，其中第 4 位已溢出棋盘，正是被mask裁掉的那一位，最终available = 0b0010只剩第 1 列，放下后第 3 行available = 0，仍返回0。所以第 0 行放第 0 列的整棵子树颗粒无收。
取第 1 列（position = 0b0010）：传下去columns = 0b0010、diagonals1 = 0b0100、diagonals2 = 0b0001。第 1 行封锁集为0b0111，available = 0b1000，只能放第 3 列。放下后第 2 行columns = 0b1010、diagonals1 = 0b11000、diagonals2 = 0b0100，available = 0b0001，只能放第 0 列。再放下后第 3 行columns = 0b1011、diagonals1 = 0b110010、diagonals2 = 0b0010，available = 0b0100，只能放第 2 列。放下后row == 4，返回1。这条路径对应摆法「各行依次放在第 1、3、0、2 列」。
取第 2 列：与上一条完全镜像，得到摆法「第 2、0、3、1 列」，返回1。
取第 3 列：与第 0 列镜像，同样一无所获，返回0。
四个分支累加得0 + 1 + 1 + 0 = 2，与n = 4的正确答案一致。顺带看边界：
n = 1时第 0 行available = 0b1，放下即row == 1，返回1；n = 2时无论第 0 行放哪一列，第 1 行的available都为0，两条分支各返回0，总和为0。两者都无需特判。
代码实现
class Solution {
public int totalNQueens(int n) {
return backtrack(n, 0, 0, 0, 0);
}
private int backtrack(int n, int row, int columns, int diagonals1, int diagonals2) {
if (row == n) {
return 1;
}
int mask = (1 << n) - 1;
int available = mask & ~(columns | diagonals1 | diagonals2);
int count = 0;
while (available != 0) {
int position = available & -available;
available -= position;
count += backtrack(n, row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1);
}
return count;
}
}
func totalNQueens(n int) int {
var backtrack func(int, int, int, int) int
backtrack = func(row int, columns int, diagonals1 int, diagonals2 int) int {
if row == n {
return 1
}
mask := (1 << n) - 1
available := mask & ^(columns | diagonals1 | diagonals2)
count := 0
for available != 0 {
position := available & -available
available -= position
count += backtrack(row+1, columns|position, (diagonals1|position)<<1, (diagonals2|position)>>1)
}
return count
}
return backtrack(0, 0, 0, 0)
}
复杂度分析
- 时间复杂度：$O(n!)$ 级别。第 0 行有
n个候选，第 1 行至多n - 2个（本列与两条对角线各封掉至少一个），越往下候选越少，搜索树节点数被n!上界卡住。位运算不改变这个量级，但把「每层枚举n列并三次查表」压成几条按位指令，常数极小。- 空间复杂度：$O(n)$，递归深度等于行数
n，每层只有mask、available、position、count这几个int。三个状态集合是按值传递的整数而非数组，没有额外的 $O(n)$ 结构，这是位运算写法相对布尔数组写法的额外收益。
关键点总结
- 把二维搜索降成一维决策：识别出「每行必放且只放一个」，是这道题从「在棋盘上选格子」变成「给每行选列号」的转折点，也是所有棋盘类回溯题的第一步。
- 状态压缩的判断标准：当状态是「一组不超过 64 个元素的占用标记」且只做并集、取反、取最低位这类操作时，位集合几乎总是优于布尔数组。
n <= 9这样的小上界就是出题人在提示可以压缩。- 移位表达对角线随行平移，免去了
2n - 1条对角线的编号映射，也免去了显式撤销——代价是必须用mask裁掉溢出位。这个技巧能整套搬到数独、骑士巡游等棋盘题上。- 参数按值传递即天然回溯：状态放在参数里而不是成员变量或数组里，就没有「忘记恢复现场」的风险，白板上写更不容易出错。
x & -x取最低位1，x -= x & -x消最低位1，这对组合是位运算枚举子集/候选集的基本功，同样用于树状数组和状压 DP。- 面试视角：先说清「逐行放置 + 三集合冲突判定」的朴素回溯，写出来后再主动提出位运算优化并解释
<< 1/>> 1的几何含义，是本题的加分路径。若面试官问「n更大怎么办」，可答：n到15以上时可加对称性剪枝（第一行只枚举一半列，答案翻倍并单独处理正中列），但复杂度量级不变，本质上无多项式解。
易错点总结
- 递归时先移位再取并：写成
(diagonals1 << 1) | position，当前行这个皇后的对角线影响没有跟着平移，下一行会把它封锁在同一列而不是斜方向，n = 4得8、n = 8得1686，全部偏大。- 对角线忘记移位：直接传
diagonals1 | position，两个对角线集合退化成「列占用的副本」，只剩列约束，n = 4返回24（即4!）而不是2。mask写成1 << n而不是(1 << n) - 1：可用位只剩棋盘外的第n位，第 0 行放到界外、第 1 行就无位可放，任何n都返回0。- 漏掉
mask：写成available = ~(columns | diagonals1 | diagonals2)，取反后的高位全是1，会被当成棋盘外的合法列继续放皇后，n = 4直接跑出天文数字甚至栈溢出。- 取最低位写成
available & (available - 1)：这是「消掉」最低位而不是「取出」最低位，position会带上一堆无关的高位，n = 4得到97029900这种彻底错乱的结果。- 忘记
available -= position：候选集永远不减少，while循环在第一列上无限重复，直接死循环。- 递归出口返回
true/0而不是1：出口返回0会让所有方案都被计成0，n = 8输出0而不是92。- 把 52 题当成 51 题写：额外维护棋盘字符串数组并返回方案列表，
n = 9时内存与耗时都成倍上升，本题只需要一个计数器。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 51. N 皇后 | 困难 | 同一套搜索，但要还原棋盘，必须额外记录每行的列号并拼出字符串 |
| 面试题 08.12. 八皇后 | 困难 | 与 51 同题，输出格式略有差异，可直接套用本题骨架 |
| 37. 解数独 | 困难 | 同为「填格子 + 冲突集合」，约束来自行列宫三重，且需就地改写棋盘 |
| 79. 单词搜索 | 中等 | 网格上的回溯，状态是访问标记而非位集合，必须显式撤销 |
| 46. 全排列 | 中等 | 只有列约束、没有对角线约束，本题去掉两个对角线集合就退化成它 |
| 78. 子集 | 中等 | 每个元素二选一的无约束枚举，用来对照理解冲突剪枝带来的收益 |
| 473. 火柴拼正方形 | 中等 | 同为可行性搜索，剪枝靠「超出目标值」与「同构分支只试一次」 |
| 698. 划分为k个相等的子集 | 中等 | 分组型回溯，n 较小时同样可用位掩码压缩已选集合 |
| 191. 位1的个数 | 简单 | 专练 x & -x 与 x & (x - 1) 这两个位技巧的差别 |