刷过LeetCode的读者对第51题N皇后肯定不陌生输出棋盘布局的回溯解法几乎是每个算法学习者的入门必修课。但紧接着的第52题N皇后II很多人只是把它当成同一道题的简化版——只要把保存结果的代码删掉、改成计数器加一就行于是草草收场。真正把这题细细拆过一遍之后我发现这个只统计方案数量的改动远不是删代码那么简单。它意味着搜索树不再需要维护路径可以引入更激进的剪枝也意味着我们可以用更紧凑的状态表示去压榨运行时间甚至把N推到远超题目约束的范围。这篇文章不打算只给一份能AC的代码而是想把从朴素回溯到位运算、再到对称剪枝的完整演进过程讲透。每个阶段为什么要这样改、改完能带来什么、有哪些容易踩的坑都尽量交代清楚。无论你是刚开始刷题的新手还是准备面试想讲出层次感的候选人应该都能从中挖到点东西。1. 先说清楚N皇后II和N皇后I差的不仅是计数很多人的第一反应是N皇后I要返回所有解N皇后II只返回解的个数那直接把N皇后I的代码拿过来把收集结果的逻辑换成一个count 1不就行了逻辑上确实没错但这就等于把一个明明可以更轻量的问题硬生生背上了输出所有解的重担。1.1 题目约束与返回类型一次简化带来的自由度先看两个题目的差异点我把它们放在一起对比对比项N皇后ILeetCode 51N皇后IILeetCode 52返回内容所有合法棋盘的字符串数组合法方案的数量int是否必须保留路径必须最终要还原棋盘不需要只需在叶子节点计数可行剪枝手段只剪不可行分支可在剪枝基础上叠加对称性去重n的最大约束1到91到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 三个判重数组的下标设计为什么是rowcol和row-coln-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) * ...这正是阶乘的形态。在n9时这个版本在现代CPU上是毫秒级响应直接提交LeetCode没有任何问题。但如果你把它丢到n14体验就会变得很难看递归节点数涨到千万甚至上亿级别耗时可能要好几十秒。我通常把这个版本当作基线版本所有优化都以它为参照物来衡量收益。这里有个小经验写回溯时把冲突判断放在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在row1时col应为-1超出棋盘在row2时col为-2也超出。所以其实这条对角线根本影响不到下一行。从(0,0)出发的左上到右下对角线row - col 0在row1时col1所以下一行第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)这个版本在n9时耗时比三数组版快一个量级而且代码更短。如果你用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的地方我第一次写时把奇数情况也直接乘2n5的答案从10变成了16debug了很久才发现中心列被重复计算了。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时生效递归过程中不再使用。实际上这个掩码从头到尾只需要在第一行起作用所以你也可以通过拆两个函数来做但我个人觉得传参的方式更通用后续想扩展下界剪枝也方便。实测下来这个版本在n9时耗时是纯位运算版的一半左右搜索节点数大约稳定减少45%到55%属于白捡的性能。5. 继续突破更大N、更紧的状态与并行化思路LeetCode的约束停在n9但如果你真正对N皇后问题产生兴趣迟早会想把N往14、16、18甚至20推。这时候单纯靠位运算已经不够了需要引入更多思路。5.1 从n9到n16瓶颈在哪n9时解的总数是352搜索节点数在万级别毫秒级出结果。n14时解的总数是365596但搜索节点数会膨胀到千万甚至上亿纯Python跑起来非常吃力C也得抠常数。瓶颈其实有两层第一是递归调用次数爆炸第二是每次递归的状态更新虽然快但调用次数太多常数再低也扛不住指数级增长。这时候单纯靠代码微优化已经收效甚微必须砍搜索树本身。有一类做法是动态选择下一行而不是固定按row顺序递归。这个思路叫最小剩余值启发式MRV每层递归都从当前可选列数最少的行开始放。N皇后问题中如果你固定按行放本质上每一行的剩余可选位置都差不多MRV效果不明显但如果你允许跳行选择先放那些被限制最死的行可以更早剪掉大块搜索空间。实现复杂度高一些但配合位运算状态可以做到。5.2 三条已验证的提速路线真正能在大N上拉开差距的我实际验证过的主要有三条。第一是轨道对称归约。棋盘在旋转90度、180度、270度以及镜像这8种操作下会形成等价类一个解在群作用下会有若干等价版本。搜索时只枚举每个等价类的一个代表最后按轨道大小加权累加。这个思路能比左右镜像剪枝节省更多但实现复杂边界条件多适合想挑战极限的人。LeetCode的n9完全用不上这个。第二是多线程并行。N皇后搜索天然可并行第一行的每一种放置都会生成一棵完全独立的搜索子树。把这些子树分配到不同线程各自递归计数最后汇总即可。配合左右镜像剪枝实际上只需要派发n/2个任务。主要难点是任务负载不均衡——有的子树很早就死掉了有的子树会长出很多解需要引入简单的任务队列做动态调度而不是傻乎乎地平均分。第三是用C重写核心递归并把递归拆成显式栈的循环版本。显式栈能避开函数调用开销但对N皇后这种深度只有n的递归收益其实不大。真正有价值的是把dfs变成非递归后可以在更深层做更多精细剪枝比如检查剩余行能否放得下剩余皇后。这个检查听起来很玄乎实际就是算一算当前还能放的位置数量是否小于剩余皇后数如果小于就直接回溯。很朴素的剪枝但在一些卡边界的情况下能救急。把这三个方向组合起来N16在C多线程版本下能做到秒级左右N20仍然需要分钟级甚至更久。N皇后问题至今没有一个多项式解法也没有闭式公式大规模计算本身就是一个颇具挑战性的搜索优化课题。6. 调试、边界与面试实战一些过来人经验代码写出来是一回事能一次写对是另一回事。N皇后II虽然短但有些错误特别隐蔽没有充分验证的话你甚至可能拿一个错误的答案还自我感觉良好。6.1 用标准答案表快速验证实现N皇后问题前几项的标准答案是所有实现都必须通过的基本测试n解的数量11203042510647408929352我自己每次写完新版本第一件事就是跑这张表。尤其是n6到n5之间数量从10掉到4这个反直觉下跌能很好地检验你是否把某些非法解也放进去了。如果你发现n6输出的是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那一下的快乐它练的是你在约束下找规律、压冗余的直觉这种东西只要练进去了走到哪里都用得上。