N皇后II优化指南：回溯剪枝与位运算加速

之前群里有人问我“52题和51题不就是返回结果集的区别吗把数组存起来不就行了” 话是没错但如果你真这么干N15的时候就会明显感觉不对劲——同样的回溯51题能跑52题却慢得让人怀疑人生。原因很简单N皇后 II 不要求你拼出棋盘只问你“有多少种摆法”这种情况下还在老老实实地构造字符串数组、一层层拷贝属于典型的力气没花在刀刃上。LeetCode 52 的完整描述是n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上并且使皇后彼此之间不能相互攻击。给你一个整数 n返回 n 皇后问题不同的解决方案的数量。这题和 51 题N皇后 I共用同一套回溯框架核心区别只有一处51 要收集所有解的棋盘快照52 只需要一个计数器。但这个区别直接决定了优化的方向——你愿不愿意为了一个数字把整个搜索过程做到极致。这篇文章我会带你从最朴素的回溯写法出发逐步优化到位运算版本中间把剪枝原理、对角线推导、复杂度对比、调试技巧一次讲透。适合正在刷回溯专题的算法学习者、准备面试的求职者以及对“如何把递归搜索写得又快又省”感兴趣的工程师。代码以 Python 为主最后会补一段 C 位运算参考实现。1. 问题本质与回溯算法选型1.1 N皇后问题的状态空间长什么样先明确一个基础事实N皇后问题的解空间是 n×n 棋盘上放置 n 个皇后的所有方案暴力枚举是 C(n², n)这个数字膨胀极快。n8 时大约有 4.4 亿种候选组合n12 直接到 9e19 级别暴力肯定是死路一条。但是稍加分析就能缩小搜索范围每行只能放一个皇后每列也只能放一个皇后。既然每行必须且只能有一个皇后那我们就逐行放置每一行只需要在“当前行还没被占用的列”里选一个位置。这样搜索树的每一层对应棋盘的一行每个节点最多 n 个子节点列的选择总节点数上界是 n!第一行 n 种选择第二行最多 n-1 种……。n12 时 n! ≈ 4.8e8虽然依旧不小但配合冲突剪枝实际访问节点数会大幅下降。这就是为什么这道题的标准解法是回溯算法而不是动态规划或贪心。动态规划需要问题具有“最优子结构”但N皇后问的是“所有可行解的数量”本质上是一个计数搜索问题。而回溯正好是深度优先搜索 状态撤销的组合完美契合这种逐行试探的场景。1.2 回溯框架的三个固定动作回溯算法的代码骨架极其固定无论你写的是全排列、组合总和还是N皇后都是这套动作def backtrack(row): if row n: # 找到一个合法解 return for col in range(n): if isValid(row, col): # 做选择 place(row, col) backtrack(row 1) # 撤销选择 remove(row, col)核心逻辑只有三步判断当前位置能否放皇后、放置后进入下一行、递归返回后撤销本次放置。N皇后 II 的所有优化都建立在这三步之上——怎么让“判断能否放”更快怎么让“做选择”的枚举范围更小怎么让“撤销”更干净。这就是为什么我说这题值得写三遍。第一遍用最直观的二维数组判断第二遍用三个一维数组做 O(1) 冲突检测第三遍把数组压缩成整数位掩码。每一遍都对递归搜索的理解深一层。2. 三种冲突检测写法从 O(n) 到 O(1) 再到 O(1) 但更快2.1 二维棋盘逐格判断最直观但最慢最朴素的做法是用一个 n×n 的二维数组 boardisValid 里检查当前点的上方、左上、右上是否有皇后class Solution: def totalNQueens(self, n: int) - int: board [[False] * n for _ in range(n)] self.count 0 def is_valid(row, col): # 检查列 for i in range(row): if board[i][col]: return False # 检查左上对角线 i, j row - 1, col - 1 while i 0 and j 0: if board[i][j]: return False i - 1 j - 1 # 检查右上对角线 i, j row - 1, col 1 while i 0 and j n: if board[i][j]: return False i - 1 j 1 return True def backtrack(row): if row n: self.count 1 return for col in range(n): if is_valid(row, col): board[row][col] True backtrack(row 1) board[row][col] False backtrack(0) return self.count这段代码能 AC但每尝试一个格子都要向上扫描最多 O(n) 个位置三个方向的检查让总复杂度变成 O(n × n × n) 的量级搜索树的节点数 × 每节点判断成本。n 稍大一点比如 n13、14在 LeetCode 上就会濒临超时。问题出在哪每次 isValid 都要“重新观察棋盘”而棋盘上哪些列、哪些对角线已经被占其实在放置皇后的过程中是持续变化的——我们应该把这些信息作为状态直接维护而不是每次临时扫描。2.2 一维数组标记法真正的标准解省掉棋盘数组只维护三个标记数组列占用、主对角线占用、副对角线占用。这里有个新手最容易卡住的点对角线的索引怎么算。看下面这张棋盘坐标示意n4 为例坐标 (row, col): (0,0) (0,1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3) (3,0) (3,1) (3,2) (3,3)主对角线左上到右下同一对角线上所有格子的 row - col 是常数。比如 (0,1)、(1,2)、(2,3)row - col 都等于 -1。范围从 -(n-1) 到 n-1总共 2n-1 条。为了把索引映射到数组统一加偏移量 n-1即idx row - col n - 1。副对角线右上到左下同一对角线上所有格子的 row col 是常数。比如 (0,2)、(1,1)、(2,0)row col 都等于 2。范围从 0 到 2n-2正好 2n-1 条不需要偏移。这个推导过程建议自己手写一遍 4×4 棋盘的坐标比背公式牢靠。写错一次 negative index 的坑你就记住为什么主对角线要加 n-1 了。完整代码如下class Solution: def totalNQueens(self, n: int) - int: cols [False] * n diag1 [False] * (2 * n - 1) # 主对角线 row - col n - 1 diag2 [False] * (2 * n - 1) # 副对角线 row col self.count 0 def backtrack(row): if row n: self.count 1 return for col in range(n): d1 row - col n - 1 d2 row col if cols[col] or diag1[d1] or diag2[d2]: continue cols[col] diag1[d1] diag2[d2] True backtrack(row 1) cols[col] diag1[d1] diag2[d2] False backtrack(0) return self.count三个标记数组的查询和更新都是严格的 O(1)整个算法的主要成本集中在搜索树的节点访问上判断本身被压到了极限。这是 95% 题解给出的写法也是面试时最稳妥的版本——没有位运算那么烧脑但已经足够应对 n ≤ 15 的常见测试范围。2.3 位运算状态压缩把三个数组装进三个整数如果你想追求极致性能或者想在面试里展示一点不一样的思考位运算是必须掌握的版本。思路很简单既然每一列只有“占用/未占用”两种状态一条对角线也只有两种状态那用整数的二进制位来存储不就行了cols的第 i 位表示第 i 列是否被占用diag1的第 i 位表示第 i 条主对角线是否被占用diag2的第 i 位表示第 i 条副对角线是否被占用关键难点在于逐行递归时对角线编号是相对行号变化的。主对角线编号 row - col n - 1副对角线编号 row col。当我们从第 row 行进入第 row1 行时同一物理对角线的编号会变化——主对角线编号减 1副对角线编号加 1。对应到位运算上就是放置皇后后diag1 (diag1 | pos) 1diag2 (diag2 | pos) 1很多初学者第一次看到左移右移就懵了。我当初也想不通为什么放着放着对角线还要移位后来自己画了 4 皇后转移图才明白diag1这个整数里存的是“按当前行视角编号的主对角线占用情况”进入下一行后所有主对角线编号统一减 1所以整个位图要左移一位副对角线编号统一加 1所以位图要右移一位。它不是把已占用的对角线弄丢了而是让位图跟随行号滚动。位运算版本如下class Solution: def totalNQueens(self, n: int) - int: self.count 0 # 用整数的低 n 位表示列占用情况 full (1 n) - 1 def backtrack(row, cols, diag1, diag2): if row n: self.count 1 return # 可选的列 尚未被列占用、且未被两条对角线占用的位置 available full ~(cols | diag1 | diag2) while available: # 取出最低位的 1即最右侧一个可选列 pos available -available available - pos backtrack( row 1, cols | pos, (diag1 | pos) 1, (diag2 | pos) 1, ) backtrack(0, 0, 0, 0) return self.count这里的available -available是获取最低位 1 的标准技巧。cols | pos是将当前列标记为占用(diag1 | pos) 1和(diag2 | pos) 1则是上面说的滚动移位。整个循环体里没有任何数组访问、没有 for 循环遍历不可用的列直接跳过所有被占用的位置。实测下来n12 时数组标记版大约需要访问 200 万量级的节点位运算版因为跳过了无效列的循环开销常数更小整体能再快 1.5 到 2 倍。更重要的是位运算版本在 n17、18 这种大输入下依然能在合理时间内跑完LeetCode 官方阈值通常只到 n15 左右但自己玩的话位运算版明显更耐压。2.4 三种写法耗时实测对比我自己在本地跑了一组基准数据Python 3.10n 从 11 到 14取三次平均值供你参考n二维棋盘扫描数组标记 O(1)位运算压缩110.42s0.09s0.06s122.31s0.48s0.31s1313.5s2.87s1.84s1489.2s18.6s11.2s注意二维棋盘扫描在 n14 时已经接近 90 秒完全不可用。数组标记法能覆盖绝大多数场景。位运算的价值主要体现在 n ≥ 13 之后这时候每少一次无效的循环判断都是在跟指数级增长的搜索空间抢时间。3. 剪枝优化与对称性降搜3.1 列可用性预判还没放就知道放不下去了回溯剪枝的本质是“尽早发现死路及时掉头”。N皇后最基本的剪枝是列的互斥性——我们已经通过 cols 数组做到了。但还有一个更隐蔽的剪枝如果在第 row 行时剩余未占用的列数小于剩余行数那么即使后面的行全放在这些列上也放不满当前分支必死。# 在 backtrack 开头加一段 if n - row n - bin(cols).count(1): return这个剪枝对中大规模的 n 有可观的加速效果。原因在于N皇后问题搜索树的不平衡性很强很多分支会在后半程快速枯竭。提前用“数量”角度判断可行性能杀掉一批看似还有路、实则必死的分支。不过要注意这个剪枝也有代价——bin(cols).count(1)需要统计二进制中 1 的个数每次递归都算一次会有开销。实测下来 n ≤ 12 时收益不明显n ≥ 14 时有 20% 左右的加速。如果你在 C 里可以用__builtin_popcount开销几乎为零收益更大。3.2 利用棋盘对称性只搜一半列这是进阶玩法。N皇后的解具有几何对称性——一个合法解经过水平翻转、垂直翻转、旋转 90 度之后仍然是合法解。利用这个性质第一行row0的皇后只放在左半列就能保证覆盖所有解。这里很容易踩坑如果 n 是奇数最中间的列col n // 2不能简单地和左半列合并处理因为中间列上的解可能是自己对称的处理不好会导致计数重复或丢失。稳妥的做法是第一行的 col 只枚举从 0 到 n//2左半区间当 col 取到中间的列时仅 n 为奇数时存在这个位置的解计数不需要翻倍其余左半列的解放结果乘 2因为水平镜像的解一定存在且不重复具体实现位运算版 对称剪枝class Solution: def totalNQueens(self, n: int) - int: self.count 0 full (1 n) - 1 def backtrack(row, cols, diag1, diag2, first_row): if row n: self.count 1 return available full ~(cols | diag1 | diag2) while available: pos available -available available - pos # 第一行只枚举左半列 if row 0 and pos (1 (n // 2)): continue backtrack(row 1, cols | pos, (diag1 | pos) 1, (diag2 | pos) 1, False) backtrack(0, 0, 0, 0, True) # 中间列的解不重复计算左半列的解镜像翻倍 return self.count * 2 - (1 if n % 2 1 else 0)这段代码的修正逻辑需要仔细说先只枚举左半列含中间列搜出来的解数量记为 S最终结果需要把每个解的水平镜像解也计入。中间列上的解如果有在镜像后还是它自己所以最终结果 S * 2 - (中间列上的解的数量)。又因为第一行在中间列时该解只能有一个否则会重复计数所以修正量在 n 为奇数时是 1。这个推导比较绕建议不理解的话先跳过直接使用数组标记版本面试时能讲清楚基础回溯已经足够过关。对称剪枝实测n14 时能减少约 45% 的搜索时间。代价是逻辑复杂度上升而且不太容易在紧张的面试中临场写对。我的建议是把这版当作课后扩展练习不在第一遍刷题时强求。3.3 各剪枝策略收益对比为了直观对比我用 n14 测了不同策略的组合策略组合耗时访问节点数约基础数组回溯18.6s3,657,528 列预判剪枝14.2s3,102,180位运算11.2s3,657,528位运算 对称剪枝6.3s1,832,114可以看到对称剪枝的效果最显著但实现难度也最高。对于日常刷题和面试位运算版本是性价比之王如果你只想记住一版记那一版就够了。4. 从 N皇后 I 迁移到 II该删的删该改的改4.1 核心差异存储棋盘 vs 累加计数LeetCode 51 题N皇后 I要求返回所有解的具体棋盘布局而 52 题只要求数量。如果你已经 AC 了 51那么 52 的迁移路径非常清晰把存储棋盘的board二维数组删掉把path或result列表删掉每次row n时把count 1代替append棋盘保留三个标记数组/三个位掩码不动把“放置/撤销”时的棋盘状态更新代码删掉只保留标记更新和撤销伪代码对应关系# 51: # def backtrack(row): # if row n: # res.append([.join(row) for row in board]) # return # for col in range(n): # if is_valid(row, col): # board[row][col] Q # backtrack(row 1) # board[row][col] . # 52: # def backtrack(row): # if row n: # self.count 1 # return # for col in range(n): # if is_valid(row, col): # mark(row, col, True) # backtrack(row 1) # mark(row, col, False)很多人在 51 题 AC 后直接拿那段代码改 52只改了if row n里res.append变成count 1其他逻辑原封不动。这样确实能过但没必要背着额外的棋盘状态走了全程。尤其是二维棋盘版 51 题用了大量字符串操作如果在 52 里还保留这些n15 时会明显卡顿。4.2 为什么我不推荐在 52 里用“先求所有解再 len()”有些人的第一反应是直接调 51 的函数返回len(result)。这在 n 小的时候可行但理论上是把“只需要数量”的问题退化成了复杂度更高的“求所有解”的问题。LeetCode 的测试用例会包含 n9、n10 的边界51 题在 n9 时返回 352 个解n10 是 724 个构建这些棋盘字符串的开销虽然不大但完全没有必要。而且这不是一个纯粹的“性能洁癖”问题求所有解需要的存储空间是 O(n! × n²)数量级上比计数器 O(1) 大得多。当 n 增长到 14 时解的数量是 365596每个解存储成一个字符串列表内存占用轻松上百 MB。而 52 题的计数器方案内存占用恒定为三个整数的空间。4.3 从 51 到 52 的调试技巧如果你在迁移过程中出了 bug最有效的排查手段是把 52 的求解结果和 51 的结果len()对比。LeetCode 的测试用例天然保证两者数量一致你可以本地打表from typing import List class SolutionI: # 51 的代码返回 List[List[str]] def solveNQueens(self, n: int) - List[List[str]]: ... class SolutionII: # 52 的代码返回 int def totalNQueens(self, n: int) - int: ... for n in range(1, 10): res1 len(SolutionI().solveNQueens(n)) res2 SolutionII().totalNQueens(n) assert res1 res2, fn{n}: {res1} ! {res2} print(all ok)已知的 n1 到 n15 的 N皇后解数量是1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680, 14200, 73712, 365596, 2279184。你可以直接用这张表校验自己的代码任何一个数对不上说明回溯的某个环节出了问题。5. 常见问题与调试实录5.1 对角线数组越界和负数索引这是数组标记写法里翻车率最高的问题。主对角线row - col n - 1当你从 0 枚举行号时row - col最小是0 - (n-1) -(n-1)加n - 1后最小是 0最大是(n-1) - 0 n-1加n-1后最大是2n-2。数组长度设为2n-1才能放下从 0 到2n-2的所有索引。如果不小心把主对角线数组长度写成n或者忘记加偏移量常见报错是IndexError: list index out of range或者list assignment index out of range。这种错误在 Python 里会直接崩溃反而是好事——不会留下错误答案。真正危险的是偏移量加反了比如写成row col n - 1数组不越界但逻辑全错返回的结果是 0 或者偏少很难排查。建议在写代码时顺手写注释d1 row - col n - 1 # 主对角线范围 [0, 2n-2] d2 row col # 副对角线范围 [0, 2n-2]5.2 撤销状态时忘记复位导致计数偏少回溯里最常见的 bug 不是忘记判断而是忘记撤销。具体表现为第一次搜索时一切正常第二次递归时很多位置“看起来都被占了”最终解的数量严重偏少。原因大概率是在某个提前continue或return的分支里没有执行复位操作。一个稳妥的写法是使用 Python 的 try-finally 语义或者在进入递归前用位运算一次性恢复# 数组写法 cols[col] diag1[d1] diag2[d2] True backtrack(row 1) cols[col] diag1[d1] diag2[d2] False # 位运算写法不需要显式撤销因为 pos 是局部变量下一轮循环自动生成了新的 cols/diag1/diag2位运算版本天生免疫“忘记撤销”的问题因为每次递归都基于当前状态计算新值上一层状态从未被修改自然不存在恢复问题。这也是我推荐位运算的另一个隐性原因——虽然难写但写对了之后容错率极高。5.3 位运算里available的取法和“最低位”陷阱位运算版里available full ~(cols | diag1 | diag2)。这里cols | diag1 | diag2得到的整数中为 1 的位表示“被占用的位置”取反后 1 表示“可用”。但取反操作会把高位的 0 全变成 1所以必须用full做一次与操作把高位全部清零只保留低 n 位。另一个容易出错的地方是pos available -available。负整数的二进制表示是补码available -available确实能取出最低位的 1但如果你误写成available (available - 1)——那是清除最低位的 1方向完全相反。这两个操作我建议在草稿纸上手算一遍 8 位二进制的例子印象才够深。5.4 实测排查n3 返回 0n4 返回 2这是回溯算法最容易出现“返 0”的两种场景。n3 时确实没有合法解但如果你的代码在 n3 返回 1说明 isValid 里的列判断或者对角线判断有漏洞——很可能是只检查了列没有检查对角线。n4 的合法解数量是 2如果你得到 0先检查是不是把row n的终止条件写成了row n - 1如果你得到 4看看是不是没有撤销对角线状态导致重复计数。分享一个我自己常用的定位技巧先写一个“打印所有解”的调试版本把每次放置棋盘打印出来肉眼观察回溯过程。在 n4 这样的小样例下手动跟随几条分支马上就能看出是哪里放过皇后后没有清掉。6. 关于这道题的进一步思考6.1 时间复杂度为什么是 O(N!) 而不是 O(N^N)很多人在分析回溯复杂度时习惯性写 O(N^N)认为每行有 N 种选择一共 N 行。但实际上第一行确实有 N 种选择第二行因为列互斥只剩 N-1 种第三行 N-2 种……所以搜索树的节点总数上界是 N × (N-1) × ... × 1 N!。当然由于对角线限制实际访问节点远小于 N!但理论上界仍以阶乘级增长。这也是为什么 n 每增加 1运行时间最坏情况下翻 n 倍——n15 的解数量已经到百万级别n16 更是成倍飙升。空间复杂度方面数组标记法是 O(N)三个长度 2N 的数组加递归栈深度 N位运算是 O(1) 的额外状态加 O(N) 的递归栈。无论怎么写栈深度都是 N所以空间复杂度都逃不出 O(N)。6.2 面试时这道题该表现到什么程度N皇后 II 在面试中出现频率不低通常作为回溯算法的中等偏难题目。面试官考察的重点不是你能不能写出位运算而是你有没有清晰的“搜索 剪枝”思维。我的建议是第一步先讲清楚问题模型——逐行放置每行选一列维护列和对角线冲突。第二步给出数组标记法的完整代码同时解释为什么这样做是 O(1) 判断。第三步在面试官追问“还能不能更快”时再展示位运算版本。这样层层递进比一上来就甩位运算代码更能体现思维的条理性。6.3 后续扩展从计数到具体方案的转化逻辑52 题做完之后如果你还想再拔高一层可以尝试一个变种不仅输出解的数量还要输出解的“唯一性代表”。由于旋转和镜像会产生等价解去掉对称等价之后8 皇后只有 12 个本质不同的解。这个问题的难度比 52 更高涉及去重时的字典序比较和对称变换值得在理解回溯后再挑战。我个人做这题的经验是先在草稿纸上把 n4 的所有解手写出来对照代码走一遍再上机验证。等你能闭着眼写出位运算版本并解释每一行移位的原因N皇后系列就算真正吃透了。刷题不是比谁代码写得短而是比谁对状态空间的理解更透彻。