回溯算法

1848 年，国际象棋棋手 Max Bezzel 提出了一个看似简单的问题：把 8 个皇后放在 $8 \times 8$ 棋盘上，使得没有两个皇后互相攻击。这个问题有多少种放法？

92 种——这个答案在当时用穷举法需要很长时间。但一旦引入系统性的"尝试-撤销"策略，效率可以提高几个数量级。这就是回溯算法的精髓。

回溯（Backtracking）是一种系统搜索所有可能解的算法策略。当某条路走不通时，它退回到上一步，尝试另一条路。它比完全暴力枚举聪明，因为在发现当前路径一定不会导向解时，就果断放弃这整个分支——这叫做剪枝（Pruning）。

破除误解：回溯不是"蛮力暴搜"#

很多人把回溯和暴力枚举混为一谈。区别很重要。

完全暴力枚举：生成所有可能的候选解，检查每一个是否是有效解。回溯：在构建解的过程中逐步检测——一旦发现当前部分解无法扩展为有效完整解，立即放弃，不生成该分支下的任何候选解。

对于 $n$ 皇后问题，暴力枚举所有棋盘放法是 $\binom{64}{8} \approx 4.4 \times 10^9$。回溯版本实际探索的节点远小于此——因为早在前几行放置时，大量分支已被剪去。下文会把这两个数字精确地摆在一起。

算法骨架#

回溯算法有一个统一的递归框架：

def backtrack(state, choices):
    if is_solution(state):
        record(state)
        return

for choice in choices: if is_valid(state, choice): make_choice(state, choice) # 做选择 backtrack(state, remaining_choices) undo_choice(state, choice) # 撤销选择（回溯） ```

这个框架对所有回溯问题通用，差别只在于：如何定义"状态"、如何判断"有效"、如何判断"是解"。

手算 4 皇后：把整棵搜索树走一遍#

$n=4$ 是最小的有解规模（$n=2,3$ 无解），整棵搜索树只有十几个节点，可以完整走完。规则：逐行放置，第 $r$ 行从左到右尝试列 $1,2,3,4$；一个候选位置合法的条件是它与已放置的皇后不同列、不同对角线（判据是 $|c_i - c| \neq r - i$）。

第 1 行放列 1（左上角开局）：

第 1 行放列 2（第一个解出现在这里）：

第 1 行放列 3（第二个解，与解 #1 左右镜像）：

第 1 行放列 4：与列 1 那一支左右镜像，同样走到底、同样无解。

整棵树的账：全程做了 60 次"这个格子能放吗"的判断，其中 16 次通过（即树上有 16 个合法的部分放置节点），找到 2 个解。而完全暴力枚举——把 4 个皇后随便放到 16 格里——是 $\binom{16}{4} = 1820$ 种，每种都要完整检查。60 比 1820，差 30 倍，而且规模越大差距越夸张。

这棵树最该注意的是第 3 步：部分解只有两个皇后 $(1,3)$，第 3 行就已经四列全废。此时第 4 行还没碰过一次，但它下面的 4 个分支已经全部被砍掉了——这就是剪枝的机制：在第 $k$ 层否决，省掉的是第 $k$ 层以下整棵子树。 越早否决，省得越多，所以剪枝判据的设计价值远高于常数优化。

剪枝到底剪掉了多少#

把同一个 $n=8$ 的问题用四种精细程度不同的枚举方式各算一遍，规模是这样的：

从 44 亿到 2056，是 215 万倍。 但这四行不是一个"优化了 215 万倍"的故事，而是四次信息注入：第二行用掉了"每行必有且只有一个皇后"，第三行用掉了"每列也只能有一个"，第四行用掉了两条对角线约束。每一条约束都不是加速技巧，而是把问题本身的结构告诉算法。 回溯的性能几乎全部来自这件事。

再看剪枝之后的增长速度（逐行回溯的合法放置节点数，可自行验算）：

相邻两列的比值是 3.3、2.9、3.6、3.7、4.1、4.2——仍然是指数增长，只是底数从 8 降到了约 4，而且还在缓慢上升。 这是关于剪枝最重要的一句判断：剪枝改变底数，不改变指数的存在。$n$ 皇后的解数本身就爆炸（$n=14$ 时 365 596，$n=20$ 时约 390 亿），任何"枚举全部解"的算法都躲不过。

对称性剪枝：一刀砍掉一半#

棋盘有左右镜像对称：若 $(c_1, c_2, \ldots, c_n)$ 是解，则 $(n{+}1{-}c_1, \ldots, n{+}1{-}c_n)$ 也是解。所以第 1 行只需搜索列 $1$ 到 $\lceil n/2 \rceil$，另一半的解由镜像直接得到。

在 $n=8$ 上实测：第 1 行限制在列 1–4，节点数从 2 056 降到 1 028，找到 46 个解，乘 2 恰好还原成 92。上文 $n=4$ 的走查也一样——只搜列 1、2 两支就够，节点数从 16 降到 8，找到 1 个解，镜像出另一个。

不多不少正好一半，原因是 $n$ 为偶数时不存在"自己镜像等于自己"的第一行列号。$n$ 为奇数时中间那一列是自镜像的，那一支不能乘 2，得单独处理——对称性剪枝的坑几乎总在这种"不动点"上。

经典案例#

$n$ 皇后问题#

在 $n \times n$ 棋盘上放 $n$ 个皇后，要求没有两个皇后共行、共列、共对角线。

回溯思路：逐行放置，每行选一个列。放第 $i$ 行时，检查是否与前 $i-1$ 行的皇后冲突。若冲突，换下一列；若本行所有列都冲突，则回到第 $i-1$ 行换位置。

用位运算优化：三个整数分别记录已被占用的列、正对角线、反对角线，"本行还能放哪些格"就是 ~(cols | d1 | d2) 的低 $n$ 位，取最低置位 avail & -avail 就是下一个候选。这样每层的合法位置一次算出，冲突检测从 $O(n)$ 的循环变成常数次位运算——上文表格里的所有节点数都是用这个写法跑出来的。

$n$ 皇后问题的解数：$n=8$ 时 92，$n=14$ 时 365596，$n=20$ 时高达 39029188884（约 390 亿）——增长极快，验证了问题的搜索空间难以避免地指数级扩张。

数独求解#

数独是约束满足问题（Constraint Satisfaction Problem，CSP）的典型。回溯策略：

1. 找一个还未填写的格子（启发式：优先选"候选数字最少"的格子——最小剩余值启发式，MRV）
2. 依次尝试每个候选数字（1-9）
3. 如果数字不违反约束（行/列/3×3块中不重复），递归继续
4. 如果所有候选数字都不行，回溯到上一步

附加约束传播（Constraint Propagation）：每次填入一个数字时，更新相关格子的候选列表，能进一步剪枝。

子集和问题#

给定整数集合 $S$ 和目标值 $T$，找是否存在子集使得元素之和恰好等于 $T$。

回溯思路：对每个元素，选择"包含"或"不包含"，逐步构建子集。剪枝：当前已选元素之和超过 $T$，或剩余元素全选也不够 $T$，立即回溯。

这是 NP 完全问题的一个实例，回溯给出精确解但最坏情况指数时间。

图着色#

$k$ 图着色：给图的每个节点着色，使相邻节点颜色不同，最多使用 $k$ 种颜色。同样是 NP 完全问题。回溯逐节点枚举颜色，剪枝条件：当前节点的颜色已被相邻节点使用。

现场：数独求解器的真实数字#

Peter Norvig 在 2006 年那篇《解开每一个数独》（Solving Every Sudoku Puzzle）里做的事，是把"约束传播 + 回溯"这套组合的效果量化到可复现的程度。他的求解器主体约一页 Python 代码，用两个机制：

1. 约束传播：填入一个数字后，把它从同行、同列、同宫所有格子的候选集里删掉；如果某格候选只剩一个，立刻填上并继续传播；如果某个单元里某个数字只剩一个可能位置，也立刻填上。这两条规则会连锁反应。
2. 搜索：传播停下来后仍未解出，就选候选数最少的空格（MRV），逐个候选试，试错就回溯。

关键数字（都出自那篇文章的实测）：

更能说明剪枝威力的是这一条：在那 95 道难题上，求解器平均只需要考察 25 个可能性，而且需要真正展开搜索的格子从来不超过 9 个（题目平均有 61 个空格）。也就是说，六十多个空格里，五十多个是被约束传播直接推出来的，回溯只在剩下不到十个格子上工作。 一个数独的原始候选空间在这篇文章里被算到约 $4.6 \times 10^{38}$，压到 25 次考察——这不是"搜索快"，这是"绝大部分搜索被推理消灭了"。

失败现场：重尾分布#

同一篇文章里还有一个数字，是本节最值得记住的：Norvig 拿他生成的一道最难的题，把"候选数字的尝试顺序"改成随机，跑 30 次。结果不是"平均 6 秒"，而是27 次在 0.02 秒内完成，另外 3 次各花了约 190 秒——快慢相差近一万倍，而算法、题目、代码完全相同，只有随机顺序不同。

这就是回溯搜索著名的重尾（heavy-tailed）运行时分布：绝大多数运行极快，少数运行陷进一个巨大的无解子树里长时间出不来。Gomes、Selman、Crato 与 Kautz 在 2000 年的《自动推理杂志》上系统刻画了这个现象，并指出它的分布可以重到均值都不存在（无穷矩）——"平均运行时间"这个说法在这里字面上失去意义。

他们也给出了对策，而且极其朴素：随机重启（random restart）。跑一段时间没出结果就丢掉当前搜索、换个随机顺序重来。既然 27/30 的运行都在 0.02 秒内结束，那么"每 1 秒重启一次"几乎必然在几秒内命中一次快的运行，而不必赌那 190 秒的一支。今天所有严肃的 SAT 与 CSP 求解器都内置重启策略，源头就是这个观察。

该记住的判断：对指数级搜索算法，运行时间的方差比均值更值得关心。一个"平均很快"的求解器如果尾部厚，在生产环境里就会表现为随机的、无法复现的超时。

剪枝策略#

剪枝是回溯算法性能的核心。主要策略：

前向检验（Forward Checking）：每做一个选择，立即更新其他变量的候选域。若某变量的候选域变空，当前路径一定无解，立即回溯。

弧一致性（Arc Consistency）：比前向检验更强的约束传播，确保每对约束都一致。AC-3 算法（Mackworth 1977）是标准实现。

启发式排序：

• 最小剩余值（MRV）：优先处理候选最少的变量（最紧迫的变量）
• 度启发式（Degree Heuristic）：选约束最多的变量（对其他变量影响最大）
• 最少约束值（LCV）：选对其他变量限制最少的值（保留最多自由度）

这三条启发式的方向不一样，值得点明：MRV 和度启发式决定先处理哪个变量，目标是尽早失败（fail first）——因为失败越早，被砍掉的子树越大，正是上文第 3 步的道理。而 LCV 决定先试哪个值，目标相反，是尽量成功——先试限制最少的值，让后面的变量还有路可走。"选变量要悲观，选值要乐观"，这是 CSP 求解里最容易记混、也最常被写反的一对启发式。

回溯与动态规划的界限#

有一类问题横跨两种策略：

• 精确计数/枚举所有解：必须回溯（无法用 DP 避免指数空间）
• 最优化（找最优解的值）：若有重叠子问题，用动态规划更快
• 判断是否存在解：有时可以用 DP 避免指数时间

0-1 背包可以用 DP 的原因是：只关心"最大价值是多少"，子问题重叠可记忆化。若要枚举所有装法，则需要回溯。

计算复杂度与 NP 完全#

回溯算法完美胜任的问题，往往是 NP 完全问题：理论上没有多项式时间算法（在 P ≠ NP 假设下，见 p-vs-np），但回溯可以在实践中通过好的剪枝和启发式处理中等规模实例。

血缘：SAT 求解器就是带学习的回溯#

布尔可满足性（SAT）求解器是这一领域工程的巅峰，而它的骨架从头到尾就是回溯。

1962 年，Martin Davis、George Logemann 与 Donald Loveland 在《ACM 通讯》上发表《一个用于定理证明的机器程序》，给出了后来被称为 DPLL 的算法（名字里的 P 来自 1960 年 Davis 与 Putnam 的前作）。它的结构与上文那个八行的回溯骨架一一对应：选一个还没赋值的变量（选变量启发式），赋 true 或 false（做选择），做单元传播（unit propagation：某个子句只剩一个未赋值文字时，它的取值被强制——这就是约束传播），出现空子句就回溯。数独求解器和 SAT 求解器不是"相似"，是同一个算法在不同约束语言上的实例。

1996 年，Marques-Silva 与 Sakallah 的 GRASP 求解器加进了改变一切的一层：冲突驱动的子句学习（Conflict-Driven Clause Learning, CDCL）。朴素回溯撞墙后只是退回上一层换个值，把"为什么撞墙"的信息扔掉了；CDCL 则分析这次冲突，推导出一条新的子句（"这几个变量不能同时取这些值"）加进公式，然后非时序回跳（non-chronological backjumping）——直接跳回真正相关的那一层，而不是老实退一格。学到的子句会在整个后续搜索里持续剪枝，等于搜索过程一边走一边给自己加约束。

效果的量级：1990 年代末，能解的公式规模是几千个变量；今天的 CDCL 求解器例行处理数百万到上千万个变量与子句的工业实例。这个提升里几乎没有渐进复杂度上的改进——SAT 仍然是 NP 完全的，最坏情况仍是指数——全部来自子句学习、重启策略、变量活跃度启发式（VSIDS）和数据结构（watched literals）这些"工程"。

这件事的意义超出算法本身：芯片形式验证、程序模型检查、依赖包版本求解（apt、cargo、pip 的求解器背后常常就是 SAT 或它的近亲），都建立在"NP 完全但实际可解"这个反直觉的事实上。NP 完全说的是最坏情况；而真实世界的实例带着大量结构，回溯 + 学习正好吃这种结构。

跨域连接#

• 组合数学：剪枝改变的是指数的底数，不是指数本身。逐行放置加上两条对角线约束把八皇后的搜索底数从八压到四上下，增长仍然是指数的，而解的数量本身就在爆炸。这条判断划定了剪枝的天花板：约束能压低底数，压不掉问题的组合规模，凡是要枚举全部解的算法都躲不过。
• SAT 求解：DPLL 的骨架与回溯完全一致——选变量、赋值、单元传播、遇冲突退回，只是把约束换成了子句。真正改变量级的是冲突驱动的子句学习：分析这次冲突推出一条新子句加进公式，等于搜索一边走一边给自己加约束，并跳回真正相关的那一层。渐进复杂度没变，能解的规模涨了几个数量级。
• 逆合成分析与反应优化：逆合成把目标分子往回拆，是典型的高分支因子搜索，可用反应成千上万条。剪枝判据在这里是化学而非算法：拆出的中间体必须可得、官能团必须相容、保护基策略必须自洽，任一条不满足就砍掉整棵子树。搜索效率几乎全部来自这些判据的质量，与遍历顺序关系不大。
• 蛋白质设计革命：侧链构象的组合同样指数爆炸，标准剪枝判据是"无论其余部分怎么选，这个局部选择都不可能出现在最优解里，就删掉它"。这与部分解否决是同一条原理，区别在于它要求能量函数可加，才能做出这种局部判断。能量项一旦不可分解，剪枝失效，只能退回随机搜索。
• 心理语言学加工：人在句法歧义处会做出承诺，遇到不兼容的续接时必须重新分析，花园路径句正是这种回溯的证据。而且它可测量：重新分析处的注视时间与阅读时间显著延长。这说明人的解析器不是并行保留全部分析的，而更接近带承诺与回溯的深度优先——与"下棋时一条线走到底"的自省一致。

参考文献#

• Cormen, T. et al. Introduction to Algorithms (CLRS). 4th ed. MIT Press, 2022.
• Knuth, D. "Dancing Links." arXiv:cs/0011047, 2000. （精确覆盖问题的回溯实现）
• Davis, M., Logemann, G. & Loveland, D. "A Machine Program for Theorem-Proving." Communications of the ACM 5(7), 394–397 (1962).（DPLL）
• Marques-Silva, J. P. & Sakallah, K. A. "GRASP: A Search Algorithm for Propositional Satisfiability." IEEE Transactions on Computers 48(5), 506–521 (1999).（冲突驱动子句学习与非时序回跳）
• Gomes, C. P., Selman, B., Crato, N. & Kautz, H. "Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems." Journal of Automated Reasoning 24(1/2), 67–100 (2000).（重尾运行时分布与随机重启）
• Mackworth, A. K. "Consistency in Networks of Relations." Artificial Intelligence 8(1), 99–118 (1977).（弧一致性与 AC-3）
• Norvig, P. "Solving Every Sudoku Puzzle." norvig.com, 2006.（约束传播 + 搜索的实测数据：95 道难题平均 0.04 秒、平均考察 25 个可能性、随机化后的重尾现象）

延伸阅读#

• Russell, S. & Norvig, P. Artificial Intelligence: A Modern Approach. 4th ed. Pearson, 2020. （第6章 CSP，MRV / 度启发式 / LCV 的完整讨论）
• Biere, A., Heule, M., van Maaren, H. & Walsh, T. (eds.) Handbook of Satisfiability. 2nd ed. IOS Press, 2021.（CDCL 的权威综述）
• Knuth, D. The Art of Computer Programming, Volume 4B: Combinatorial Algorithms, Part 2. Addison-Wesley, 2022.（第 7.2.2 节"回溯程序设计"把回溯当作独立主题系统处理，大量例子取自谜题与游戏，$n$ 皇后是其中之一）