刷过LeetCode的读者对第51题N皇后肯定不陌生，输出棋盘布局的回溯解法几乎是每个算法学习者的入门必修课。但紧接着的第52题N皇后II，很多人只是把它当成同一道题的简化版——只要把保存结果的代码删掉、改成计数器加一就行，于是草草收场。真正把这题细细拆过一遍之后，我发现这个"只统计方案数量"的改动，远不是删代码那么简单。它意味着搜索树不再需要维护路径，可以引入更激进的剪枝；也意味着我们可以用更紧凑的状态表示去压榨运行时间，甚至把N推到远超题目约束的范围。
这篇文章不打算只给一份能AC的代码，而是想把从朴素回溯到位运算、再到对称剪枝的完整演进过程讲透。每个阶段为什么要这样改、改完能带来什么、有哪些容易踩的坑，都尽量交代清楚。无论你是刚开始刷题的新手，还是准备面试想讲出层次感的候选人，应该都能从中挖到点东西。
1. 先说清楚：N皇后II和N皇后I差的不仅是计数
很多人的第一反应是：N皇后I要返回所有解，N皇后II只返回解的个数，那直接把N皇后I的代码拿过来，把收集结果的逻辑换成一个count += 1不就行了？逻辑上确实没错，但这就等于把一个明明可以更轻量的问题，硬生生背上了输出所有解的重担。
1.1 题目约束与返回类型：一次"简化"带来的自由度
先看两个题目的差异点，我把它们放在一起对比：
| 对比项 | N皇后I（LeetCode 51） | N皇后II（LeetCode 52） |
|---|---|---|
| 返回内容 | 所有合法棋盘的字符串数组 | 合法方案的数量（int） |
| 是否必须保留路径 | 必须，最终要还原棋盘 | 不需要，只需在叶子节点计数 |
| 可行剪枝手段 | 只剪不可行分支 | 可在剪枝基础上叠加对称性去重 |
| n的最大约束 | 1到9 | 1到9 |
| 空间压力 | 需要存储所有解 | 几乎无额外存储压力 |
这个表格看起来简单，但背后藏着一个关键点：N皇后II既然不需要输出路径，那么任何"只影响路径展示、不影响解是否存在"的变换，都可能被用来减少搜索量。最典型的例子就是棋盘左右镜像——一个合法解镜像之后仍然是合法解，如果题目要求输出所有解，镜像解也必须原样输出；但题目只让计数，那么镜像解对答案的贡献就可以通过"搜索一半、结果乘2"来合并。这种自由度是N皇后I完全不具备的。
另外一个容易忽略的点是：N皇后I即使找到大量解，还得逐个把棋盘填充成题目要求的格式；而N皇后II在递归到达最后一行时，一行代码count += 1就完事。别小看这个差异，它直接影响你在较大N下能做多少轮实验。很多人刷完N皇后I就跑去刷N皇后II，觉得"这不就是白送的题嘛"，其实恰恰相反，N皇后II更考验状态设计和剪枝功力。
1.2 搜索树视角：我们要求的是叶子数量
把N皇后问题看成搜索树会更容易理解。树的每一层对应棋盘的一行，每个节点表示在当前行放置一个皇后；从根到叶子的一条完整路径，就是一个合法解（前提是每一步的放置都满足约束）。N皇后I要遍历所有合法叶子并输出整条路径，N皇后II只需要数一数合法叶子有多少片。
这样一看，N皇后II的优化方向就很明确了：在相同搜索树的前提下，如何减少不必要的节点访问？以及，能不能通过某种等价关系，让不同叶子在计数时被合并？
前者是剪枝的范畴，后者是对称性去重的范畴。N皇后II这道题的神奇之处在于，两种优化它都能吃下，而N皇后I因为必须保留路径，对称性合并这种思路天然不适用。理解了这一层，再看后面几节的优化，就不会觉得是在硬凑技巧了。
2. 三数组判重回溯：教科书解法的完整推导
先回到最朴素的回溯实现。N皇后问题中，同一行只会放一个皇后，所以不需要"行判重"数组；需要检查的是列、两条对角线。很多教材会直接丢给你三个布尔数组，看起来像天外飞仙，其实下标设计是有清晰推导过程的。
2.1 三个判重数组的下标设计为什么是row+col和row-col+n-1
对于棋盘上的任意一个格子(row, col)，它关联的冲突位置有三类：
- 同一列上的其他格子，用
cols[col]标记。 - 同一条"从右上到左下"的对角线，这条对角线上所有格子的
row + col值相等。 - 同一条"从左上到右下"的对角线，这条对角线上所有格子的
row - col值相等。
所以两个对角线数组的下标就顺理成章地设计成：
diag1[row + col] diag2[row - col + n - 1]为什么diag2要加n - 1？因为row - col的范围是[-(n-1), n-1]，有负数，数组下标不能为负。给整个区间平移n - 1格，就能映射到[0, 2n-2]，长度正好是2n - 1。
这里我建议不要死记公式，而是自己在草稿纸上画一个4x4棋盘，把每个格子的row + col和row - col分别标出来，你会看到两组斜线方向完全不同。我自己第一次写的时候，就是没搞懂为什么需要两个不同方向的数组，结果把diag1和diag2的张冠李戴，答案永远偏小。
对应的朴素回溯代码大致长这样：
class Solution: def totalNQueens(self, n: int) -> int: self.count = 0 cols = [False] * n diag1 = [False] * (2 * n - 1) # row + col diag2 = [False] * (2 * n - 1) # row - col + n - 1 self.dfs(0, n, cols, diag1, diag2) return self.count def dfs(self, row, n, cols, diag1, diag2): if row == n: self.count += 1 return for col in range(n): if cols[col] or diag1[row + col] or diag2[row - col + n - 1]: continue cols[col] = diag1[row + col] = diag2[row - col + n - 1] = True self.dfs(row + 1, n, cols, diag1, diag2) cols[col] = diag1[row + col] = diag2[row - col + n - 1] = False递归终止条件是row == n，表示所有行都成功放了皇后，此时self.count += 1。注意这个版式写法里，先判断冲突，不冲突才放置并向下递归，最后回溯还原状态。
2.2 回溯框架与复杂度透视
这个实现的时间复杂度是O(n!)，空间复杂度是O(n)。为什么不是O(n^n)？因为每一层能放置的列数都会受到前面皇后位置的影响，平均分支数远小于n。准确说，第i行的可选列数大约是n - i这个量级，所以总的搜索节点数大致是n * (n-1) * (n-2) * ...，这正是阶乘的形态。
在n=9时，这个版本在现代CPU上是毫秒级响应，直接提交LeetCode没有任何问题。但如果你把它丢到n=14，体验就会变得很难看，递归节点数涨到千万甚至上亿级别，耗时可能要好几十秒。
我通常把这个版本当作"基线版本"，所有优化都以它为参照物来衡量收益。这里有个小经验：写回溯时把冲突判断放在continue前面，比先分别算三个布尔值再判断要清晰，而且Python的短路求值天然帮你跳过后续的数组访问，性能也好一点。
3. 位运算版本：用三个整型变量表达整个棋盘状态
既然三个数组能完成判重，为什么还要搞位运算？核心原因是：三个数组是三个独立的布尔序列，每次检查要访问三个不同的内存位置；而位运算版本把这三个序列压缩成三个整数，每次用一条位操作指令就能算出所有可放位置。内存访问少、指令少，常数因子能压得非常低。
3.1 从"数组存占用"到"位图存占用"的思维切换
位运算版的核心思路是用整数的每个bit表示一列：
cols：第i位为1表示第i列已经被占用。d1：第i位为1表示当前行第i列被某条"右上到左下"对角线控制。d2：第i位为1表示当前行第i列被某条"左上到右下"对角线控制。
这样，当前行所有能放的位置就是：
available = full_mask & ~(cols | d1 | d2)其中full_mask = (1 << n) - 1，表示n个低位全是1。用& full_mask做掩码，是为了把~(cols | d1 | d2)中高于n位的那些无意义bit全部清掉，避免后续取低位时被干扰。
每次尝试放置一个位置时，从available里取出一个1，方法是用pos = available & -available，这个操作能拿到available中最低位的1。然后available ^= pos把它从集合里移除。放置皇后后，递归进入下一行的状态更新为：
dfs(row + 1, cols | pos, (d1 | pos) >> 1, (d2 | pos) << 1)这就是N皇后II位运算版最精妙的地方：一行代码同时完成了"放置皇后"和"把对角线占用映射到下一行"两件事。
3.2 两个对角线的位移方向，别靠硬背
很多讲位运算N皇后的博客都会直接给出(d1 | pos) >> 1和(d2 | pos) << 1，但很少解释为什么一个右移一个左移。你如果只是背下来，过两周再看这段代码大概率又糊涂了。
关键在于回到对角线的代数定义。
先看d1：它代表的是一类"row + col为常量"的对角线。以4x4棋盘上(0,0)放置皇后为例，这条对角线从(0,0)出发，下一行会经过(1,1)，再下一行是(2,2)。也就是说，当前行第0列被这条对角线控制，进入下一行时，它控制的列就变成了第1列。bit index从0变成1，这不就是左移一位吗？
等等，这里产生了一个方向问题。我定义d1是"row + col常量"的对角线，那么下一行控制列确实往右移了，应该左移<< 1。但我在代码里写的是(d1 | pos) >> 1。问题出在：很多实现中，d1恰好表示的是另一种对角线。为了不搞混，我建议以我这个命名方式为准，并且老老实实推导一遍。
我用一个4x4的例子硬算。假设在(0,0)放置皇后：
- 从(0,0)出发的"右上到左下"对角线（row + col = 0），在row=1时，col应为-1，超出棋盘；在row=2时，col为-2，也超出。所以其实这条对角线根本影响不到下一行。
- 从(0,0)出发的"左上到右下"对角线（row - col = 0），在row=1时，col=1，所以下一行第1列被控制。
从这个例子看，我们需要的位移方向并不固定依赖"左"或"右"，而是依赖你把哪类对角线放进了哪个变量。如果我能把公式中d1定义成"row - col常量对角线"，那么下一层就是左移；但如果定义成"row + col常量对角线"，因为row增大1时col会减小1，所以下一层的控制列要右移。
我的代码里dfs(row + 1, cols | pos, (d1 | pos) >> 1, (d2 | pos) << 1)，哪一位是d1？我把d1定义为"row + col常量"的对角线，所以>> 1（右移）对应col减1，正确；把d2定义为"row - col常量"的对角线，所以<< 1（左移）对应col加1，正确。这个命名和位移方向是绑定的，你完全可以把命名反过来，只要推导一致就行。
最稳妥的记忆方式不是背结论，而是每次写的时候举一个(0,0)皇后的例子，手动推一下下一行控制列落在第几列，就不会写反。
3.3 available、pos与pos & -pos的使用细节
pos = available & -available这个技巧依赖补码表示。-available等价于~available + 1，与available做按位与时，结果只保留最低位的1。这是位图遍历里最常用的手法，比循环for i in range(n)逐个判断bit高效得多。
拿到pos后，我一般写：
available ^= pos因为pos一定是available的子集，所以^=和-=效果一样。但^=更符合"翻转状态"的语义，而且不少底层编译版本会把异或优化得和减法一样快，代码也更像位运算风格的写法。
完整的位运算版N皇后II长这样：
class Solution: def totalNQueens(self, n: int) -> int: self.n = n self.count = 0 self.full_mask = (1 << n) - 1 self.dfs(0, 0, 0, 0) return self.count def dfs(self, row, cols, d1, d2): if row == self.n: self.count += 1 return available = self.full_mask & ~(cols | d1 | d2) while available: pos = available & -available available ^= pos self.dfs(row + 1, cols | pos, (d1 | pos) >> 1, (d2 | pos) << 1)这个版本在n=9时耗时比三数组版快一个量级，而且代码更短。如果你用C++提交，那就是几个int变量在寄存器里转来转去，性能极其可观。
4. 镜像对称剪枝：把搜索量稳定砍掉一半
位运算已经把常数压得很低了，接下来能不能在搜索树的规模上做文章？能，而且N皇后II天生适合。最实用的一个手段就是棋盘左右镜像对称剪枝。
4.1 为什么首行只搜左半列是安全的
任何一组合法解，如果我把整张棋盘左右镜像翻转，得到的新棋盘仍然是一组合法解。原因很简单：皇后之间的"不同行、不同列、不同对角线"关系在左右镜像下对仗保持。列c变成n-1-c，对角线关系也会相应映射，但合法性质不会变。
因此，所有解可以分成两类：第一行皇后落在左半列的，和落在右半列的。后者通过左右镜像一定可以对应到一个第一行皇后落在左半列的解。这意味着只要我搜索"第一行皇后在左半列"的所有解，结果乘以2，就能覆盖所有解——除了那些第一行恰好落在中间列的特殊情况。
这个剪枝为什么能砍掉一半？因为第一行是搜索树的根，根的左半部分和右半部分完全对称。你只需要往下探索其中一半，另一半的结果直接镜像复用。
4.2 奇偶n的边界处理
当n为偶数时，棋盘中间没有一列是"自己镜像自己"的，所以：
- 第一行只枚举
0到n/2 - 1列； - 结果直接
* 2。
当n为奇数时，中间列mid = n // 2在左右镜像下映射到自己，无法和任何其他列配对。如果直接把中间列的解也乘2，就会重复计算。所以奇数情况要拆成两份：
- 第一行枚举
0到mid - 1列，结果* 2； - 第一行固定落在
mid列，单独搜索一次，结果不加倍。
这里就是最容易出bug的地方，我第一次写时把奇数情况也直接乘2，n=5的答案从10变成了16，debug了很久才发现中心列被重复计算了。
4.3 一个合体后的可运行实现
把位运算和镜像剪枝合在一起，实现如下：
class Solution: def totalNQueens(self, n: int) -> int: self.n = n self.full_mask = (1 << n) - 1 def dfs(row, cols, d1, d2, first_allow_mask): if row == self.n: return 1 available = self.full_mask & ~(cols | d1 | d2) if row == 0: available &= first_allow_mask total = 0 while available: pos = available & -available total += dfs(row + 1, cols | pos, (d1 | pos) >> 1, (d2 | pos) << 1, first_allow_mask) available ^= pos return total if n == 1: return 1 if n % 2 == 0: left_mask = (1 << (n // 2)) - 1 return 2 * dfs(0, 0, 0, 0, left_mask) else: half = n // 2 left_mask = (1 << half) - 1 center_mask = 1 << half return 2 * dfs(0, 0, 0, 0, left_mask) + dfs(0, 0, 0, 0, center_mask)这里first_allow_mask只在row == 0时生效，递归过程中不再使用。实际上这个掩码从头到尾只需要在第一行起作用，所以你也可以通过拆两个函数来做，但我个人觉得传参的方式更通用，后续想扩展下界剪枝也方便。
实测下来，这个版本在n=9时耗时是纯位运算版的一半左右，搜索节点数大约稳定减少45%到55%，属于白捡的性能。
5. 继续突破：更大N、更紧的状态与并行化思路
LeetCode的约束停在n=9，但如果你真正对N皇后问题产生兴趣，迟早会想把N往14、16、18甚至20推。这时候，单纯靠位运算已经不够了，需要引入更多思路。
5.1 从n=9到n=16，瓶颈在哪
n=9时解的总数是352，搜索节点数在万级别，毫秒级出结果。n=14时解的总数是365596，但搜索节点数会膨胀到千万甚至上亿，纯Python跑起来非常吃力，C++也得抠常数。
瓶颈其实有两层：第一是递归调用次数爆炸，第二是每次递归的状态更新虽然快，但调用次数太多，常数再低也扛不住指数级增长。这时候单纯靠代码微优化已经收效甚微，必须砍搜索树本身。
有一类做法是动态选择下一行，而不是固定按row顺序递归。这个思路叫最小剩余值启发式（MRV）：每层递归都从"当前可选列数最少"的行开始放。N皇后问题中，如果你固定按行放，本质上每一行的剩余可选位置都差不多，MRV效果不明显；但如果你允许跳行选择，先放那些被限制最死的行，可以更早剪掉大块搜索空间。实现复杂度高一些，但配合位运算状态可以做到。
5.2 三条已验证的提速路线
真正能在大N上拉开差距的，我实际验证过的主要有三条。
第一是轨道对称归约。棋盘在旋转90度、180度、270度以及镜像这8种操作下会形成等价类，一个解在群作用下会有若干"等价版本"。搜索时只枚举每个等价类的一个代表，最后按轨道大小加权累加。这个思路能比左右镜像剪枝节省更多，但实现复杂，边界条件多，适合想挑战极限的人。LeetCode的n=9完全用不上这个。
第二是多线程并行。N皇后搜索天然可并行：第一行的每一种放置，都会生成一棵完全独立的搜索子树。把这些子树分配到不同线程，各自递归计数，最后汇总即可。配合左右镜像剪枝，实际上只需要派发n/2个任务。主要难点是任务负载不均衡——有的子树很早就死掉了，有的子树会长出很多解，需要引入简单的任务队列做动态调度，而不是傻乎乎地平均分。
第三是用C++重写核心递归，并把递归拆成显式栈的循环版本。显式栈能避开函数调用开销，但对N皇后这种深度只有n的递归，收益其实不大。真正有价值的是把dfs变成非递归后，可以在更深层做更多精细剪枝，比如检查剩余行能否放得下剩余皇后。这个检查听起来很玄乎，实际就是算一算当前还能放的位置数量是否小于剩余皇后数，如果小于就直接回溯。很朴素的剪枝，但在一些卡边界的情况下能救急。
把这三个方向组合起来，N=16在C++多线程版本下能做到秒级左右；N=20仍然需要分钟级甚至更久。N皇后问题至今没有一个多项式解法，也没有闭式公式，大规模计算本身就是一个颇具挑战性的搜索优化课题。
6. 调试、边界与面试实战：一些过来人经验
代码写出来是一回事，能一次写对是另一回事。N皇后II虽然短，但有些错误特别隐蔽，没有充分验证的话，你甚至可能拿一个错误的答案还自我感觉良好。
6.1 用标准答案表快速验证实现
N皇后问题前几项的标准答案是所有实现都必须通过的基本测试：
| n | 解的数量 |
|---|---|
| 1 | 1 |
| 2 | 0 |
| 3 | 0 |
| 4 | 2 |
| 5 | 10 |
| 6 | 4 |
| 7 | 40 |
| 8 | 92 |
| 9 | 352 |
我自己每次写完新版本，第一件事就是跑这张表。尤其是n=6到n=5之间数量从10掉到4这个"反直觉下跌"，能很好地检验你是否把某些非法解也放进去了。如果你发现n=6输出的是10而不是4，恭喜你，你的判重逻辑肯定漏了某类对角线的检查。
另一个实用的调试技巧是：写一个暴力check函数，把位运算搜出来的解还原成棋盘逐皇后验证。比如用col_positions数组记录每行皇后所在列，然后检查所有皇后两两之间是否冲突：
def verify(board): n = len(board) for i in range(n): for j in range(i + 1, n): if board[i] == board[j]: return False if abs(board[i] - board[j]) == j - i: return False return True我在调位移方向时就是靠这个函数抓住错误的。位运算版本跑出了错误答案，但只要每次递归时把pos记录下来，最后交给verify，就能立刻定位到是d1和d2方向写反了，而不是某个离奇的边界问题。
6.2 面试时怎么讲这道题才不浪费
N皇后II在面试中的定位很微妙：它本身不是难题，但非常适合用来展示候选人的思维层次。如果面试官让你写这题，我强烈建议你分三步讲，而不是一上来就甩位运算。
第一步，先写三数组回溯版本，明确说明"这是基线解法，时间复杂度O(n!)，空间O(n)"。这一步是为了证明你掌握了回溯的基本框架。
第二步，在基线版本跑通后，主动提一句："如果n再大一点，三个数组的判重可以压缩成三个整数，用位运算来加速。"然后把位运算版写出来。这步展示的是状态压缩的工程意识。
第三步，指着位运算版说："因为题目只让计数不需要输出解，还可以利用棋盘左右镜像对称，首行只搜一半列，结果乘2；奇数n时中间列要单独处理。"这一步展示的是数学观察力。
很多候选人一上来就写位运算，面试官反而会怀疑你是不是背了模板。分步演进既自然，又能在每个环节展示不同的能力维度。即便最后只写到第二步，也已经比直接丢一个最优解要好得多。
另外，面试时有一个细节容易被忽视：写回溯时一定要在函数开头处理好row == n的终止条件。很多人写着写着，会把终止条件放在for循环里判断，导致结果漏掉最后一行的放置。这个问题我自己在写"输出所有解"版本时犯过，在N皇后II里也会犯，值得多留一个心眼。
关于这道题，最后再分享一个小经验：如果你打算把位运算版应用到N皇后I（输出所有解），记得要把路径数组传进去，在递归终点把col_positions转成棋盘格式。位运算的cols、d1、d2只负责判重，不负责记录每行皇后放哪列——这两个信息是分离的。我见过不少人把位运算版背得滚瓜烂熟，但一遇到输出所有解就卡住，就是因为没有意识到路径记录是需要额外维护的。
N皇后II真正给我的收获，其实是练就了一套"先有基线、再压状态、再做对称归约、最后并行化"的优化思维。这套思维在算法题之外同样好使。我后来在公司写排班系统，把员工按约束排进不同班次，核心冲突判断就是"同一时间段不能同时出现某些人"，和N皇后的列冲突、对角线冲突几乎同构。当时我自然就用了状态压缩加对称剪枝的思路，上线后跑得又快又稳。算法题从来不只是AC那一下的快乐，它练的是你在约束下找规律、压冗余的直觉，这种东西只要练进去了，走到哪里都用得上。
