过河问题——运送狼、羊与白菜的 1200 年前谜题

大家好，我是 Senko。本文将解读逻辑谜题里最资深的“过河问题”。

农夫带着狼、羊和白菜站在河岸边。船上除了农夫只能再装一样。而且农夫不看着的时候，狼会吃羊，羊会吃白菜。那么，怎样才能把它们全都平安运到对岸？这是连小孩都能玩的朴素问题，可它是载于 1200 年前教科书上、有记录可查的最古老一批逻辑谜题，同时也是现代 AI 研究的出发点之一。

过河问题是什么

过河问题（英语 river crossing puzzle，这一版叫 wolf, goat and cabbage problem），是在运输工具的容量与“不能放在一起的组合”这两条约束下，设计把全员运往对岸的步骤的谜题。先把规则整理一下。

农夫想把狼、羊、白菜全部运到对岸
只有农夫会划船。船上除农夫外只能再装一样
农夫不在的那一岸，不能把狼和羊单独留在一起（羊会被吃）
农夫不在的那一岸，不能把羊和白菜单独留在一起（白菜会被吃）

从第一步起，这道谜题的性格就露出来了。先运狼，留下的那岸羊会吃白菜。先运白菜，狼会吃羊。也就是说，第一步只有运羊这一个选项。问题在下一步。第二趟不管运什么，放到对岸的瞬间就会和羊凑成危险的一对。很多人的手在这里停住了。

查理曼的宫廷学者留下的原典

这道谜题的出处古老得惊人，可上溯到8 世纪的欧洲。侍奉法兰克王国查理曼大帝的英格兰学者阿尔昆（约 735～804 年）所作的题集《磨砺青年的命题集》里，就原样收录着狼、羊和白菜的问题。

这本题集是用拉丁文写的、五十来道题的谜题集，被评价为现存西方最古老的一批数学谜题集。阿尔昆是统领查理曼宫廷学校的当世第一流知识人，他在给大帝的信里写道要送上“供消遣的算术题”，一般认为这就是这本题集的由来。也就是说，它本是为皇帝的教养而做的谜题集。

有意思的是，题集里连着收了三道过河题。第 17 题是“善妒的三位丈夫”，约束是丈夫不允许自己不在场时妻子与别的男人同处，三对夫妇要用两人座的船过河，这一题需要 11 步，相当难。第 18 题就是本文的狼、羊与白菜。第 19 题是“体重很沉的夫妇与两个孩子”，问只能承载一个大人重量的船怎样把全家运过去。变换约束的种类，把同一骨架的问题排在一起——这个编排方式与现代的习题集完全是同一个发想。

1200 年前的老师，用过河问题来磨砺青年和皇帝的头脑。我觉得这是象征谜题这一门类生命力之长的一个事实。

答案是 7 步，钥匙在第 4 步

最短答案是 7 步。跟着走一遍。

把羊运到对岸
农夫独自返回
把狼运到对岸
带着羊返回
把白菜运到对岸
农夫独自返回
把羊运到对岸

全局的点睛之笔，不用说就是第 4 步。特意把好不容易运过去的羊带回原岸。正因为有这一步看似白费的后退，狼和白菜才能安全地聚到对岸。第 3 步把狼换成白菜也有对称的解，最短解就只有这两种。

而要紧的是，不含后退的解并不存在。一旦禁止把某样带回来的走法，这道题就无解了。也就是说，第 4 步不是权宜之计，而是逻辑上被强制的唯一之路。

用图看清“绕路才是最短路”的结构

为什么后退是必需的，把谜题画成状态的地图就一目了然。

每个时点的状况，由狼、羊、白菜、农夫各在哪一岸决定。组合是 2 的 4 次方即 16 种。从中除掉“羊被吃”“白菜被吃”的状态，安全状态只剩 10 个。把这 10 个状态画成点，把船划一趟能互相到达的状态用线连起来，就会看到从起点到终点的路几乎是一条独木道，而第 4 步的后退就嵌在这条路的中途。

这样一看，过河问题就从“灵光一闪的问题”变成了“地图上的最短路问题”。而这恰恰是让计算机解谜题时的基本战略：把状态全部列出来，用允许的移动连起来，再搜索从起点到终点的路径。这个被称为状态空间搜索的框架，成了人工智能研究的地基之一。

事实上，AI 研究者索尔·阿马雷尔 1968 年发表的经典论文，就以过河问题的亲戚“传教士与食人族问题”为题材，论述了仅仅改变问题的表示方法，搜索的难度就会剧变。此后这类过河谜题，一直被当作 AI 与算法教科书里状态空间搜索的第一道例题。游戏 AI 解残局也好，导航找路线也好，根子上都和农夫与羊的船程是同一回事。

能否容许暂时的后退，决定计划的质量

我觉得这道谜题向日常抛出的教训是：光把前进叠起来，未必就能到达目的地。

比如软件开发中的重构，就是把跑得好好的东西先拆掉的第 4 步。爬山时，与其正面直登眼前的坡，先下一段再绕过山脊往往更快。在职业上，为了重新学习而暂时降薪或卸下职位，长期看反而是最短路径的事也不罕见。要求每一步都增加成果的评价方式，会把含有后退的最短路径从选项里抹掉。

另一个教训，是“先把不能放在一起的组合写出来”这套约束整理术。过河问题的实务版其实到处都是：工序表上不能同时开跑的作业、开会时凑在一起就吵翻的利益相关方、药物的相互作用、服务器上不能混部的负载。只要把容量的约束与相性的约束分开写出来，这类安排问题就会好解得多。

派生问题与计算机的解法

船上能装两样的情况

3 步就结束。第一步把狼和白菜一起运走，第二步农夫独自返回，第三步运羊，完了。狼和白菜是同处也安全的一对，留在原岸的羊单独一个也闹不出事。因为能把危险人物羊隔离到最后，后退那一步就整个不需要了。约束相同，仅仅运输容量加一，难点就消失，这是个好例子。

善妒的丈夫们与著名变体

除了阿尔昆题集里三对夫妇的版本（两人座的船，11 步），传教士与食人族问题（任一岸上食人族都不能多于传教士）也很有名。另外作为过河的亲戚，“过桥与火把问题”也常被出。过桥分别需要 1 分、2 分、5 分、10 分的四个人，只有一支火把、每次两人同行，能否在 17 分钟内全部过桥——这一题的钥匙同样是“先让快的两人过去，再让一人返回”这个反直觉的走法。