謝玉庚

（中國石化中原石油化工有限責(zé)任公司，河南 濮陽 457004）

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

謝玉庚

（中國石化中原石油化工有限責(zé)任公司，河南 濮陽 457004）

本文模擬人工智能的思路，用回溯法編程求解愛因斯坦謎題，使總排列數(shù)下降了7個數(shù)量級，極大提高了解題速度。程序編寫了線索輸入函數(shù)，把迷題線索存入向量中，可隨意修改線索的內(nèi)容、數(shù)量及順序，進而對新的謎題進行重新求解，而不用修改剪枝函數(shù)的代碼，適用性好。

愛因斯坦謎題；回溯法；拼圖；人工智能；向量

1 引言

愛因斯坦謎題又稱Zebra謎題[1]，是一道很有趣的邏輯推理題，基本內(nèi)容如下：有一排五間房子，每一間房子的顏色都不同，在這些房子里住著五個不同國籍的人，每個人喂養(yǎng)了不同的寵物，喜歡不同的飲料，抽不同的雪茄。目的是最后要找到養(yǎng)魚的人。這是一個能夠進行人工求解的謎題。有很多人嘗試用計算機來求解問題。文獻[2]列舉了人工圖表法和SAT求解法。文獻[2]本身論述了定理證明器PVS求解法，都可以在有限的時間里取得較好的結(jié)果。文獻[3]提供了編程求解法，需要在(5!)5個排列中找到答案，這是個天文數(shù)字，如果能調(diào)整好合適的線索順序，也許可以找到令人滿意的求解速度。網(wǎng)絡(luò)上也逐漸給出了具體的編程求解方案如文獻[4]，其基本思路屬于回溯法[5]，速度也很快，但不能像文獻[2]所述的那些輔助辦法那樣具有較廣泛的適用性。綜合以上文獻及程序，本文根據(jù)圖表解題思路結(jié)合拼圖的概念用回溯法及向量技術(shù)[6]編寫了求解愛因斯坦謎題的程序，取得了進一步的良好效果。

2 人工解題思路

畫好5行5列的空表格，先根據(jù)線索8、9、14填入固定的元素“挪威人”、“藍色”、“牛奶”。然后根據(jù)第一條線索盡可能從最左側(cè)的列填入其它活動的元素，再分析判斷剩下的空格可否滿足第二條線索，依此類推。如果不能繼續(xù)滿足下一個線索，則右移上一個線索的列位置，繼續(xù)分析，直至符合所有的線索就可以找出謎題的出答案。

以下估算這種思路的排列數(shù)：

首先，線索8、9、14固定了相關(guān)元素內(nèi)容。其排列數(shù)都是1。

第一個線索“英國人住紅房子”只能在第3列至第5列任選其一，排列數(shù)為3。

第二個線索“瑞典人養(yǎng)狗”可在第2、4、5列任選其一，排列數(shù)為3，依此類推，如表1所示為部分估算過程。

表1 表格拼圖求解愛因斯坦謎題

按照這種思路，本人估算的排列數(shù)總數(shù)為3*3*2*3*1*4* 1*1*1*4*2*2*1*1*1=3456個，這種估算因人而異，但其數(shù)量級相差不大。

這個問題的最大排列數(shù)是（5！）5，是250億，比這種拼圖法高了7個數(shù)量級。

這種思路實際上是把25個小方格的拼圖簡化成16個小圖案的拼圖，其中有12個小圖案是可以左右移動的，但是因為有上下行交錯占位的排斥關(guān)系，其總排列數(shù)會進一步減少?？磥磉@種思路的確很“劃算”。

3 具體的程序設(shè)計實現(xiàn)

用5行5列的字符串?dāng)?shù)組string houses[5][5]代表5個房子，存儲國家、顏色、飲料、香煙、寵物5種屬性及其內(nèi)容。

數(shù)組初始化：線索8、9、14無需分析，用函數(shù)void settlement(int,int,string)把它們的內(nèi)容直接分配到相應(yīng)的數(shù)組元素里，其他的元素為空，程序中用字符串“____”表示。

其他12條線索每個都分為兩個子因素，其列范圍都可以從0到5，綠色除外。但還是需要根據(jù)不同的邏輯確定各個子因素各自的列范圍。

在分析過程中，有些線索的第一子因素已經(jīng)在前面的線索中出現(xiàn)過，其列范圍被視為已固定，不需進行列范圍的試探，用void initfactors1(int)函數(shù)處理。例如線索4和5都出現(xiàn)了綠房子。

第二子因素的列范圍確認比較復(fù)雜，其邏輯包括“自己”、“隔壁”、“左面”、“左隔壁”等類型，用函數(shù)void initfactors2(int)處理。

將結(jié)構(gòu)struct hint的對象加入向量vector

當(dāng)同時滿足兩個子因素時，用向前試探標志factor1記錄內(nèi)層子因素是否完成列循環(huán)。線索號condnum加1，通過search(condnum)進入下一個線索，進行向前試探分析。

不能同時滿足兩個子因素時進行回溯分析。線索號condnum減1后，用search(condnum)回溯到上一個線索的分析，如果其內(nèi)層的子因素列循環(huán)尚未完成，則根據(jù)factor1的值穿透外層循環(huán)先進行內(nèi)層循環(huán)，否則按照正常邏輯從外層循環(huán)向內(nèi)層循環(huán)逐步分析。會經(jīng)常發(fā)生連續(xù)回溯的情況。

程序用while語句對search(int)函數(shù)進行循環(huán)分析，這樣程序就出現(xiàn)了三層while循環(huán)的嵌套分析，從而實現(xiàn)了對向量中每個元素（線索）里內(nèi)外層子因素的回溯分析。

程序結(jié)果如圖1所示。本程序?qū)⒕€索4認定為綠房子可以在白房子左面所有的位置，不僅限于左隔壁，故而求解出7組答案。

4 程序的優(yōu)點及難點

由于使用了向量，可以隨意增減線索輸入函數(shù)addhint()的調(diào)用次數(shù)，再通過修改形參、改變調(diào)用次序等辦法就可以隨意改變謎題線索的數(shù)量、內(nèi)容、順序，而不用修改剪枝函數(shù)源代碼，甚至可從控制臺進行線索的輸入，使程序具有很好的靈活性及類似SAT求解器的適用性。靈活性的代價就是提高了出錯率，本程序最不經(jīng)意的錯誤是第二因素的重復(fù)出現(xiàn)，程序提供了必要的檢查重復(fù)輸入的函數(shù)isrepeat()，來提醒這種錯誤的發(fā)生。

用while語句結(jié)合線性結(jié)構(gòu)還減少了遞歸法容易發(fā)生的堆棧溢出的問題。但三層while循環(huán)經(jīng)常發(fā)生“跳層”的情況，也增加了程序調(diào)試的難度，除非不得已，盡量不采用“跳層”的辦法。

圖1 謎題的第7個答案

5 結(jié)語

綜合以上分析，雖然本文程序邏輯較復(fù)雜，但程序具有更好的靈活性和適用性。本程序通過修改houses[][]數(shù)組下標、修改越界檢查極限、修改setelement()函數(shù)形參、修改addhint()函數(shù)的形參、增減函數(shù)的調(diào)用次數(shù)、改變調(diào)用次序，便可用于更多維度、更多線索的Einstein謎題的靈活分析。

[1]田聰，段振華，王小兵．Einstein謎的SA T求解[J]．計算機科學(xué)，2010(0 5)：18 4-18 6．

[2]朱維軍，周清雷．求解愛因斯坦謎題的一種形式系統(tǒng)及推理方法[J]．計算機科學(xué)，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]管西京．程序設(shè)計算法新手自學(xué)手冊[M]．北京：機械工業(yè)出版社，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-），男，陜西白水人，本科，工程師，研究方向為設(shè)備管理信息化。