用回溯法編程求解愛因斯坦謎題

謝玉庚

（中國石化中原石油化工有限責任公司，河南 濮陽 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-），男，陜西白水人，本科，工程師，研究方向為設備管理信息化。