第 10 章

回溯算法——1848年，一位棋手提出了连高斯都没能完全解开的谜题

正在加载交互实验…

第一季 · 人类如何驯服数据

历史主线：1848—1972年 · 八皇后、数学穷举、搜索树与结构化程序设计1848年，德国柏林。欧洲正处在一个动荡的年代。政治革命、工业化和科学研究正在改变社会。就在这一年，一份德国国际象棋杂志刊登了一道看起来很简单的题目。在一张普通的8×8国际象棋棋盘上，放置八个皇后。要求它们彼此不能攻击。听起来像是一个稍微复杂一点的棋盘游戏。但它很快吸引了数学家的注意。甚至连当时欧洲最著名的数学家之一——Carl Friedrich Gauss（卡尔·弗里德里希·高斯），也对这道题产生了兴趣。高斯尝试计算所有可能的答案。他找到了一批正确的排列。可是，他没能找全。真正令人惊讶的是：这道题并不难验证答案，却很难证明已经找到了全部答案。一个世纪之后，当计算机科学家重新研究它时，这个问题成为了讲解一种强大算法思想的经典范例。这种思想就是：Backtracking——回溯。它的核心不是永远向前。而是知道什么时候应该撤销自己的决定。

第一幕：1848年，一位德国棋手留下了一个谜题

Max Bezzel

1824—1871 · 德国国际象棋棋手、棋题创作者他不是因为建立某个庞大的数学理论而出名，而是因为1848年发表的一道棋题，后来持续影响了数学与计算机科学。

1848年，Bezzel 在柏林的国际象棋杂志 Schachzeitung 上提出八皇后问题。这件事的意义在于：它把一个棋盘摆放问题，变成了可以系统研究的组合数学问题。国际象棋中的皇后很强大。它可以沿着横线、竖线、对角线移动任意格数，只要道路没有被其他棋子阻挡。因此，两位皇后如果位于同一行、同一列或同一条对角线上，就会互相攻击。现在要求在64个格子上放置八位皇后，使任何两位都无法攻击彼此。^{[美国数学学会][ajedrezlatitudsur.wordpress.com]}

皇后的攻击范围

♛

皇后位于第4行第4列。标出的其他格子都处于它的攻击线上。

如果只需要摆出一种合法布局，经过一些尝试，也许并不难。但是，Bezzel 的问题很快被研究者推向了更深的一层：究竟有多少种不同的合法布局？这就不再是一个普通的棋盘谜题。而是一道完整的搜索与计数问题。

第二幕：1850年，高斯为什么没能找全答案？

时间来到1850年。这一年，另一位研究者 Franz Nauck 在莱比锡的 Illustrirte Zeitung 中再次提出了八皇后问题。Nauck 最初发表了一批解，后来在同年9月将其修正、扩充为92种摆法。与此同时，高斯也通过阅读相关报道与通信接触了这个问题。根据历史研究，高斯一度找到了76种候选排列，随后发现其中4种重复，因此剩下72种。而 Nauck 给出的数量是92。^{[ajedrezlatitudsur.wordpress.com][美国数学学会]}也就是说，即便是高斯这样杰出的数学家，在当时的手工枚举中，也没有找全所有答案。这不是因为他不懂数学。而是因为“找出若干答案”和“保证没有遗漏任何答案”，是两种不同的任务。

历史上甚至还出现过一次误传

1874年，数学家 J. W. L. Glaisher 在讨论八皇后问题时，把问题的最初提出者错误地归给了 Nauck，并留下了可能使后人误认为高斯已经完整解决问题的记述。1977年，数学史研究者 Paul J. Campbell 专门发表文章：Gauss and the Eight Queens Problem: A Study in Miniature of the Propagation of Historical Error即《高斯与八皇后问题：历史错误传播的一个小型案例》。论文说明：1848年的 Bezzel 才是现有文献中更早的提出者，而高斯只是进行了不完整的尝试。^{[ajedrezlatitudsur.wordpress.com]}这一段历史有两层意义。第一，数学天才也会在复杂枚举中漏掉情况。第二，科学史本身也需要验证，不能因为某个说法流传很广，就把它当作事实。

究竟有多少个答案？

全部合法布局

92

排除旋转、镜像重复后的基本类型

12

92是把不同棋盘位置都算作不同解的数量。但如果一个布局旋转90度、180度，或者进行镜像翻转，可以得到另一个布局，那么从对称性角度看，它们属于同一类。这样合并之后，只剩12种基本解。^{[整数数列在线百科全书]}而让计算机系统地枚举全部92种解，正是回溯算法的经典任务。

第三幕：一道只有64个格子的题，为什么如此难以穷举？

假设你是一位生活在1850年的数学爱好者。你没有计算机。面前只有一张棋盘、一支铅笔和一叠草稿纸。你可能想：“64个格子，放八个皇后，不就是从64个位置里挑出8个吗？”如果完全不考虑任何攻击条件，所有选法的数量是：

\binom{64}{8}=4,426,165,368

超过44亿种！如果每秒能够检查一种排列，也需要约140年才能全部检查完。当然，数学家不会真的这样做。因为我们可以先观察问题本身，排除大量不可能的排列。

第一次压缩：每一行只能放一个皇后

八个皇后不能在同一行。棋盘正好有八行。因此，每一行必须恰好放一个皇后。同样，每一列也必须恰好有一个皇后。既然每行每列都只能有一个皇后，那么合法排列一定对应一种列编号的排列。例如：

queens = [0, 4, 7, 5, 2, 6, 1, 3]

它表示：第0行放第0列。第1行放第4列。第2行放第7列。以此类推。八个互不重复的列编号，总共有：

8!=40,320

种排列。从44亿多，突然下降到40320。我们还没有开始搜索，仅仅利用问题约束，就让候选空间缩小了十万倍以上。

第二次压缩：一旦出现冲突，就不再向下探索

现在假设我们已经放置了三位皇后。准备放第四位。如果第四位与之前某位皇后位于同一条对角线，那么这个布局已经不可能成为合法答案。因为后面继续放置第五、第六、第七、第八位皇后，也无法消除当前的攻击关系。因此，我们完全没有必要继续。应该立即撤销第四位皇后，尝试另一个位置。如果这一行所有位置都不合法呢？那就退回上一行。移动第三位皇后。这就是回溯。它与普通暴力枚举最大的区别，并不在于是否尝试很多可能性。而在于：回溯在解尚未构造完成时，就能够识别某些绝不可能成功的分支，并提前停止探索。这种提前放弃叫作：剪枝（Pruning）。

第四幕：现在轮到你，把皇后放上棋盘

我们先做一个真正可以操作的实验。规则很简单：你要在每一行放置一个皇后。如果某个位置与已有皇后冲突，就不能放置。如果走错了，可以撤销上一枚皇后。先从4×4开始。它已经足够让我们体验回溯，却不会像8×8那样复杂。

皇后挑战室

每行放置一枚，尝试找到合法布局

0/4 枚皇后

棋盘大小

显示受攻击格子

请选择第1行皇后的位置。

在4×4棋盘中，只有两种合法解。如果你把第一行皇后放在最左边，就会发现，无论怎样尝试后面的行，都无法完成全部四枚皇后的放置。而只要撤销第一枚皇后，尝试其他位置，就有机会找到答案。这就是回溯最重要的一点：失败不意味着程序结束，而意味着当前这条路径已经探索完毕，需要返回上一个决策点。

第五幕：1965年，“回溯”正式成为一种通用程序设计方法

我们从1850年跳到1965年。一百多年过去，电子计算机已经出现。程序员开始面对越来越复杂的组合搜索问题。1950年代和1960年代，数学家与程序设计研究者逐渐把“试探—撤销—再试探”的方法系统化。1965年，Solomon W. Golomb 与 Leonard D. Baumert 在 Journal of the ACM 发表：Backtrack Programming（回溯程序设计）。这是回溯算法历史上的重要论文。根据美国国家标准与技术研究院（NIST）的算法词典，论文提到，Backtrack 这一名称由加州大学伯克利分校的数学家 Derrick Henry Lehmer 使用并推广。^[xlinux]这里需要澄清：Lehmer 并不是第一个想到“走不通就退回来”的人。这种思维远早于现代计算机。我们在第六章讲过的19世纪 Trémaux 迷宫探索方法，就具有回溯思想。1965年研究的重要意义，是把它作为一种适用于广泛组合问题的程序设计方法进行明确讨论。

搜索空间可以画成一棵树

假设每个决策点有三个可能选择。第一层有3个分支。第二层最多有9个。第三层最多有27个。于是，我们得到一棵搜索树。

查看 SVG 配图原件

10-004.svg · 点击查看大图

这是一个本质性的飞跃。过去，我们可能认为程序需要枚举所有完整答案，然后检查。现在，回溯告诉我们：每个尚未完成的局部状态，本身就值得检查。一旦确定这个局部状态不可能扩展成合法答案，整棵子树都可以跳过。而且剪枝越早，省掉的后续搜索通常越多。

第六幕：1971年，Dijkstra 用八皇后解释怎样正确设计程序

Edsger W. Dijkstra

1930—2002 · 荷兰计算机科学家我们在第六章已经认识他：最短路径算法、程序正确性、结构化程序设计等领域的重要研究者。

1971年8月，Dijkstra 写下了一份教学手稿：A Short Introduction to the Art of Programming（程序设计艺术简论）。其中第九章，正是八皇后问题。后来，他也在1972年出版的《Structured Programming》中讨论了这个例子。这次我们不必依赖后人的转述，因为他的原始手稿就保存在德克萨斯大学的 Dijkstra 档案馆中。阅读 Dijkstra 1971年《The Problem of Eight Queens》原始手稿Dijkstra 的讲解非常值得仔细阅读。他没有一开始就写出一份成熟的回溯程序。而是问：既然最终目标是八位皇后互不攻击，怎样构造一个容易逐步生成的候选集合？首先，可以规定每一行恰好有一位皇后。这样就可以用一个数组表示棋盘：

position[row] = column

接下来，只需要判断新加入的皇后是否与已有皇后冲突。然后，一行一行构造。这就导向回溯。他还指出一个重要事实：一种有效的程序设计方法，不仅应该产生正确结果，也应该让我们能够解释为什么它不会遗漏任何解。 ^{[德克萨斯大学奥斯汀分校计算机科学]}

为什么每次只需要检查三类冲突？

假设已经按行放置皇后。当前准备在第

r

行、第

c

列放置一位皇后。由于每行只放一位，不必再检查同行冲突。剩下三个条件：不能有已有皇后占据相同列。不能有已有皇后位于同一条 / 对角线。不能有已有皇后位于同一条 \ 对角线。数学上，可以用：

c

r-c

r+c

分别标记列和两类对角线。为什么？对于同一条左上至右下的对角线：

r-c=\text{常数}

而对于右上至左下的对角线：

r+c=\text{常数}

因此，我们可以使用三个集合：

cols = set()
diag1 = set()
diag2 = set()

每次放置前，只需要判断：

if c in cols:
    continue

if r - c in diag1:
    continue

if r + c in diag2:
    continue

这就避免了每次扫描整个棋盘。通过哈希集合，通常能够以均摊

O(1)

的时间进行这些成员检查。是不是很熟悉？第四章的哈希表，再一次成为解决更复杂算法问题的基础工具。

第七幕：真正的回溯，只有三个动作

我们现在把整个过程压缩成一个通用思维框架。做选择（Choose）→ 深入搜索（Explore）→ 撤销选择（Unchoose）。用 Python 实现八皇后：

def solve_n_queens(n):
    results = []

    positions = []
    cols = set()
    diag1 = set()
    diag2 = set()

    def backtrack(row):
        if row == n:
            results.append(positions.copy())
            return

        for col in range(n):
            d1 = row - col
            d2 = row + col

            if col in cols or d1 in diag1 or d2 in diag2:
                continue

            # 1. 做选择
            positions.append(col)
            cols.add(col)
            diag1.add(d1)
            diag2.add(d2)

            # 2. 深入搜索
            backtrack(row + 1)

            # 3. 撤销选择
            positions.pop()
            cols.remove(col)
            diag1.remove(d1)
            diag2.remove(d2)

    backtrack(0)
    return results


solutions = solve_n_queens(8)
print(len(solutions))  # 92

为什么一定要撤销选择？

仔细看：

positions.append(col)

我们在当前行尝试一个位置。接着调用：

backtrack(row + 1)

深入处理后续行。不管后续成功还是失败，当这层递归返回时，我们都必须恢复当前层进入下一候选位置之前的状态。因此：

positions.pop()

以及：

cols.remove(col)
diag1.remove(d1)
diag2.remove(d2)

如果缺少这些撤销操作，上一条搜索分支留下的状态就会污染下一条分支。计算机可能错误地认为某些位置已经被占用。这是一种非常常见的回溯程序错误。

回溯与 DFS 到底是什么关系？

我们在第六章讲过深度优先搜索。DFS 沿一条路径不断深入，走到尽头后再返回。回溯通常也采取这种搜索顺序。区别在于，回溯特别强调：每走一步就检查当前部分解是否仍有希望；如果没有希望，立即剪枝，并恢复状态。可以把它理解成：回溯经常是应用于隐式解空间树、带有约束检查和状态撤销的 DFS。但并不是所有 DFS 都在求解组合约束问题，也不是所有回溯实现都必须写成显式递归函数。

第八幕：为什么八皇后的搜索空间比我们想象的小？

现在来一个真正的计算实验。我们已经知道：如果完全忽略约束，从64个格子挑8个，有44亿多种组合。如果只要求每行一位皇后，候选数是：

8^8=16,777,216

如果还要求列不能重复，就剩下：

8!=40,320

如果再及时剪掉对角线冲突分支，实际需要探索的部分状态数量还会显著减少。

实验：改变棋盘大小，观察回溯搜索量

搜索空间压缩实验

精确计数

不重复列的完整排列数

40,320

回溯访问的部分状态数

2,057

完整合法解数量

92

允许访问的最大深度

8

每根柱子对应 N=4 至 N=8 的部分状态数量，包含根节点和完整解叶节点。

查看图表数据

n	回溯访问节点数
4	17
5	54
6	153
7	552
8	2057

这里的节点数统计采用逐行放置、按列从小到大尝试、仅在放置合法时递归的回溯程序。不同统计口径（是否计入失败尝试）会得到不同节点数量。

请注意一个微妙之处。8皇后有92个完整解。但搜索过程中，我们还必须检查许多尚未完成的部分布局。因此，访问节点数一定不只是92。然而，相比遍历所有可能的完整排列，及时剪枝已经节省了大量无意义工作。不过，回溯并没有让所有指数级问题都变得容易。最坏情况下，搜索树依然可能非常庞大。对于 N 皇后这类问题，一种自然的粗略上界是

O(N!)

量级的候选排列搜索；使用不同状态表示、约束策略和对称性优化后，实际工作量可能相差很大。回溯的优势是：它可以利用具体问题的约束，大幅减少实际探索量，而不是无条件消除组合爆炸。

第九幕：2000年，Knuth 让链表开始“跳舞”

Donald Knuth

《计算机程序设计艺术》作者他长期研究组合算法、程序正确性、离散数学和高效数据结构。

故事走到2000年。距离八皇后问题最早发表，已经过去152年。但研究者还在探索：怎样让回溯算法运行得更高效？这一年，Knuth 发表了一篇题为：Dancing Links（舞蹈链）的论文。他的思路非常特别。回溯程序不断做选择，然后撤销选择。如果每次做选择都要复制一份庞大的状态，或者每次撤销都要重新构建大量数据，成本就会很高。那么，能不能设计一种数据结构，使删除与恢复操作都非常迅速？Knuth 使用了双向循环链表，并设计了能够快速移除和恢复节点的操作。这一技术尤其适合求解精确覆盖问题（Exact Cover）。^[arXiv]

什么是精确覆盖？

假设我们有四项任务：A、B、C、D。现在有三组候选方案：

方案1覆盖 A、B。
方案2覆盖 C、D。
方案3覆盖 B、C。

我们希望选出若干组方案，使每项任务恰好被覆盖一次。例如，选择方案1与方案2就满足要求。但如果选择方案1和方案3，B 就会被重复覆盖。这类问题可以用回溯解决。而八皇后、某些拼图和数独问题，也能被转化为类似的约束满足模型。

为什么叫 Dancing Links？

因为在双向链表中，如果临时删除一个节点，可以让它左右的邻居直接连接。而恢复时，又可以利用保存的邻居指针把它重新插回原位置。从概念上看，节点仿佛在结构里不断离开、归位。

双向链表中的可逆删除

查看 SVG 配图原件

10-007.svg · 点击查看大图

在算法的每一次递归中，这类可逆操作都可以避免大量状态复制。Knuth 在论文中也展示了它处理多种组合谜题的能力，包括较大规模的 N 皇后问题。Knuth 2000年论文《Dancing Links》但并不是所有回溯问题都适合 Dancing Links。它主要适用于能够建模为精确覆盖的问题。对于普通的八皇后，使用三个集合记录列与对角线，已经是非常清晰而高效的教学实现。真正值得学习的是 Knuth 背后的设计原则：如果算法不断修改和恢复状态，那么数据结构应当让这些操作尽可能便宜。这又让我们回到了第一章的链表。原来，最初看起来简单的指针操作，在复杂组合算法中也能发挥重要作用。

第十幕：回溯与动态规划，为什么看起来如此相似，却又完全不同？

这是我认为最值得和上一章联系起来的一部分。第八章，Bellman 告诉我们：如果很多路径最终到达相同的状态，可以保存这个状态的最优答案，避免重复计算。这一章，回溯告诉我们：如果一条路径已经违反约束，就立即停止继续探索。它们都在利用状态信息减少搜索。但处理问题的方式不同。

回溯：放弃不可能成功的路径

例如八皇后。如果当前两位皇后已经位于同一对角线，那么继续放置后面的皇后也无济于事。因此直接剪掉分支。

动态规划：复用已经计算过的状态

例如背包问题。如果我们已经计算出：“只考虑前5件物品、容量为10时的最大价值”那么以后遇到同一个子问题，就可以直接复用答案。

两者的关键区别

	回溯 Backtracking	动态规划 Dynamic Programming
核心操作	尝试、检查、撤销	定义状态、计算、复用
主要优化	剪掉无效分支	避免重复子问题计算
常见实现	DFS / 递归	记忆化 / 填表
是否枚举解	经常需要	通常聚合子问题答案
典型问题	八皇后、排列组合、数独	背包、编辑距离、路径计数

不过，二者并非互斥。在复杂算法中，回溯搜索可以利用记忆化来避免重复状态，也可以利用动态规划结果作为剪枝依据。例如某些旅行商问题算法，既使用分支限界搜索，又利用状态压缩 DP 提供界限或求解子问题。这再次说明：算法不是彼此隔离的工具，而是可以组合的思想。

第十一幕：从八皇后，到数独和现代约束求解器

回溯思想在现代软件中拥有大量应用。

数独

填数独时，我们可以：选择一个尚未填入的格子。列出它当前允许的候选数字。尝试填入其中一个。如果后续发现矛盾，撤销这个数字，再尝试其他候选。这与八皇后的算法结构几乎相同。但一个优秀的数独求解器通常不会机械地从左上角开始。它可能优先处理候选数字最少的格子。这叫作：Minimum Remaining Values（MRV），最少剩余值启发式。为什么有用？因为一个只剩两种可能的格子，比一个还有九种可能的格子更容易迅速暴露矛盾。如果某个选择是错误的，我们希望尽可能早地发现。这就与回溯的核心思想完全一致。

编译器与解析器

在某些语法解析方法中，解析器会尝试一条语法分支。如果无法匹配，就回到某个选择点，尝试另一种解析。不过，并非所有现代解析器都依赖回溯；LL、LR 等解析方法使用不同的分析策略。

AI 与约束满足问题

许多排程、资源分配、逻辑谜题可以建模为约束满足问题（Constraint Satisfaction Problem，CSP）。例如：

给不同考试安排时间和教室。
为员工安排轮班。
在电路布局中分配资源。
为不同任务分配机器。
解决复杂组合谜题。

一个约束求解器可能结合回溯、约束传播、启发式变量选择、冲突学习等技术。因此，八皇后虽然只是一个棋盘谜题，却是理解现代约束搜索的重要入口。

终章挑战：什么时候应该立刻撤销？

假设现在有三个数字：1、2、3要求排列成三个位置，但必须满足：

第一位不能是3。
第二位必须比第一位大。
第三位必须比第二位大。

你尝试：2、1、3当你放置第二位的1时，就已经违反条件。这时应该怎么做？

一位真正理解回溯的工程师，会采取哪种行动？

继续放置第三位数字，等完整排列后再判断立即撤销第二位，尝试其他数字把整个搜索过程全部清空，从头开始记录这个排列，然后继续搜索后续分支

回溯最关键的一点，不是“遇到失败就从头再来”。而是：只撤销足够多的选择，回到最近一个仍有其他可能性的决策点。这让搜索既系统，又不会遗漏其他分支。

尾声：一种敢于后退的算法

让我们回顾这段跨越150多年的历史。1848年，Max Bezzel 在棋类杂志上提出八皇后问题。1850年，Franz Nauck 给出了92个排列，而高斯的手工尝试没有找全。1965年，Golomb 和 Baumert 系统讨论回溯程序设计。1971—1972年，Dijkstra 利用八皇后问题解释如何构造清晰、可证明正确的程序。2000年，Donald Knuth 又通过 Dancing Links 展示了如何让某些组合搜索的状态修改与恢复变得更加高效。这些研究者面对的问题不同，工具不同，甚至相隔一个多世纪。但他们共同揭示了一种非常重要的计算思想：不必每次都走到尽头，才承认这条路不对。当一个部分解已经不可能扩展成最终答案时，就应该立刻撤销它。这并不是失败。而是一种有数学依据的节省。

第十章知识总结

概念	核心思想
Backtracking	尝试、深入、撤销
Search Tree	把选择过程表示为树
Pruning	提前舍弃不可能成功的分支
Constraint Checking	尽早检查局部状态是否有效
DFS	深入探索，再返回分支点
State Restoration	返回后恢复此前状态
Heuristics	优先尝试更有希望、能更快发现矛盾的选择
Exact Cover	每项约束必须被恰好满足一次

本章历史资料

美国数学会：八皇后问题的历史与组合数学背景 Paul J. Campbell（1977）：《Gauss and the Eight Queens Problem》NIST：Backtracking 的定义及1965年论文史料 Dijkstra（1971）：《The Problem of Eight Queens》Donald Knuth（2000）：《Dancing Links》

下一章预告

第十一章：字符串匹配——1970年代，三位科学家如何让计算机不必从头反复比较？

假设你有一份长达一百万字符的文本。你希望寻找其中的一段特定文字。最直观的办法，是从文本第一个位置开始，逐字符比较。一旦发现不匹配，就移动一个位置，再重新比较。可这样做，可能反复比较许多已经检查过的字符。20世纪70年代，Donald Knuth、James Morris 和 Vaughan Pratt 等研究者系统研究了这一问题。他们发现，已经比较过的字符，其实包含可以利用的信息。为什么要在不匹配后，把所有进度都丢弃？这就引出了著名的 KMP 字符串匹配算法。下一章，我们将从真实论文和早期文本处理的研究环境出发，看看如何通过构造前缀函数，让模式匹配避免大量重复工作。更有意思的是：一个看起来只是寻找字符串的小算法，为什么能够体现自动机、有限状态与算法复杂度之间的深刻联系？