用回溯法编程求解爱因斯坦谜题

谢玉庚

（中国石化中原石油化工有限责任公司，河南 濮阳 457004）

用回溯法编程求解爱因斯坦谜题

谢玉庚

（中国石化中原石油化工有限责任公司，河南 濮阳 457004）

本文模拟人工智能的思路，用回溯法编程求解爱因斯坦谜题，使总排列数下降了7个数量级，极大提高了解题速度。程序编写了线索输入函数，把迷题线索存入向量中，可随意修改线索的内容、数量及顺序，进而对新的谜题进行重新求解，而不用修改剪枝函数的代码，适用性好。

爱因斯坦谜题；回溯法；拼图；人工智能；向量

1 引言

爱因斯坦谜题又称Zebra谜题[1]，是一道很有趣的逻辑推理题，基本内容如下：有一排五间房子，每一间房子的颜色都不同，在这些房子里住着五个不同国籍的人，每个人喂养了不同的宠物，喜欢不同的饮料，抽不同的雪茄。目的是最后要找到养鱼的人。这是一个能够进行人工求解的谜题。有很多人尝试用计算机来求解问题。文献[2]列举了人工图表法和SAT求解法。文献[2]本身论述了定理证明器PVS求解法，都可以在有限的时间里取得较好的结果。文献[3]提供了编程求解法，需要在(5!)5个排列中找到答案，这是个天文数字，如果能调整好合适的线索顺序，也许可以找到令人满意的求解速度。网络上也逐渐给出了具体的编程求解方案如文献[4]，其基本思路属于回溯法[5]，速度也很快，但不能像文献[2]所述的那些辅助办法那样具有较广泛的适用性。综合以上文献及程序，本文根据图表解题思路结合拼图的概念用回溯法及向量技术[6]编写了求解爱因斯坦谜题的程序，取得了进一步的良好效果。

2 人工解题思路

画好5行5列的空表格，先根据线索8、9、14填入固定的元素“挪威人”、“蓝色”、“牛奶”。然后根据第一条线索尽可能从最左侧的列填入其它活动的元素，再分析判断剩下的空格可否满足第二条线索，依此类推。如果不能继续满足下一个线索，则右移上一个线索的列位置，继续分析，直至符合所有的线索就可以找出谜题的出答案。

以下估算这种思路的排列数：

首先，线索8、9、14固定了相关元素内容。其排列数都是1。

第一个线索“英国人住红房子”只能在第3列至第5列任选其一，排列数为3。

第二个线索“瑞典人养狗”可在第2、4、5列任选其一，排列数为3，依此类推，如表1所示为部分估算过程。

表1 表格拼图求解爱因斯坦谜题

按照这种思路，本人估算的排列数总数为3*3*2*3*1*4* 1*1*1*4*2*2*1*1*1=3456个，这种估算因人而异，但其数量级相差不大。

这个问题的最大排列数是（5！）5，是250亿，比这种拼图法高了7个数量级。

这种思路实际上是把25个小方格的拼图简化成16个小图案的拼图，其中有12个小图案是可以左右移动的，但是因为有上下行交错占位的排斥关系，其总排列数会进一步减少。看来这种思路的确很“划算”。

3 具体的程序设计实现

用5行5列的字符串数组string houses[5][5]代表5个房子，存储国家、颜色、饮料、香烟、宠物5种属性及其内容。

数组初始化：线索8、9、14无需分析，用函数void settlement(int,int,string)把它们的内容直接分配到相应的数组元素里，其他的元素为空，程序中用字符串“____”表示。

其他12条线索每个都分为两个子因素，其列范围都可以从0到5，绿色除外。但还是需要根据不同的逻辑确定各个子因素各自的列范围。

在分析过程中，有些线索的第一子因素已经在前面的线索中出现过，其列范围被视为已固定，不需进行列范围的试探，用void initfactors1(int)函数处理。例如线索4和5都出现了绿房子。

第二子因素的列范围确认比较复杂，其逻辑包括“自己”、“隔壁”、“左面”、“左隔壁”等类型，用函数void initfactors2(int)处理。

将结构struct hint的对象加入向量vector

当同时满足两个子因素时，用向前试探标志factor1记录内层子因素是否完成列循环。线索号condnum加1，通过search(condnum)进入下一个线索，进行向前试探分析。

不能同时满足两个子因素时进行回溯分析。线索号condnum减1后，用search(condnum)回溯到上一个线索的分析，如果其内层的子因素列循环尚未完成，则根据factor1的值穿透外层循环先进行内层循环，否则按照正常逻辑从外层循环向内层循环逐步分析。会经常发生连续回溯的情况。

程序用while语句对search(int)函数进行循环分析，这样程序就出现了三层while循环的嵌套分析，从而实现了对向量中每个元素（线索）里内外层子因素的回溯分析。

程序结果如图1所示。本程序将线索4认定为绿房子可以在白房子左面所有的位置，不仅限于左隔壁，故而求解出7组答案。

4 程序的优点及难点

由于使用了向量，可以随意增减线索输入函数addhint()的调用次数，再通过修改形参、改变调用次序等办法就可以随意改变谜题线索的数量、内容、顺序，而不用修改剪枝函数源代码，甚至可从控制台进行线索的输入，使程序具有很好的灵活性及类似SAT求解器的适用性。灵活性的代价就是提高了出错率，本程序最不经意的错误是第二因素的重复出现，程序提供了必要的检查重复输入的函数isrepeat()，来提醒这种错误的发生。

用while语句结合线性结构还减少了递归法容易发生的堆栈溢出的问题。但三层while循环经常发生“跳层”的情况，也增加了程序调试的难度，除非不得已，尽量不采用“跳层”的办法。

图1 谜题的第7个答案

5 结语

综合以上分析，虽然本文程序逻辑较复杂，但程序具有更好的灵活性和适用性。本程序通过修改houses[][]数组下标、修改越界检查极限、修改setelement()函数形参、修改addhint()函数的形参、增减函数的调用次数、改变调用次序，便可用于更多维度、更多线索的Einstein谜题的灵活分析。

[1]田聪，段振华，王小兵．Einstein谜的SA T求解[J]．计算机科学，2010(0 5)：18 4-18 6．

[2]朱维军，周清雷．求解爱因斯坦谜题的一种形式系统及推理方法[J]．计算机科学，2012(0 9)：2 44-2 46．

[3]邬晓钧．爱因斯坦的谜题解答[J]．程序员，200 7(0 7)：10 7-10 9．

[4]“爱因斯坦谜语”C语言智能分析源码[EB/OL]．http：//www．openloongson.org/forum.php?mod=viewthread&tid=148&extra=page%3D3，2015．

[5]管西京．程序设计算法新手自学手册[M]．北京：机械工业出版社，2012．

The Solution of Einstein’S Riddle with Backtracking Algorithm

Xie Yugeng
(Sinopec Zhongyuan Petrochemical Co.,Ltd.,Puyang 457004,Henan)

With the thought of artificial intelligence,this paper uses the backtracking algorithm in solving Einstein’s Riddle, which can reduce the number of permutations by seven orders of magnitude and greatly improve the problem solving speed.The program includes a clue input function and puts the puzzle clues in vector.The content,quantity and sequence of the clues can be modified at random,to resolve new puzzles without modification of pruning function code.Therefore,the program has good applicability.

Einstein’S Riddle;backtracking algorithm;jigsaw;A.I.;vector

TP18

A

1008-6609(2016)10-0050-02

谢玉庚（19 72-），男，陕西白水人，本科，工程师，研究方向为设备管理信息化。