穷举和推理：用C++程序求解“谁养鱼”

这期《程序员》提到“爱因斯坦的谜题”，我才注意到“谁养鱼”这个题目。问题如下：

1、在一条街上，有5座房子，喷了5种颜色
2、每个房里住着不同国籍的人
3、每个人喝不同的饮料，抽不同品牌的香烟，养不同的宠物
已知：
1、英国人住红色房子
2、瑞典人养狗
3、丹麦人喝茶
4、绿色房子在白色房子左面
5、绿色房子主人喝咖啡
6、抽Pall Mall 香烟的人养鸟
7、黄色房子主人抽Dunhill 香烟
8、住在中间房子的人喝牛奶
9、 挪威人住第一间房
10、抽Blends香烟的人住在养猫的人隔壁
11、养马的人住抽Dunhill 香烟的人隔壁
12、抽Blue Master的人喝啤酒
13、德国人抽Prince香烟
14、挪威人住蓝色房子隔壁
15、抽Blends香烟的人有一个喝水的邻居
问题是：谁养鱼？


在网上找一下，看到以下资料：一个手工表格求解、一个Lisp程序求解和阿牛的穷举程序，用C#实现。本文分别用穷举法和推理法解答了这个问题。我先用C++完成了推理法求解。后来看到阿牛的穷举程序后，为了比较两者的效率，又用C++实现了穷举法（参照阿牛的程序）。在我的电脑上，推理法运行时间为：

求解1000次花费3828毫秒，平均每次需要3.8毫秒


在我的T7100笔记本上平均运行时间约为1.88毫秒。穷举法的运行时间与初始数据有很大关系。对比Lisp程序需要的时间（几百到几千毫秒），C++程序确实要快一点。

本文主要介绍算法，对具体实现感兴趣的朋友可以查看源代码。从我的主页（http://www.fmddlmyy.cn）可以下载推理法和穷举法的完整源代码。

1 穷举

穷举法的思路很简单：遍历没有约束时所有可能的解（本文称作解空间），用所有约束条件逐一检查，直到找到符合要求的解。实现穷举法的关键是：怎样遍历解空间？换句话说，我们要按照一定顺序枚举出所有可能的解。

可以把“谁养鱼”的解看作按照房间位置排序的5组属性，例如：

1 挪威 黄色 猫 水 Dunhill
2 丹麦 蓝色 马 茶 Blends
3 英国 红色 鸟 牛奶 Pall Mall
4 德国 绿色 鱼 咖啡 Prince
5 瑞典 白色 狗 啤酒 Blue Master

每组属性是5个元素的排列（不重复），有120（5的阶乘）种可能性，如果没有约束条件，解空间的大小就是120的五次方。尽管解空间很大，由于约束条件可以一下排除很多解，所以需要检查的次数并不像“穷举法”字面上暗示的那么多。穷举法的主要逻辑如下：

foreach (属性1的所有排列) {
if (违反约束条件) {
提前进入下轮循环;
}
foreach (属性2的所有排列) {
if (违反约束条件) {
提前进入下轮循环;
}
foreach (属性3的所有排列) {
if (违反约束条件) {
提前进入下轮循环;
}
foreach (属性4的所有排列) {
if (违反约束条件) {
提前进入下轮循环;
}
foreach (属性5的所有排列) {
if (符合约束条件) {
得到正确解，返回;
}
}
}
}
}
}


进入内层循环前的判断很重要，通过这个判断可以跳过很多次检查。如果约束条件能在外层发挥作用，就可以跳过更多的检查。在外层循环检查约束时，因为还没有填写内层属性，无法使用与内层属性相关的约束条件。所以，将属性放在循环的哪个层次对总检查次数的影响很明显。例如:

属性排列（外->内）	找到正确解的检查次数	总检查次数（找到正确解后不返回）	执行时间（1000次平均）
国家-颜色-香烟-宠物-饮料	6167	11476	14.6毫秒
国家-颜色-宠物-饮料-香烟	28896	61290	84.2毫秒
国家-香烟-饮料-颜色-宠物	47460	86756	110.3毫秒

可见，根据约束条件仔细安排属性位置可以明显降低总检查次数。“找到正确解的检查次数”（或“执行时间”）也有很大的偶然性。假设我们把正确解作为初始数据，显然一下就完成了。

穷举法类似于武功中的“一力降十会”，让我们再试试“以巧破千斤”。

2 推理

我们可以让计算机按照人类的思维模式使用约束条件逐步推导，得到答案。为了更清晰地理解问题域，我们先约定一些名词。

2.1 探索问题域

2.1.1 对象、方案和方案集

在这个问题域中，我们用对象表示一个具有全部属性的人。对象有6个属性：国家、颜色、宠物、饮料、香烟、房间号。可以将所有属性都未定的对象称为空对象。两个空对象是不可区分的。只要对象具备一个及以上已知属性，它就成为唯一的、独特的。

每个方案包含5个对象。这5个对象的所有已知属性都是不同的。方案中的对象在逻辑上是无序的。

方案集是方案的集合。

如果把推理过程看作船的航行，Wizard会这样预言这次航行：

方案集是船，方案是乘客，
所有约束条件构成问题域的环境。
航行伊始，船上只有一个乘客。
它的所有对象的
所有属性都是未定的，
代表我们对环境的一无所知。
当船经过一个个约束条件时，
船上的乘客有时增加、有时减少。
无论乘客怎么变化，船总包含着所有可能。
无论乘客怎么变化，我们的知识都在增加。
当船通过所有的约束条件，
一个乘客会到达终点，
它就是答案。


在介绍详细的推理过程前，让我们再考察一下约束条件。

2.1.2 对象内约束和对象间约束

约束条件可以分为两类：对象内约束和对象间约束。对象内约束描述一个对象内两个属性的关系，例如“英国人住红色房子”。对象间约束描述两个对象的属性间的关系，例如“抽Blends香烟的人住在养猫的人隔壁”。

在“谁养鱼”的约束条件中，对象间约束有两种关系：

1. 邻居关系，例如前面所说的“抽Blends香烟的人住在养猫的人隔壁”；
2. 有序邻居关系。例如“绿色房子在白色房子左面”。

2.2 推理过程

2.2.1 初始状态

“我们构建一个空方案，它的所有对象的所有属性都是未定的，它是方案集中的唯一方案。未定代表可能，这个唯一的方案也包含了所有的可能。”

这个开头虽然很有“无中生有”的哲学意味，但是不实用。我实际采用的初始状态是这样的：

方案1
英国 红色 未定 未定 未定 未定
瑞典 未定 狗 未定 未定 未定
丹麦 未定 未定 茶 未定 未定
德国 未定 未定 未定 Prince 未定
挪威 未定 未定 未定 未定 房间1


我手工选择了5个“对象内约束”对方案作了初始化。我特意选择了不可能出现在同一个对象上的约束条件。这样，这个方案还是包含了所有的可能。初始状态的方案集中只有这么一个方案。

2.2.2 使用对象内约束

将当前方案集作为输入方案集，再准备一个空的输出方案集。将对象内约束应用到输入方案集的所有方案上。例如将“绿色房子主人喝咖啡”应用到方案1上，这时可能出现两种情况：

1. 约束条件可以放到方案的多个对象上。例如“绿色房子主人喝咖啡”可以放到颜色和饮料属性未定的对象上。每次将约束条件放到一个不矛盾的位置，就会产生一个新的方案。将新方案放到输出方案集中。
2. 约束条件可能与方案冲突。这时简单地忽略这个方案。

范例程序可以打印出推导过程，“使用对象内约束”的推导过程如下：

初始状态
-------------------- 一共有 1 个解 --------------------

解1
英国 红色 未定 未定 未定 未定
瑞典 未定 狗 未定 未定 未定
丹麦 未定 未定 茶 未定 未定
德国 未定 未定 未定 Prince 未定
挪威 未定 未定 未定 未定 房间1



增加约束: 5、绿色房子主人喝咖啡
-------------------- 一共有 3 个解 --------------------

解1
英国 红色 未定 未定 未定 未定
瑞典 绿色 狗 咖啡 未定 未定
丹麦 未定 未定 茶 未定 未定
德国 未定 未定 未定 Prince 未定
挪威 未定 未定 未定 未定 房间1

解2
英国 红色 未定 未定 未定 未定
瑞典 未定 狗 未定 未定 未定
丹麦 未定 未定 茶 未定 未定
德国 绿色 未定 咖啡 Prince 未定
挪威 未定 未定 未定 未定 房间1

解3
英国 红色 未定 未定 未定 未定
瑞典 未定 狗 未定 未定 未定
丹麦 未定 未定 茶 未定 未定
德国 未定 未定 未定 Prince 未定
挪威 绿色 未定 咖啡 未定 房间1



增加约束: 12、抽Blue Master的人喝啤酒
-------------------- 一共有 7 个解 --------------------
...


增加约束: 6、抽Pall Mall香烟的人养鸟
-------------------- 一共有 16 个解 --------------------
...


增加约束: 7、黄色房子主人抽Dunhill香烟
-------------------- 一共有 19 个解 --------------------
...


增加约束: 9+14、 挪威人住第一间房+挪威人住蓝色房子隔壁=第二间房是蓝色的
-------------------- 一共有 28 个解 --------------------
...


增加约束: 8、住在中间房子的人喝牛奶
-------------------- 一共有 30 个解 --------------------
...


对象内约束的指定属性被应用到方案的未定属性上，使方案的眉目逐渐清晰。每个输出方案集总是包含着在增加了当前所有约束后的所有可能。

2.2.3 使用对象间约束

对象间约束必须被应用到方案的已知属性上，然后判断两个方案的房间号属性是否符合指定关系。为此，我们在对方案使用对象间约束前，必须保证：

1. 假设约束条件使用了某个属性值（例如颜色为绿色），方案中必须有对象具备这个属性值；
2. 方案所有对象的房间号属性已知。

如果方案不满足上述条件，我们在应用约束条件前就必须先“扩展”方案，让其满足上述条件。“扩展”的过程还是读入一个方案集，输出一个方案集。读入方案如果已经具备指定属性值，就直接将其放入输出方案集。读入方案如果已经不具备指定属性值，就将增加该属性值后的所有可能方案放入输出方案集。

对房间号属性的扩展只需要在应用第一个“对象间约束”前做一次就可以了。

使用对象间约束对扩展过的方案集进行过滤，去掉不满足约束条件的方案，就得到了最后的答案。这部分的推导过程如下：

增加约束: 4、绿色房子在白色房子左面
-------------------- 一共有 4 个解 --------------------

解1
英国 红色 鸟 牛奶 Pall Mall 房间3
瑞典 蓝色 狗 啤酒 Blue Master 房间2
丹麦 白色 未定 茶 Blends 房间5
德国 绿色 未定 咖啡 Prince 房间4
挪威 黄色 未定 水 Dunhill 房间1

解2
英国 红色 鸟 牛奶 Pall Mall 房间3
瑞典 白色 狗 啤酒 Blue Master 房间5
丹麦 蓝色 未定 茶 Blends 房间2
德国 绿色 未定 咖啡 Prince 房间4
挪威 黄色 未定 水 Dunhill 房间1

解3
英国 红色 未定 牛奶 Blends 房间3
瑞典 蓝色 狗 啤酒 Blue Master 房间2
丹麦 白色 鸟 茶 Pall Mall 房间5
德国 绿色 未定 咖啡 Prince 房间4
挪威 黄色 未定 水 Dunhill 房间1

解4
英国 红色 未定 牛奶 Blends 房间3
瑞典 白色 狗 啤酒 Blue Master 房间5
丹麦 蓝色 鸟 茶 Pall Mall 房间2
德国 绿色 未定 咖啡 Prince 房间4
挪威 黄色 未定 水 Dunhill 房间1



增加约束: 10、抽Blends香烟的人住在养猫的人隔壁
-------------------- 一共有 4 个解 --------------------

解1
英国 红色 鸟 牛奶 Pall Mall 房间3
瑞典 蓝色 狗 啤酒 Blue Master 房间2
丹麦 白色 未定 茶 Blends 房间5
德国 绿色 猫 咖啡 Prince 房间4
挪威 黄色 未定 水 Dunhill 房间1

解2
英国 红色 鸟 牛奶 Pall Mall 房间3
瑞典 白色 狗 啤酒 Blue Master 房间5
丹麦 蓝色 未定 茶 Blends 房间2
德国 绿色 未定 咖啡 Prince 房间4
挪威 黄色 猫 水 Dunhill 房间1

解3
英国 红色 未定 牛奶 Blends 房间3
瑞典 蓝色 狗 啤酒 Blue Master 房间2
丹麦 白色 鸟 茶 Pall Mall 房间5
德国 绿色 猫 咖啡 Prince 房间4
挪威 黄色 未定 水 Dunhill 房间1

解4
英国 红色 未定 牛奶 Blends 房间3
瑞典 白色 狗 啤酒 Blue Master 房间5
丹麦 蓝色 鸟 茶 Pall Mall 房间2
德国 绿色 猫 咖啡 Prince 房间4
挪威 黄色 未定 水 Dunhill 房间1



增加约束: 15、抽Blends香烟的人有一个喝水的邻居
-------------------- 一共有 1 个解 --------------------

解1
英国 红色 鸟 牛奶 Pall Mall 房间3
瑞典 白色 狗 啤酒 Blue Master 房间5
丹麦 蓝色 未定 茶 Blends 房间2
德国 绿色 未定 咖啡 Prince 房间4
挪威 黄色 猫 水 Dunhill 房间1



增加约束: 11、养马的人住抽Dunhill香烟的人隔壁
-------------------- 一共有 1 个解 --------------------

解1
英国 红色 鸟 牛奶 Pall Mall 房间3
瑞典 白色 狗 啤酒 Blue Master 房间5
丹麦 蓝色 马 茶 Blends 房间2
德国 绿色 鱼 咖啡 Prince 房间4
挪威 黄色 猫 水 Dunhill 房间1

推理结束。


2.3 不足

目前的推理法程序还有一个地方可以改进：就是在扩展房间号时，其实没有必要先扩展方案集。因为，扩展房间号其实就是几个房间号在几个未定位置的排列。可以对每个方案，枚举所有房间号的排列后，直接用约束条件过滤。这样可以减少需要放入方案集中的方案。

这个推理法已经比较接近人类的思维模式了。但有一点不像：人在推理时喜欢假设和尝试，如果走不通就退回去再尝试其它可能。人类一般不会一板一眼地在每一步上列出所有可能。我的算法没有设计“尝试-回溯”机制。增加这个机制会使逻辑更复杂，严重违反KISS（Keep It Simple, Stupid）理念。其实对于“谁养鱼”这种规模的问题，穷举法是最合适的。

我本来想把“谁养鱼”的问题从5阶扩展到12阶，以测试穷举法和推理法的性能，还选择了一个武林大会的题材。但在准备了12组属性后，发现至少要写70多个hint才能玩起来，就不想玩了。有兴趣的朋友可以用推理法的程序出题。