递归、回溯、剪枝这三个词分开看很多朋友觉得自己早就掌握了递归不过是一个函数自己调用自己回溯不过是在递归前后改一次状态剪枝也不过是提前 return但真到了综合题里它们互相嵌套、互相影响的时候代码就很容易越写越乱。这篇是“算法奇妙屋”第三十一篇也是递归、回溯与剪枝专题的第四个综合问题。前三个综合问题分别讲了组合类搜索、路径类搜索和带约束的排列这第四篇我特意挑了一个“看着规则简单、做起来五脏俱全”的经典题N 皇后。N 皇后适合做这个专题的收尾题是因为它不像纯模板题那样背下来就能过。你在每一行选择放皇后的列但每一列、每一条主对角线、每一条副对角线都不能再出现第二个皇后这直接逼着你同时处理递归、回溯、剪枝三个动作。更妙的是这题可以做得很难——从布尔数组检查到位掩码优化再到对称剪枝、约束传播每一步都能把性能往上推一个数量级。只要你把这题吃透后面的解数独、图着色、排课表、任务分配本质都是同一套骨架。所以这篇文章我不想只给一个答案而是把整个思考链路写清楚为什么状态要这么设计、剪枝的约束从哪来、递归栈在失败时到底发生了什么、代码里哪些位置最容易写错。新手可以照着抄有经验的也能在“复杂度直觉”和“通用化”这两节里再核对一下自己的理解。1. 综合题的选材N 皇后到底考了你哪几块本事1.1 一个约束满足问题的最标准长相N 皇后的题面你背都能背出来在一个 N×N 的棋盘上放置 N 个皇后任意两个皇后都不能处于同一行、同一列或同一条斜线上。题目可能让你输出所有摆放方案也可能只让你数方案个数还可能让你只输出任意一个可行解。问题看似是棋盘问题但把它剥开它其实是一个标准的约束满足问题Constraint Satisfaction ProblemCSP。所谓约束满足问题就是有一堆变量每个变量有若干可选值变量之间存在硬性约束。放在 N 皇后里变量是每一行的皇后到底选哪一列可取值是 0 到 N-1约束是任意两行之间的列号不能相等它们的行号差也不能等于列号差的绝对值。学过 CSP 的人会立刻意识到这题完全可以用通用的回溯搜索模板去解甚至可以直接套用前向检查、弧一致性这些更高级的约束传播手段。之所以说它适合放在“综合问题 4”这个位置是因为它把递归的“状态设计”和剪枝的“约束建模”捆绑在了一起。你如果不能把“两个皇后不能同斜线”翻译成程序里的下标运算那写出来的递归函数就会有一大堆 for 循环逐格检查复杂度直接爆炸。反过来如果你能准确建模剪枝写起来会非常顺手每走一步只需要判断当前选择的列、主对角线、副对角线是否被占用。这个“翻译”过程就是综合题和模板题最大的区别。1.2 先算清楚暴力枚举的账很多人觉得 N 皇后没必要剪枝因为 N 小时候暴力也能算。我们用数字看一下这个错觉是怎么来的。如果完全不管约束把所有皇后任意放在空位上那么从 64 个格里选 8 个位置放皇后组合数是 C(64,8)精确值是 4,426,165,368约 44 亿。44 亿次操作在现代电脑上也许能硬扛但如果你还要判断斜线冲突每多一个判断时间就翻几倍而且这还只是 N8。稍微聪明一点利用“每行只能有一个皇后”的性质把搜索空间从“选格子”变成“逐行选列”。这样 N8 的候选解只有 8! 40320 个叶子N10 是 10! ≈ 3.63×10^6N12 是 12! ≈ 4.79×10^8到 N20 已经是 20! ≈ 2.43×10^18。你会发现即使按行枚举N 每增加 1工作量都近似乘 N。如果不剪枝N12 的 4.79 亿个排列光生成出来就要好一阵更别说还要逐格判断冲突了。而一个带完整剪枝的递归回溯在 N12 时通常能在一两秒内跑完所有解。差别不在机器而在搜索树的形状暴力枚举把所有叶子都走一遍回溯加剪枝却能在叶子出现之前就把不可能的分支砍掉。所谓“剪枝”不是优化彩蛋而是暴力搜索能够继续活下去的生命线。2. 先搭递归骨架把“放棋子”表达成逐行选择2.1 状态怎么设计递归才好写写递归第一个问题永远是函数参数传什么很多初学者喜欢把整个棋盘传进去结果函数签名又长又难读。N 皇后里一个更好的办法是只传“当前要处理的行号 row”然后把已经占用的信息放在外部数组里。为什么这样设计因为从第 0 行开始每一行一行往下放天然形成了一个“顺序”。当程序执行到 dfs(row) 时第 0 行到第 row-1 行已经各放了一个皇后后面的行还没处理。这个信息用 row 一个参数就表达了。至于已经放了哪些列、哪些对角线被占用全局的布尔数组维护即可。递归函数是访问这些数组而不是把棋盘整个拷贝一份。这里的核心思想是状态变量不要面面俱到只保留“决策到哪一步了”和“有哪些约束被触发过”。在更复杂的搜索问题里也是同理。如果你发现递归函数里同时传了 started、visited、count、path、sum 等一大堆参数通常意味着状态设计还不够收敛先花几分钟想想能不能把部分信息组织成共享数组。2.2 递归主体、终止条件和解收集一个都不能混递归函数的结构非常固定就是三段式的终止条件、遍历候选、递归与撤销。对于 N 皇后伪代码可以写成def dfs(row): if row n: # 终止所有行都放完 记录方案 return for col in range(n): # 遍历当前行的每一个候选列 if 当前位置合法: 放置皇后更新占用标记 dfs(row 1) 撤销皇后恢复占用标记这个结构你可能见过无数次但请特别注意两个容易混的点。第一终止条件必须放在候选循环之前。每放完一行就进入下一层递归自然会出现 row n 的时刻这个时刻并不是代表第 n 行有皇后而是代表 0 到 n-1 行已经全部放好了。很多人把终止条件写成if row n: return但不记录方案最后跑出来解是空的就是因为忘了“到达终点也是一次合法方案的完成”。第二终止条件里记录方案时必须把当前棋盘的“快照”保存下来而不是保存棋盘对象的引用。这个问题第六节还会细说这里是所有回溯题最容易踩的坑回溯之后棋盘变了之前“保存”的也一起变了。2.3 为什么这里注定是递归而不是多重循环有人可能会问逐行选列N8 时不就是八个嵌套 for 循环吗N 固定为 8 的时候确实可以写八层循环硬枚举然后里面加判断。可一旦 N 是变量你就没办法在代码里动态写出 N 层 for。递归在这里的本质是“循环层数不确定时的替代方案”每一层递归处理一行有多少行递归就压多少层。理解这个点对后面所有搜索类题目都有帮助。排列、子集、组合、数独、图着色凡是“要选择的数量”不固定选择空间又层层相扣第一反应就应该是递归 回溯而不是试图用 while 循环去模拟一个随时变化的嵌套深度。3. 剪枝的三板斧约束冲突、对称去重、顺序优化3.1 用数组把“不同列、不同斜线”变成 O(1) 判定N 皇后剪枝的核心是把“是否冲突”的判断从扫描整个棋盘降成一次数组访问。这需要三个数组列占用数组 cols主对角线占用数组 diag1副对角线占用数组 diag2。关键在于斜线的下标映射。在一个棋盘上如果把坐标记为 (row, col)那么所有落在同一条主对角线左上到右下上的格子row - col 的值是固定的所有落在同一条副对角线右上到左下上的格子row col 的值是固定的。 diag1 和 diag2 的长度都应该是 2*N-1因为 row - col 的范围是 -(N-1) 到 N-1row col 的范围是 0 到 2N-2。为了把负数的 row - col 也当成数组下标用通常在存取 diag1 时做一次平移d1 row - col n - 1。这样 d1 的范围正好落在 [0, 2n-2]。副对角线直接d2 row col不需要额外处理。所以一次合法性判断就变成if cols[col] or diag1[row - col n - 1] or diag2[row col]: continue列冲突用 O(1) 判断两条斜线冲突也用 O(1) 判断。这个优化看起来不起眼但它决定了整个搜索过程中的单节点成本。如果不建模而是每次在 for 循环里检查“前面每个皇后是否和当前格子同斜线”每个节点都要付出 O(row) 的检查时间累计起来就是数量级的差距。3.2 对称去重的边界很多 N 皇后的进阶教程都会告诉你可以用对称性剪枝每一行放置皇后时只扫描一半的列因为棋盘关于竖轴对称所以第一行的皇后放在第 0 列和解放在第 N-1 列是镜像关系。这个思路本身没错但要注意它的适用场景。如果你只需要“找到任意一个解”那当然可以在第一行只试前一半列找到之后立刻返回。如果你需要“数出所有不重复的、本质不同”的解那对称去重也能用但必须处理奇数 N 时中心列带来的特殊情况而且最后要把镜像关系算清楚不然会多数或者少数。但如果题目要求“输出所有解”那通常不要去对称剪枝因为镜像是两个不同的解题目要求的就是输出完整的解集合。我在初学阶段犯过这个错为了追求效率强制第一行只放前一半列结果 N4 只输出 1 个解丢了它的左右镜像。效率是上去了答案却错了。剪枝永远是“在不改变答案集合的前提下删掉无用分支”如果删掉的是“有用的解”那叫 bug不叫优化。3.3 搜索顺序本身也是剪枝机会在 N 皇后里大多数人习惯从第 0 行一路放到第 N-1 行。这个顺序符合直觉但不是唯一的。在更一般的 CSP 问题里有个非常有效的策略叫 MRVMinimum Remaining Values每次优先选择当前可选值最少、约束最强的变量去尝试。N 皇后也可以借鉴这个思想当你放了前几行之后后面的行可选的列会越来越少。也就是说后面的行其实是“更拥挤”的变量。如果你从最拥挤的行开始搜索往往能更快地发现冲突。实际做法之一是把行的处理顺序重新排一下比如先处理棋盘中间的行因为它们受两侧限制更大或者动态选择当前可选列最少的那一行。当然标准逐行递归的写法已经隐含了一部分 MRV 效果越到后面剩余行能放的位置越少。因此 N 皇后未必需要显式重排行顺序。但理解这层逻辑之后你就明白为什么在解数独这类题里优先填“候选数最少”的空格能产生那么大的加速。搜索顺序不是执行细节而是和剪枝同等重要的策略。4. 回溯栈现场一次失败的尝试是如何“退回去”的4.1 N4 的一小段探索轨迹拆解N 皇后说“回溯”很抽象我们直接跟一趟 N4 的探索过程看看调用栈内部到底发生了什么。假设程序按这样的顺序尝试第 0 行先放第 0 列进入第 1 行第 1 行检查第 0、1 列都存在冲突于是放第 2 列进入第 2 行之后遍历 0、1、2、3 四个列发现全被占用于是当前这个 dfs(2) 函数正常跑完退出返回到 dfs(1)。此时第 1 行刚刚放的皇后需要被撤销然后把第 1 行的列游标移动到 3再往下一层探索。我把这个过程简化成一张对照表当前行动作发生了什么0放 col0进入第 1 行1试 col2进入第 2 行2四个列全冲突dfs(2) 结束回到第 1 行1撤销 col2试 col3进入第 2 行2放 col1进入第 3 行3四个列全冲突dfs(3) 结束回到第 2 行2其余列也不可行回到第 1 行1撤销 col3本行无剩余列回到第 0 行0撤销 col0试 col1继续找最终得到一组解这里的关键点在于第 2 行出现冲突时并不是程序主动“知道”应该回退而是 dfs(2) 的 for 循环天然跑完了函数自己 return于是控制权被动回到了上一层。这个“函数自己跑完返回”的机制就是递归实现回溯的根本原因。你不需要写一个跳转语句递归调用栈天然帮你记住了上一步的现场。4.2 传参恢复与原地撤销两种写法的取舍回溯的状态恢复有两种常见思路。第一种是把全部状态作为参数往后传下一层递归拿到的是新数组回到上一层时自然“旧状态”还在不需要显式撤销。第二种是共用一份数组进入递归前修改递归返回后再改回来。N 皇后标准解法里用的是第二种因为共享数组可以避免大量拷贝性能好但代价是你必须保证每一步递归返回后都执行撤销动作。我自己的习惯是修改共享数组时把“赋值”和“恢复”紧贴着 dfs 调用写中间不要夹任何可能提前 return 的逻辑。例如board[row][col] Q cols[col] diag1[...] diag2[...] True dfs(row 1) board[row][col] . cols[col] diag1[...] diag2[...] False这样写的好处是一目了然进入递归前变了几样东西出来之后马上原样恢复。如果中间出现别的分支极容易漏恢复一旦漏掉这个数组就被污染了后面的分支全都判断出错而且这种错误非常难定位。5. 可复制的完整代码和它背后的通用搜索框架5.1 完整 Python 求解器直接跑下面这段代码是 N 皇后最直接的实现没有位运算、没有对称剪枝只保留最核心的三个布尔数组和一行一行递归。它足够稳也容易读懂适合作为综合题的参考实现。def solve_n_queens(n): cols [False] * n # 列是否被占用 diag1 [False] * (2 * n - 1) # 主对角线row - col n - 1 diag2 [False] * (2 * n - 1) # 副对角线row col board [[.] * n for _ in range(n)] solutions [] def dfs(row): if row n: solutions.append([.join(line) for line in board]) return for col in range(n): if cols[col] or diag1[row - col n - 1] or diag2[row col]: continue board[row][col] Q cols[col] True diag1[row - col n - 1] True diag2[row col] True dfs(row 1) board[row][col] . cols[col] False diag1[row - col n - 1] False diag2[row col] False dfs(0) return solutions如果你只需要求“任意一组解”可以在solutions.append之后立刻 return True并且递归函数返回 True 时直接终止如果你要全部解就用上面的收集方式。这个区别我在第六节还会强调因为这里的改动虽然小影响却很大。5.2 实测表现N8/10/12 会怎样把代码跑起来N8 会得到 92 个解N10 是 724 个N12 是 14200 个。这个数据本身就是检验程序正确性的好手段。如果你写出来的 N8 不是 92那一定哪里出了问题不用等面试官提醒。用纯 Python 跑这段代码N8 几乎是瞬间完成N10 通常在一秒以内N12 到 N14 就开始明显变慢。因为 Python 本身循环和函数调用的开销比较高所以如果你想挑战更大的 N比如 N20 以上就要考虑继续优化用位掩码代替三个布尔数组用整数的与或非运算一次算出所有可用列这样常数会小很多也能配合预占位等策略。N标准解数量暴力按行排列叶子数剪枝后的搜索量级89240320万级107243.63×10^6十万级12142004.79×10^8百万级20——2.43×10^18不是普通回溯能扛的这张表想说明一个朴素但重要的道理剪枝改变了搜索趋势但没有改变指数级的本质。数据规模一大单靠回溯仍然不够必须引入更高级的约束传播或启发式甚至换思路。但凡是 N 在十几量级的搜索题上面这个递归 剪枝框架就是最可靠的答题模板。5.3 从 N 皇后提取“回溯 剪枝”通用模板N 皇后做完之后最有价值的动作是把它背后的通用框架抽出来这才是“综合问题”真正希望训练的能力。所有能用回溯解决的问题都长这样def backtrack(assignment): if is_complete(assignment): record_solution(assignment) return var select_unassigned_variable(assignment) for value in order_domain_values(var, assignment): if is_consistent(var, value, assignment): apply(var, value, assignment) backtrack(assignment) undo(var, value, assignment)解数独时var是一个空格order_domain_values是它的候选数字集合图着色时var是一个顶点候选值是颜色集合排课表时var是一门课候选值是时间与教室组合。所谓综合问题考的就是你在新问题里能不能重新定义这四个函数完成判断、未分配变量选择、候选值排序、合法性检查。N 皇后的四个函数极其清晰已完成 所有行都放了未分配变量 下一行候选值 0 到 n-1 的列合法性 三个布尔数组的占用情况。你如果把 N 皇后的代码背得再熟而不理解这层抽象下一道题换个马甲就又不会了。这就是我一直强调“综合题 4”选 N 皇后不是为了做题而是为了把这个“接口”牢牢刻在脑子里。6. 我反复写错过的几个位置含排查经验6.1 对角线索引换算N 皇后最容易翻车的地方是主对角线的下标。很多人写成diag1[row - col]但 N 小于 3 的时候可能不报错N 一变大就出现数组越界或者更糟的是在 Python 里不越界也不报错而是用负索引悄悄访问了数组尾部导致搜索结果看起来“正常”其实是错的。负索引的问题是隐蔽的因为程序不会抛异常你必须自己意识到 row - col 可能出现负数并且需要平移 N-1 才能变成非负下标。排查这个问题的经验是先用 N4 手动跑通确保输出 2 个解。然后换 N5 验证 10 个解。如果 N4 输出少了解大概率是某条斜线的下标映射错误或者没被正确恢复。别一上来就用 N8 调试解太多反而看不出问题。6.2 保存解时的引用陷阱这可能是所有回溯题里最典型的坑。如果你写solutions.append(board)那你会得到一排长得一模一样的解因为board是一个列表对象后面回溯时所有.和Q的修改都会反映到同一个对象上。等整个搜索结束solutions里存的其实是同一个棋盘最终的样子。正确写法是生成行的不可变快照solutions.append([.join(row) for row in board])因为.join(row)每次都会生成一个新字符串等于把当前状态拷贝了下来。我更推荐在每一行是列表的情况下用这个方式而不是用copy.deepcopy(board)后者又慢又没必要。凡是深度超过一层的容器保存解的时候都要多问自己一句我存的是引用还是副本6.3 剪枝与递归顺序倒置导致的诡异结果最后一个高频错误是把递归调用和撤销动作的顺序写反。比如有人在递归调用之前就把标记恢复了board[row][col] Q dfs(row 1) board[row][col] . # 如果这行写到了 dfs 之前这会导致当前层搜索还没完成下一层递归看到的棋盘就已经不包含当前皇后了于是同一条斜线上可能出现两个皇后程序却当作合法解。这类 bug 的表现是N4 输出一堆“看起来很像解但其实有冲突”的棋盘而且每次结果还不一样。我的排查习惯是在一个小数据下把递归返回后的打印打开检查“进入第 row 层时棋盘长什么样”。如果皇后少了先去看是不是撤销过早如果皇后多了先去看是不是忘了撤销。很多回溯题的诡异行为最后都能归到“状态恢复的时机”这件事上。最后再分享一个小技巧写回溯代码时尽量把“放置、递归、撤销”这三行紧紧贴在一起中间不要插任何无关判断。剪枝判断放在它们之前结果记录放在递归返回之后。这个顺序一旦稳定下来你会发现自己写搜索类题目的出错率会明显下降。这是我在反复改 N 皇后这个综合题时收获最大的一点。