回溯、剪枝、N皇后这几个词放在一起几乎是算法面试里绕不开的经典组合。很多人一看到“N皇后”就头大觉得棋盘题复杂、代码容易绕晕也有不少人背过LeetCode 51的代码但换一道变体就不会了。实际上N皇后是理解回溯算法最理想的一道题它的搜索空间直观可见剪枝逻辑接近真实世界的决策过程而且同样思路能直接迁移到全排列、组合求和、数独求解等一系列题目上。这篇文章我就用八皇后入手把回溯框架、剪枝策略、位运算优化讲透再贴出LeetCode 51和52的完整实现与踩坑记录。如果你是一个刚开始刷回溯题的同学看完这篇能彻底搞懂N皇后的每一个判断条件为什么这么写如果你已经会套模板那么我重点聊的剪枝细节和位运算思路能帮你把代码复杂度降下来、面试时写得更有底气。1. 回溯算法的本质把暴力搜索变成决策树遍历1.1 为什么N皇后问题不能用暴力枚举先看八皇后最原始的表述在一个8×8的棋盘上放置8个皇后要求任意两个皇后不能在同一行、同一列或同一条对角线上。如果直接暴力枚举最朴素的想法是从64个格子里选8个格子也就是C(64, 8)种组合。这个数字大概是40多亿单靠循环去验证每一组合是否合法程序跑完一个8皇后就已经要等很久更不用说n10、n12的情况。但换个角度看这个问题题目有一个天然限制每一行最多只能放一个皇后。因为两个皇后不能在同一行这是硬性约束。所以我们可以把“在64个格子选8个”拆成“逐行决策”第一行有一个位置第二行有一个位置……一直放到第八行。这样搜索空间直接从组合数变成了8的8次方也就是1600多万种情况虽然还是大但已经有优化的空间。这个“逐行决策”的思路就是回溯的雏形每一步做一次选择做完全部选择后判断是否满足条件如果不满足就回退到上一步换一种选法。它本质上是深度优先搜索只不过搜索的对象是一棵决策树。1.2 回溯三步法选择、递归、撤销回溯算法有一个非常统一的代码骨架几乎覆盖了九成回溯类题目def backtrack(路径, 选择列表): if 满足结束条件: 记录结果 return for 选择 in 选择列表: 做选择 backtrack(路径, 新的选择列表) 撤销选择对于N皇后问题具体映射关系是这样的路径已经放置好的皇后位置我用一个长度为n的数组存储每一行皇后所在的列号。选择列表当前行可以放置皇后的所有列号。结束条件行号走到n说明每一行都成功放置了一个皇后得到一个合法解。做选择在当前行的某一列放置皇后进入下一行继续递归。撤销选择把这一行的皇后移除尝试当前行的下一列。很多初学者写回溯代码容易漏掉“撤销选择”这一步导致结果错乱。这是因为递归返回后如果不清除当前状态上一层循环遍历下一个选择时路径会被之前的残留数据污染。撤销的本质是恢复现场让每一次分支尝试都从相同的初始状态出发。1.3 剪枝是回溯的魂而不是可有可无的优化如果把回溯比作找路那“剪枝”就是提前判断这条路走不通干脆不进去。N皇后问题中最自然的剪枝就是合法性检查在准备往第row行、第col列放皇后前先扫描已经放置的皇后看它们是否和当前位置冲突。如果冲突这个分支直接跳过。有人可能会觉得这个检查本身就增加了开销算不算剪枝算。因为在回溯树的遍历过程中一旦发现当前分支无解就立刻停止往下递归这个行为就是剪枝。真正高质量的剪枝不是靠复杂的启发式规则而是靠提前阻断无解分支。N皇后问题的剪枝有三个层次第一层行冲突天然消除因为我们按行递归每一行必然只放一个皇后。 第二层列冲突用数组标记O(1)时间内判断该列是否已被占用。 第三层对角线冲突用数学规律优化这也是最容易写错的地方。如果只用最基本的合法判断8皇后大概需要跑几万次递归调用如果加上数组标记剪枝递归次数会显著下降如果用位运算把三层判断合并成一个整数的位判断性能还能再提升一截。这三种方案我会在后面的章节里都给出来。2. N皇后的约束拆解与剪枝策略2.1 对角线判断的数学本质截距是恒定的N皇后问题的合法性判断难点不在行列而在对角线。我们要知道棋盘上的对角线分两种方向从左上到右下以及从右上到左下。判断两个格子是否处在同一条对角线上不能靠斜率公式慢慢算应该直接看坐标特征。假设棋盘的行号是row、列号是col。对于主对角线方向的格子它们满足row - col是一个固定值对于副对角线方向的格子它们满足row col是一个固定值。举个例子。在8×8棋盘上(0, 3)和(1, 4)这两个位置row - col分别是-3和-3说明它们在一条从左上到右下的对角线上(0, 3)和(1, 2)这两个位置row col分别是3和3说明它们在一条从右上到左下的对角线上。用这个规律做判断可以不用数组记录每一条对角线的占用情况吗可以。最朴素的写法是每到一个新位置就遍历之前所有皇后逐一比较row - col或者row col是否相等。但这样每次判断的复杂度是O(n)不是最优。更好的办法是直接用两个布尔数组分别记录哪些主对角线、哪些副对角线已经被占用。2.2 三种常见的冲突标记方案对比方案一每步遍历检查。这是最容易理解的写法在place(row, col)时循环检查之前所有皇后看列冲突或对角冲突。代码短逻辑直接但性能差特别是n增大以后递归次数和单次判断的复杂度同时增长。方案二数组标记。用三个数组分别记录列占用、主对角线占用、副对角线占用。列下标范围是0到n-1主对角线下标用row - col n - 1做偏移副对角线下标直接用row col。判断时O(1)解决回溯时把标记撤销。这是最推荐的工程写法。方案三位运算标记。用三个整数变量colFlag、mainDiagFlag、subDiagFlag的二进制位来标记占用情况。每放置一个皇后就把该列、该主对角线、该副对角线对应的位置1回溯时用异或操作恢复。位运算优化的核心收益是判断当前行哪些列可用时可以用位运算一次性得出所有合法位置而不是遍历0到n-1的每一列。我用一张表来对照这三种方案的核心特征方案空间占用单次判断复杂度代码复杂度适用场景每步遍历检查O(n)存棋盘O(n)最低面试热身、学习理解数组标记O(n)存棋盘O(n)存列O(2n-1)存对角线O(1)中等笔试、常规实现位运算标记O(n)存棋盘O(1)存标记O(1)较高性能要求高、大n测试数组标记已经是面试中的标准答案位运算是加分项。下面我重点把数组标记的对角线下标设计讲透因为这是大多数人写N皇后时第一个卡住的地方。2.3 下标偏移的主对角线设计细节主对角线判断用row - col但row - col的范围是-(n-1)到n-1有负数。如果把负数直接在数组下标里用肯定会越界。所以需要加一个偏移量比如统一加上n-1把范围映射到0到2n-2。这样主对角线数组长度就是2*n - 1。副对角线用row col代替范围是0到2n-2天然非负不需要偏移。这个偏移量设计是否合理直接决定代码是否正确。我见过不少人面试时栽在这里要么忘记给row - col加偏移要么偏移量算错导致对角线冲突漏检。踩过一次坑之后我的习惯是先写一行注释主对角线用 row - col n - 1副对角线用 row col把范围都检查一遍再动手写代码。2.4 n4手动推演看回溯如何走完决策树光讲代码框架不见得能真正理解回溯。我们手动模拟一下4皇后的完整决策过程。从第0行开始依次尝试列0、列1、列2、列3。第0行选择第0列row1。第1行第0列冲突跳过第1列副对角线冲突跳过第2列合法放置。第2行第0列冲突、第1列与主对角线冲突、第2列列冲突、第3列主对角线冲突全部不可用说明当前路径走到头了。回溯到第1行撤销第2列尝试第3列。第1行第3列合法放置。第2行第0列合法放置。第3行所有列都冲突此路不通。继续回溯到第0行撤销第0列尝试第1列。整个过程中一旦发现某一行没有任何合法列就立刻返回上一层而不是继续往下探索。这就是剪枝在起作用。n4的完整解只有两个但如果不用剪枝回溯树会被大量无效分支填充代码也会在无解分支上浪费很多时间。3. LeetCode 51与52完整实现与细节注释3.1 从一道题理解另一道题51和52的差异在哪里LeetCode 51要求返回所有解的棋盘解由字符串数组构成每一行是一个字符串Q表示皇后点表示空白LeetCode 52只要求返回解的个数。两道题底层算法完全一致区别仅在结果处理方式51需要deep copy棋盘并转换为字符串列表52只需要在找到解时累加一个计数器。基于常见的模板我给出一个用数组标记的Python实现同时兼容两个题目class Solution: def solveNQueens(self, n: int) - List[List[str]]: board [[. for _ in range(n)] for _ in range(n)] col_used [False] * n diag1_used [False] * (2 * n - 1) # row col diag2_used [False] * (2 * n - 1) # row - col n - 1 def make_board(board): return [.join(row) for row in board] def dfs(row): if row n: res.append(make_board(board)) return for col in range(n): d1 row col d2 row - col n - 1 if col_used[col] or diag1_used[d1] or diag2_used[d2]: continue board[row][col] Q col_used[col] True diag1_used[d1] True diag2_used[d2] True dfs(row 1) board[row][col] . col_used[col] False diag1_used[d1] False diag2_used[d2] False res [] dfs(0) return res def totalNQueens(self, n: int) - int: self.count 0 col_used [False] * n diag1_used [False] * (2 * n - 1) diag2_used [False] * (2 * n - 1) def dfs(row): if row n: self.count 1 return for col in range(n): d1 row col d2 row - col n - 1 if col_used[col] or diag1_used[d1] or diag2_used[d2]: continue col_used[col] True diag1_used[d1] True diag2_used[d2] True dfs(row 1) col_used[col] False diag1_used[d1] False diag2_used[d2] False dfs(0) return self.count这段代码里有一个容易忽略的点make_board函数对board做了字符串转换。很多语言中列表是引用类型如果直接把board加入结果后续递归会不断修改同一块内存最终导致所有结果都一样。所以51题一定要在找到解时生成一份独立的快照。Python中的[.join(row) for row in board]就是一种深拷贝式的快照。3.2 位运算优化版用三个整数代替三个数组如果n扩大到12甚至更大数组标记也能跑但位运算版本在判断“当前行有哪些列可用”时能一次性拿到所有合法列的集合省掉了for col in range(n)里对每一列的合法性判断。这个优化思路很值得学会因为它在很多状态压缩类题目里都会用到。思路是这样的三个整数colFlag、mainDiagFlag、subDiagFlag分别记录列、主对角线、副对角线的占用情况。第i位为1表示第i列或被映射到第i条对角线已经占用。搜索时先用这三个标记计算出当前行哪些列已经被占用occupied colFlag | mainDiagFlag | subDiagFlag注意mainDiagFlag和subDiagFlag的二进制位不是直接对应列号需要根据当前行row做映射。经典写法是主对角线标记当前是第row行第col列主对角线的编号用row - col n - 1表示所以在mainDiagFlag里对应的是第(row - col n - 1)位。判断是否占用用mainDiagFlag的第(row - col n - 1)位。副对角线标记子対角线编号用row col表示对应第(row col)位。如果直接把这三者做或运算必须把列号所在位统一到同一个基准上。一种常见实现是把对角线标记的位数左移或右移让当前行的“可用列”集中体现在一整块二进制区段。但这样解释起来容易混乱我建议初学者还是先用数组标记版本写对再研究位运算版本。这里给出一个清晰可读的位运算版本class Solution: def totalNQueens(self, n: int) - int: self.count 0 full (1 n) - 1 # 低n位全为1表示所有列都可用 def dfs(row, col_flag, diag1_flag, diag2_flag): if row n: self.count 1 return # 计算当前行所有可用的列 # diag1_flag 记录副对角线占用每下降一行需要右移一位 # diag2_flag 记录主对角线占用每下降一行需要左移一位 available full (~(col_flag | diag1_flag | diag2_flag)) while available: # 取出最低位的1即当前可放置的一列 pos available (-available) available ^ pos col pos.bit_length() - 1 dfs(row 1, col_flag | pos, (diag1_flag | pos) 1, (diag2_flag | pos) 1) dfs(0, 0, 0, 0) return self.count这个版本的核心巧妙之处副对角线在下一行会整体右移一位因为row col的编号在row增加时同一副对角线对应的列会减少1主对角线会整体左移一位因为row - col的编号在row增加时同一主对角线对应的列会增加1。这样递归传参时就自动完成了对角线的动态映射完全不需要数组偏移量。虽然这个版本更高级但它有一个可读性的代价。如果面试时写这个版本一定要能解释清楚左右移位的含义如果解释不清反而会扣分。我的建议是先用数组标记版本打底讲清楚之后提一句“大n优化可以用位运算”实际写不写看面试官反应。3.3 复杂度分析回溯算法的时间复杂度怎么算N皇后最坏情况下的搜索树规模是n的阶乘量级因为每一行的可选列数随行数增加而递减所以时间复杂度通常表述为O(n!)。但加了剪枝以后实际递归次数远小于n!。比如8皇后纯暴力8^8约1677万次尝试加剪枝后只需要约1.5万次递归调用12皇后差距更悬殊。空间复杂度方面数组标记版需要O(n)存棋盘结果O(n)存列占用数组O(2n-1)存对角线数组整体O(n)。递归栈深度是n也是O(n)。需要特别说明的是LeetCode 51如果要求返回所有解输出本身占用的空间不算入算法空间复杂度但如果你用列表保存所有结果实际内存占用是O(n * 解的数量 * n)即O(n^2 * 解数)。大n时这个内存开销可能比算法本身更可观这也是52题只需要计数却采用同样深度搜索的原因之一它能控制输出体积。3.4 从n1到n8的边界测试用例写N皇后代码边界用例务必跑一遍。我用几个典型输入自查n1唯一解是[Q]。很多代码在n0或n1时容易数组越界或结果为空这题必须单独验证。n2无解因为2×2棋盘放不下两个互不攻击的皇后。n3无解。n4两个解。n892个解这是经典结果如果输出不是92说明代码有bug。这些边界值可以在写完代码后立刻作为自测用例。尤其是n2和n3的无解输出能检查回溯流程是否正确处理了“全程无解”的情况。4. 常见问题排查与性能优化实录4.1 递归结果全是一样的快照没做对这是LeetCode 51最常见的问题很多人遇到输出结果重复且都是同一个棋盘。原因前面提过board是可变对象加入res时如果没有生成快照后续修改board会同时修改res里已经保存的结果。排查方法很简单在res.append处打断点观察每次加入的内容是否在后续被修改。修复方法是每次加入时做一个字符串快照而不是直接把board列表塞进去。4.2 列冲突判断失效数组下标对不上另一个高频问题出在对角线数组的长度上。主对角线数组长度必须是2*n - 1因为row - col n - 1的最大值是2n-2。如果图省事只申请了n长度运行时一定会越界或者更隐蔽地出现对角冲突漏检。建议在初始化时写一行注释说明每个数组的含义并在d1、d2计算完成后先print出来验证一次范围。这个习惯能帮你在一分钟内定位所有下标越界问题。4.3 剪枝位置不对循环内检查变成事后检查正确的剪枝位置是在进入下一层递归之前。有些写法是先无条件DFS进到下一层再判断当前位置是否合法这样虽然也能得到结果但会多出大量无效递归。剪枝应该前置当前列不合法就直接continue不要让递归函数带着非法状态继续执行。从代码风格上说把合法性判断放在循环最前面会让逻辑更清晰。我习惯把它写成一句continue表达式一旦命中冲突立即跳过避免多层嵌套。4.4 对称剪枝进一步减半搜索空间如果你追求极致性能可以观察N皇后问题的棋盘对称性。一个合法解经过水平翻转、垂直翻转或中心旋转后仍然是合法解。所以在搜索过程中可以在第0行只尝试列0到列(n-1)/2的范围把得到的解进行对称变换生成另一半解。严格来说对称剪枝在实现上有一些细节例如当n为偶数和时间中点重合的情况需要特殊处理。这个优化更适合竞赛或大n表演面试时提一嘴就够不建议为了它牺牲主代码的清晰度。4.5 大n场景下的替代方案最小冲突算法当n很大时比如n1000回溯算法即使有剪枝也跑不动因为解空间暴增。这时学术界常用局部搜索算法比如最小冲突算法随机放置n个皇后不断选择一个冲突数最大的皇后把它移动到当前列中冲突数最小的位置迭代直到冲突为0。最小冲突算法不是确定性算法它可能找不到解需要重启但平均效率极高号称能秒解百万级N皇后。这个算法不在LeetCode 51/52的答案范畴内但从“看懂回溯”到“理解暴力搜索的边界”掌握它的思路会让你对算法选型有更深的认识。4.6 常见问题速查表现象可能原因排查/修复结果全是同一个棋盘加入res时未生成快照用字符串join生成独立列表再加入对角线越界或冲突漏检row-col未加偏移或数组长度不对检查数组长度2n-1确认偏移n-1解的数量偏少某个合法列被错误跳过打印d1/d2值与手动棋盘对照递归次数爆炸剪枝放在递归函数内部而非循环前把合法性判断前置到for循环开头栈溢出n过大或递归深度过深大多数平台n15以下没问题超出再考虑非递归或局部搜索旋转或翻转解重复未做重复过滤的对称扩展不需要过滤51/52的标准解法不要求去重5. 把这些思路迁移到其他回溯题N皇后学明白之后你会发现回溯题有很多共性。比如LeetCode 46的全排列本质是逐位选择数字选择列表是剩余未使用的数LeetCode 39的组合总和本质是每层选择当前候选数中的某一个并允许重复选择LeetCode 37的解数独本质是按空格逐格填入1到9并用行列宫三个标记做剪枝。它们的模板都和N皇后一致确定路径数据结构、确定选择列表、确定结束条件、做选择、递归、撤销选择。不同题目区别只在“选择列表怎么生成”和“冲突条件怎么判断”。所以刷题时不要孤立地做N皇后把它当成回溯的标准件然后把全排列、组合、子集、数独都套到同一个模板里练习。一旦你不再背代码而是能自己推导出每一步的含义回溯题基本就没难题了。我个人在实际操作中的体会是N皇后最适合用来检验自己是否真的理解递归状态管理。如果你今天看懂了文章里的代码明天合上屏幕能自己在LeetCode 51上从空文件写到通过那说明回溯的框架已经长在你脑子里了如果还要边看边写建议再手动模拟两遍n4的决策树把每一步的进入、返回、撤销都画出来。这个看似笨办法的练习比抄十遍代码都管用。最后再分享一个小技巧。平时调试回溯题不要一味盯着LeetCode跑结果可以用一张小棋盘和几个不同颜色棋子做物理模拟。我在学习阶段就是拿8×8网格纸手动推演n4的两个解推完之后所有关于回溯的困惑都变得具体了。理解状态回溯的本质就是从一次失败尝试里干干净净地抽身出来然后下一次尝试依然从起点开始。
