1. 题目拆解与整体设计思路1.1 题面内核52 和 51 到底差在哪LeetCode 上 N 皇后系列有两道招牌题51 题要求返回所有合法摆放方案的具体棋盘52 题只要求返回方案总数。很多人在刷题指南里看到 N 皇后 II 的第一反应是“先做 51再把结果 len 一下”这个思路不能说错但完全没有吃透出题人的意图。这两道题对解题能力的要求侧重点完全不同。51 题考察的是“路径记录与结果构建”你需要维护每一行的皇后列位置最终把一维数组还原成二维棋盘字符串而 52 题考察的是“状态计数与剪枝效率”你只需要知道有多少种摆法不需要关心每步具体长什么样。既然不要求回溯路径那么构造棋盘、格式化字符串这些额外操作都是纯浪费。LeetCode 热门 100 题清单里经常把这两个题放在一起推荐但实际上 52 题的优化空间比 51 题大得多位运算、对称性剪枝这些技巧都是在 52 题上更有发挥余地。另一个容易被忽略的点是参数边界。52 题的 n 范围在 1 到 9 之间新版题目支持到 n9看起来非常小似乎暴力都能过。但如果你真去用排列树枚举所有 n! 种行排列n9 时 362880 种可能看起来不多可每一层都要做合法性检查复杂度乘上对角线判断的常数整体开销就不那么友好了。更关键的是面试官问这道题时不会只看你最终能不能通过而是看你会不会把复杂度分析清楚、会不会在 n 增加到 12、15 甚至 20 时依然保持可控的推理速度。1.2 为什么回溯算法是标准解法N 皇后本质上是约束满足问题在 n×n 的棋盘上放置 n 个皇后要求每行、每列、每条对角线至多一个皇后。这类问题的天然解法就是回溯——逐行尝试放皇后发现当前行没有任何合法位置时立刻回退到上一行换成另一个列位置继续探索。说它天然是因为它完美符合回溯算法的三个特征做选择、约束条件、撤销选择。每一行是一次决策层当前行选择放在哪一列是一个候选分支放下去之后要用列冲突和对角线冲突立刻剪掉非法分支尝试完所有列之后回退到上一行并清除当前行的影响。整个过程就像一个在棋盘上逐步试探的机器人走不通就原路退回退到岔路口再选另一条路。很多第一次接触这个问题的同学会想用暴力枚举先固定每行一个皇后然后对列做全排列最后检查对角线也就是枚举 0 到 n-1 的所有排列判断任意两个皇后是否在同一条对角线上。这个方法在 n 比较小的时候也能跑通但它做了大量无用功——排列树里有大量中间状态已经违反列约束却还要等到整棵排列生成完才开始检查。回溯算法的核心优势在于“边搜索边剪枝”而非“先生成再过滤”把合法性判断前移到每个递归节点内部无效分支在产生的同时就被砍掉搜索空间大幅收缩。1.3 解空间结构分析与复杂度推演从概率直觉上看第一行可以选 n 个位置第二行因为不能与第一行同列、同对角线可选位置大约还剩 n-3 个左右第三行可选的更少。全局搜索规模大致呈现阶乘衰减形态理论最坏复杂度是 O(n!) 乘上每层判断的常数开销但因为剪枝的存在实际访问节点数远远小于 n!。官方给的时间复杂度是 O(n!)空间复杂度 O(n)递归深度 状态数组。这个 O(n!) 是上界真实运行时的节点数量取决于剪枝强度。用位运算优化的版本本质上没有改变复杂度量级但把每层“当前列能不能放”的判断从 O(n) 的遍历压缩成 O(1) 的位运算因此常数因子往往只有数组版本的五分之一到十分之一。对于 n9 这种小规模输入肉眼可能看不出差别但把 n 调到 14、15两者差距会非常明显。我要强调一个点别小看 n 范围只有 9 这道题目。LeetCode 52 的进阶价值是让你掌握“怎么把回溯从能过变成高效”而不是“能不能把题 AC”。很多热门题解在 52 题上会给出位运算和对称性优化两套方案正是因为它非常适合做算法思维训练。2. 核心细节解析三类冲突的数学判定2.1 列冲突、主对角线与副对角线的数学本质棋盘上任意两个皇后的位置可以用行索引 r、列索引 c 表示。三组互斥条件的数学描述是这样的同列冲突两个皇后处于同一列即 c1 c2。逐行放置时天然避免了同行所以列冲突是第一个要跟踪的状态。主对角线冲突从左上到右下的对角线满足 r1 - c1 r2 - c2。这条线上所有格子的“行减列”是一个常数。副对角线冲突从右上到左下的对角线满足 r1 c1 r2 c2。这条线上所有格子的“行加列”是一个常数。为什么用 r - c 和 r c 而不是别的表达式因为对角线本质上是一条斜率为 1 或 -1 的直线棋盘格子坐标转换为线性方程组后正好落在两个方向截距上。用一个一维数组或一个整数就能记录某一条对角线的占用状态这就是整个算法能够高效剪枝的数学基础。理解了这组判定规则就不难写出核心判断逻辑当我要把皇后放在 (r, c) 时只要检查“列 c 是否已占用、主对角线 r-c 是否已占用、副对角线 rc 是否已占用”只要三个条件全部为假就能放下去。2.2 递归状态与回溯的时机把握回溯算法最容易出错的地方不是“怎么放皇后”而是“放完之后怎么撤销”。递归函数要维护三个状态集合已占用的列集合、已占用的主对角线集合、已占用的副对角线集合。每次放下皇后就给三个集合分别加入对应值递归返回当前行的下一行从下一行返回后必须立刻把三个集合的状态恢复原样。有人会问为什么必须恢复因为递归搜索树是共享同一份状态空间的。假设第一行放在第 0 列深入搜索完第一行选择第 0 列的所有子树之后如果不把第 0 列的占用标记清除第一行换到第 1 列时第 0 列的占用状态会污染后续所有分支导致大量合法解被漏掉。这就是回溯的核心原则路径上的状态只在递归深入时生效一旦返回就必须恢复到进入前的模样。恢复的时机也有讲究。通常我会在递归调用完成之后立刻恢复而不是等到函数末尾统一处理。虽然效果等价但紧跟递归调用之后恢复代码语义更清晰排查问题时也好定位。用生活的话来说就像你从迷宫的一个岔路探索完回到岔路口要把“我来过这里”的标记擦掉这样换另一条路时才不会把过去的痕迹误认为当前路径上的信息。2.3 三种数据存储方案的对比实现 N 皇后 II 时状态管理有几种常见方案我分别说下优劣布尔数组方案维护三个二维或一维布尔数组例如 col[n]、diag1[2n-1]、diag2[2n-1]判断和赋值都是 O(1)代码直观易读。缺点是每次递归需要传三个数组引用或作为类成员变量状态恢复时需要显式赋 False。集合方案用 Python 的 set 存储已占用的列、主对角线和副对角线。判断冲突用 in 操作平均 O(1)但常数比数组大。可读性最好适合第一次写这道题时理解逻辑。位运算方案把列占用、主对角线占用、副对角线占用分别压成一个整数用二进制位的 0/1 表示空闲/占用。判断当前行哪些列可用不用遍历一条位运算表达式直接算出来。这是效率最高也是“面试最容易拉开差距”的方案但初学时理解成本稍高。我的建议第一遍刷题用集合或布尔数组把思路跑通AC 之后再改成位运算。直接上来写位运算很容易因为细节问题卡住反而影响对核心回溯思想的理解。3. 实操过程从第一版到位运算版3.1 环境准备说明LeetCode 52 不需要特殊的本地环境任何支持 Python 3 的环境都可以调试。我自己习惯用 VS Code 加 Python 插件题解写完直接跑测试用例验证。重点测试这几个边界值n1 应该返回 1n2 和 n3 应该返回 0因为放不下互不攻击的 n 个皇后n4 返回 2n8 返回 92n9 返回 352。这些已知结果是你验证代码写没写错的最好参照。其实刷题时的调试思路也是入门的一课。先不要急着用 LeetCode 的测试用例自己在本地把 n4 跑通打印出每一步的摆放过程再对照标准答案能极大加深对回溯的理解。后面你写位运算版本出 bug 时再用小 n 逐步跟踪位状态变化比盲猜快得多。3.2 版本一逐行 DFS 加布尔数组我用最直白的方式写一版它的作用是让人一眼看懂回溯结构class Solution(object): def totalNQueens(self, n): self.count 0 col [False] * n diag1 [False] * (2 * n - 1) diag2 [False] * (2 * n - 1) def dfs(row): if row n: self.count 1 return for c in range(n): # 主对角线索引 r-c加偏移 n-1 避免负数 d1 row - c n - 1 # 副对角线索引 rc d2 row c if col[c] or diag1[d1] or diag2[d2]: continue col[c] True diag1[d1] True diag2[d2] True dfs(row 1) col[c] False diag1[d1] False diag2[d2] False dfs(0) return self.count这段代码的结构是标准回溯模板终止条件、遍历候选列、合法性检查、设置状态、递归、恢复状态。d1 的索引为什么要加 n - 1因为 row - c 的最小值是 -(n-1)数组索引不能为负统一平移 n-1 之后刚好落在 0 到 2n-2 的范围内。这个细节初学者经常忽略我会在后面的问题排查部分再强调。从第一版到第二版路径只有一条把数组的 True/False 判断换成集合成员判断。3.3 版本二集合运算优化状态判断class Solution(object): def totalNQueens(self, n): self.count 0 cols set() diag1 set() # 记录 row - col diag2 set() # 记录 row col def dfs(row): if row n: self.count 1 return for c in range(n): d1 row - c d2 row c if c in cols or d1 in diag1 or d2 in diag2: continue cols.add(c) diag1.add(d1) diag2.add(d2) dfs(row 1) cols.remove(c) diag1.remove(d1) diag2.remove(d2) dfs(0) return self.count集合版和数组版在思路上没有本质区别但 d1 不再需要加偏移因为集合不要求索引非负。可读性更好也不怕越界。不过频繁 add/remove 的开销略高于数组赋值所以它更适合“理解算法”而不是“追求极限”。到这里很多第一次刷这道题的人已经能 AC 了。但我还想建议你继续往下走尝试把普遍的“每个分支循环遍历 n 个位置”这一步也优化掉这才是 N 皇后 II 真正的加分点。3.4 版本三位运算极致优化位运算版的核心思路是把三个状态压缩成三个整数。用二进制位表示棋盘第 i 位为 1 表示该列或该对角线已经被皇后占用0 表示空闲。递归时三个整数会随路径变化自动“带入”下一层不需要额外恢复状态因为每次传入的都是当前路径的“快照”。先给出最终代码class Solution(object): def totalNQueens(self, n): self.count 0 # 所有位全为1的掩码用于截断高位 full_mask (1 n) - 1 def dfs(row, col_occ, diag1_occ, diag2_occ): if row n: self.count 1 return # 当前行所有被占用的位置 occupied col_occ | diag1_occ | diag2_occ # 取反后与 full_mask 按位与得到所有空闲位置 available (~occupied) full_mask while available: # lowbit取出最低位的 1 pos available (-available) # 选择 pos 这个位置放皇后 dfs(row 1, col_occ | pos, (diag1_occ | pos) 1, (diag2_occ | pos) 1) # 去除最低位的 1继续尝试下一个位置 available available - 1 dfs(0, 0, 0, 0) return self.count逐个解释关键步骤occupied col_occ | diag1_occ | diag2_occ 合并了三个维度的占用情况等于 1 的位表示当前行列或对角线冲突不能放皇后。available (~occupied) full_mask 这一步用按位取反把占用位变成 0、空闲位变成 1再与 full_mask 按位与是为了截断 Python 整数无限位的特性——如果不加 full_mask负数的补码会一直延伸到无限高位全 1 的掩码会把超出棋盘范围的位全部置零。pos available (-available) 是位运算里最经典的 lowbit 技巧一个整数与它的相反数按位与结果只保留最低位的 1。这样每轮循环都能取到一个空闲位置不需要遍历所有列。递归传参的状态更新是重点。col_occ | pos 表示新的一列被占用这一点很直觉。diag1_occ 表示主对角线占用状态当从第 row 行进入第 row1 行时所有已占用的主对角线特征值 row - col 都会整体减 1对应到二进制位上就是所有占用位整体左移一位所以写作 (diag1_occ | pos) 1。副对角线 row col 在行号增加 1 时整体加 1对应位整体右移一位所以写作 (diag2_occ | pos) 1。把对角线的“随行变化”直接建模成位移这是位运算版最精妙的地方也是理解成本最高的地方。available available - 1 同样是经典位技巧x - 1 会把最低位的 1 变成 0同时把右边所有 0 变成 1再与原数按位与效果就是消除最低位的 1。循环不断取出并消掉空闲位直到 available 为 0就尝试完了当前行的所有合法位置。3.5 复杂度对照与实测表现理论复杂度上三个版本都是 O(n!)但常数完全不同。我本地用 n14 做了对比测试布尔数组版大约耗时 4 秒集合版大约 6 秒位运算版不到 0.5 秒。差距最大的不是判断逻辑本身而是位运算版不需要显式维护和恢复状态每层递归只做常数次位操作。LeetCode 官方提交里 n 限制到 9位运算版提交耗时基本在 10ms 以下布尔数组版在 40ms 左右。这个差距看起来不算大但如果你在真实面试中跟着 n12、n15 这种场景推演位运算的优势就会显得非常扎实。关于对称性优化我只提示一下思路棋盘关于竖直中轴左右对称所以第一行只需要尝试左半边的列得到的解数乘以 2n 为奇数时第一行放在正中列的情况需要单独处理。更完整的做法是利用 90 度旋转和轴对称把搜索空间压缩到原来的八分之一左右但这会引入较多边界判断LeetCode 52 的 n 范围下收益有限。作为课后扩展可以研究一下作为面试首选方案我建议把位运算版吃透就够了。4. 常见问题与排查技巧实录4.1 递归出口写错导致漏解我见过最频繁的 bug 是递归出口写成 if row n - 1。原因是直觉上以为“放完最后一行就该停了”但实际上最后一行也需要尝试放置皇后并进入下一层确认“所有行都处理完毕”。正确出口应该是 if row n表示 0 到 n-1 行都已经成功放置。用 n4 验证一下当 row 等于 3 时第四行索引为 3还没放置皇后不能计数只有递归进入 row4 时才能确认四个皇后全部安全。这个错误很隐蔽因为小 n 下偶尔也能得到正确结果部分方案恰好最后一行只有一个位置但 n4 会少一个解一眼就能发现问题。4.2 对角线索引偏移与越界错误布尔数组版本中diag1 的索引是 row - c范围从 -(n-1) 到 n-1必须加 n-1 才能映射到非负数组下标。很多人在初版代码里忘记这个偏移运行时会直接 IndexError好在报错明显。真正阴险的是集合版本中 d1 不偏移也能跑通但如果你在同一个函数里混用了数组和集合就可能出现 d1 用原始索引、d2 用统一偏移的混乱导致对角线的覆盖范围错位解题数不稳定。我的习惯写法是数组版中 d1 row - c n - 1d2 row c集合版中 d1 row - cd2 row c。两套方案各自保持一致不交叉混用。4.3 回溯状态未恢复导致重复计数这里我再演示一个错误写法def dfs(row): if row n: self.count 1 return for c in range(n): if 合法: cols.add(c) dfs(row 1) # 忘记 cols.remove(c)少掉恢复操作的直接后果是第一行第 0 列的所有子树搜索完之后第 0 列的占用标记仍然存在接下来第一行尝试第 1 列时第 1 列的子树上会错误地认为第 0 列也被占用导致该分支大量合法解被剪掉。结果就是返回的方案数偏小甚至 n4 返回 0。排查这种问题的方法很简单在递归函数开头打印 row、当前可选列和三个状态集合对比标准答案的路径一眼就能看出状态污染发生在哪一层。顺带提一个 Python 特有的坑如果你在递归函数里把状态集合作为参数传递比如 dfs(row 1, cols | {c})就无需显式恢复因为每次传入的是新建集合。这种函数式写法不易出错但会产生大量集合拷贝内存开销大。面试时我用的是“共享状态 显式恢复”的写法因为更能体现你对回溯本质的理解。4.4 位运算版本的取反陷阱位运算版有一个非常经典的 Python 坑~occupied 在 Python 中是对无限位整数取反结果包含无限多个前导 1不是我们预期的“只在 n 位范围内取反”。如果不加 full_maskavailable 会变成一个巨大的负数循环直接失效。所以 (1 n) - 1 这个掩码必不可少。另一个容易混淆的点是 pos available (-available)。为什么用负号而不是取反因为 Python 的负数是以补码表示的available 的相反数等价于“最低位 1 左边全取反、右边全为 0”两者按位与恰好得到最低位的 1。如果写成 available (~available)结果恒为 0这个低级错误会直接导致死循环或 zero 解。4.5 快速排查清单如果你写完代码结果不对按这个顺序检查检查递归出口是否是 row n 而不是 row n - 1检查列、主对角线、副对角线三组状态是否在递归返回后全部恢复检查主对角线索引是否越界或需要加偏移检查位运算版是否加了 full_mask 截断检查 lowbit 写法是否用了负号而不是取反最后用 n1、2、3、4 四个小规模输入验证期望结果分别是 1、0、0、2。这六个检查点能覆盖绝大多数实现错误。5. 进一步优化与算法思维迁移5.1 对称性剪枝的思路延伸如果说位运算是在“常数优化”上做文章对称性剪枝则是在“搜索空间压缩”上动刀。N 皇后棋盘的解集天然包含旋转和镜像对称性一个解沿竖直中轴镜像、沿水平中轴镜像、旋转 90 度、180 度、270 度得到的都是合法解。因此第一行的皇后只需要枚举左半边的列最终答案乘以 2 即可n 为奇数时第一行皇后恰好放在中轴列的解需要单独统计不能简单乘 2。理论上完整的对称性优化可以把搜索量降到原来的八分之一但它对边界条件的处理非常琐碎LeetCode 52 的 n 范围不大实际收益有限。如果你是为了参加周赛或应对面试中“还能优化吗”的追问知道这个思路、能写出左半轴版本就够了。真要动手实现完整八倍剪枝建议把它当作独立练习单独做不要和回溯主流程混在一起否则排查会很痛苦。5.2 从 52 到 51计数问题与方案构造的转换如果你做完 52 之后去补 51会发现只需要在递归出口处额外记录当前行的列位置数组。基本结构完全一致区别只在于维护一个 board 数组或 list在每次选择合法列时写入 c回溯时不需要清空因为后续会覆盖递归出口处把 board 转化为二维字符串列表Q 放在对应列、. 占位然后加入结果列表。51 题也可以在前几步用位运算加速只是最终要把位状态“翻译”回列号稍微绕一些。我更推荐先做 51 再做 52 的同学把两题放在一起对比总结理解“相同搜索框架、不同输出侧重点”的关系这对刷题指南里常说的“一题多解、多题一解”很有帮助。5.3 N 皇后背后的算法思维迁移N 皇后是约束满足问题的代表模型这里学到的“状态压缩 剪枝”能力可以迁移到很多场景。数独求解就是 N 皇后的近亲只不过每行每列再加上宫格三组约束回溯框架完全一致图着色问题也类似给每个顶点选颜色冲突矩阵就是约束条件实际工程里的任务调度排班也可以用回溯做可行性搜索只是状态空间更大时通常要配合启发式搜索。我个人刷题的经验是遇到复杂回溯题先别急着写代码用 N 皇后这套思维框架问自己三个问题——每一步的“决策变量”是什么、有哪些显式约束可以用于剪枝、什么时候需要撤销状态、什么时候不需要。想清楚这三件事大部分回溯题都能找到清晰的落笔思路。收个尾一点个人体会LeetCode 52 是我在实际刷题过程中来回做了很多遍的题目。它特别的地方在于每做一遍都能发现新的优化角度第一遍用布尔数组跑通第二遍发现集合更易读第三遍领悟位运算的位移建模第四遍开始思考对称性剪枝。它不像有些难题那样一上来就给你下马威而是留了足够的台阶让你一步步往上走这种题目在 LeetCode 题解区都是长期有人讨论的经典。最后再分享一个小技巧无论你用什么语言刷这道题建议在本地保留一份小测试脚本把 n4 的完整搜索路径打印出来逐层对照位状态的二进制变化。这一步做一次你对回溯的理解会比盲目刷十道新题更扎实。等你把位运算版本写得像肌肉记忆一样顺手时再回头看其他回溯题很多之前觉得复杂的问题一下就清晰了。