输入您的搜索字词 提交搜索表单
	Web www.fmddlmyy.cn

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

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

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

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

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

1 穷举

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

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

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

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

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

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

2 推理

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

2.1 探索问题域

2.1.1 对象、方案和方案集

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

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

方案集是方案的集合。

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

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

2.1.２ 对象内约束和对象间约束

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

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

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

2.2 推理过程

2.2.1 初始状态

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

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

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

2.2.2 使用对象内约束

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

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

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

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

2.2.3 使用对象间约束

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

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

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

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

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

2.3 不足

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

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

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

	输入您的搜索字词 提交搜索表单
	Web www.fmddlmyy.cn