用窮舉法解愛因斯坦問題

李振夏

摘要 上個世紀，大科學(xué)家愛因斯坦提出了一道非常經(jīng)典的邏輯題“誰在養(yǎng)魚”？這是一道很非常經(jīng)典的智力題，據(jù)愛因斯坦說，全世界只有大約2%的聰明人，能夠推得出這個問題的答案。在沒有計算機的年代，相信普通人看到這個問題無從下手，聰明者基本都是以表格的方式來推導(dǎo)。計算機出現(xiàn)后很多依靠人腦無法完成的事情可以變得順利成章了。本文要介紹的方法就是這樣：以窮舉法來破解這道題。

【關(guān)鍵詞】愛因斯坦 窮舉法 Java編程 排列組合 長郡中學(xué)

1 問題描述

上個世紀，大科學(xué)家愛因斯坦提出了一道非常經(jīng)典的邏輯題，題目的內(nèi)容是這樣的：在一條街上有五個不同顏色的房間排成一排，每個房間里分別住著一個不同國籍的人，每個人都喝一種特定品牌的飲料，抽一種特定品牌的煙，養(yǎng)一種寵物，沒有任意兩個人抽相同品牌的香煙，或喝相同品牌的飲料，或養(yǎng)相同的寵物，又知：

（1）英國人住在紅房子里。

（2）瑞典人養(yǎng)狗。

（3）丹麥人喝茶。

（4）綠房子緊挨著白房子，在白房子的左邊。

（5）綠房子的主人喝咖啡。

（6）抽PALL MALL牌香煙的人養(yǎng)鳥。

（7）黃房子里的人抽DUNHILL牌的煙。

（8）住中間房子的人喝牛奶。

（9）挪威人住在第一個房子里（最左邊）。

（10）抽BLENDS香煙的人和養(yǎng)貓的人相鄰。

（11）養(yǎng)馬的人和抽DUNHILL牌香煙的人相鄰。

（12）抽BLUEMASTER牌香煙的人喝啤酒。

（13）德國人抽PRINCE牌香煙。

（14）挪威人和住藍房子的人相鄰。

（15）抽BLENDS牌香煙和喝礦泉水的人相鄰。

問題：誰在養(yǎng)魚？

2 解題思路

就這道題來說，窮舉法是最直接也是容易讓人理解的方法。所謂窮舉法的基本思想是根據(jù)題目的部分條件確定答案的大致范圍，并在此范圍內(nèi)對所有可能的情況逐一驗證，直到全部情況驗證完畢。若某個情況驗證符合題目的全部條件，則為本問題的一個解;若全部情況驗證后都不符合題目的全部條件，則本題無解。就本道題而言肯定就只有一個答案。

在正式計算之前，需要先來討論一下答案的形式和范圍。就這套題而言，有五個房子（在面向?qū)ο蟮某绦蛑蟹Q為實體），每個房子從左到右依次排列，每個房子有個序號分別從O到4（在這里就按照程序的思維來進行，從O開始進行編號），每個房子分別有五個屬性：房屋的顏色（以下簡稱顏色）、居住者的國籍（以下簡稱國籍）、居住者的喜愛的飲料（以下簡稱飲料）、居住者喜歡的香煙（以下簡稱香煙）、居住者養(yǎng)的寵物（以下簡稱寵物）。這五個屬性每種屬性有5個值，那么一共有多少個可能的解呢？為了弄清這個問題，讓我們先從一個屬性來分析，假設(shè)單單就顏色來說，總共5中顏色，分給5套房子，有多少中可能性呢？在學(xué)了數(shù)學(xué)的排列定理后，我們知道這里其實就是一個排列組合問題：

就顏色的來說，實際上就是5的全排列?？赡艿慕M合數(shù)為：5*4*3*2*1=120種排列方式。知道了就一種屬性來說有120種可能性，那么就5個屬性來說，他們的可能組合數(shù)為120*120*120*120*120= 24883200000個可能的解（這么龐大的數(shù)字，如果不做優(yōu)化就人來說幾乎就是不可能完成的）。

了解了解題思路后，接下來要做的就是分別對顏色、國籍、飲料、香煙和寵物計算出每個屬性的所有可能的排列組合并將這些組合放到5個數(shù)組里面，然后再用多層循環(huán)的方式，從每個數(shù)組中取出一個組合進行校驗：其實簡單，具體如何校驗?zāi)?？題中的15調(diào)線索，每條就是一個校驗規(guī)則。

3 解題算法

3.1 數(shù)據(jù)初始化

聲明5各列表，每個列表中依次放入相關(guān)的選項

private static List nationalities;

private static List houseColors;

private static List drinks;

private sratic List smokings;

private sratic List pets;

static{

//初始化數(shù)據(jù)

nationalities= Arrays.asList（“英國”，“瑞典”，“丹麥”，“挪威”，“德國”）;

houseColors= Arrays.asList（“紅”，“綠”，“白”，“黃”，“藍”）;

drinks= Arrays.asList（“茶”，“咖啡”，“牛奶”，“啤酒”，“礦泉水”）;

smokings= Arrays.asList（"PALLMALL"， "DUNHILL"， "BLENDS"，”BLUEMASTER"， "PRINCE"）;

pets= Arrays.asList（“狗”，“鳥”，“馬”，“貓”，“魚”）;

）

3.2 排列組合的計算

就本題而言，一個最為核心和重要的就是如何算出一組數(shù)據(jù)的排列組合。設(shè)a、b、c、d、e五個數(shù)為一組，如何算出這5個組的所有排列組合的形式。根據(jù)假設(shè)對一個有n位的數(shù)組來說，第一位有n種選擇，第2位有n.1種選擇，第一位和第二位的組合有n*（n-l）各，他們與3位的組合有n*（n-1）*（n-2）個。依次進行遞歸前面n-l位與最后一位的組合只剩下一種形式，依次得出算法如下：

/{{

*求list中元素的所有排列組合

* @param list列表中的元素

* @return

*/

public static List list）{

List

List line=newArrayList（）;

permutarion（line， lisr， result）;

return result，

）

/**

*計算所有的排列組合

* @param line前面元素的組合

* @param remains剩余還沒有組合的元素

* @param result保存最終的計算結(jié)果，里面的每個list是一種組合形式

*/

private static void permutation（Listline， List remains， List

line= cloneList（line）;

remains= cloneList（remains）;

int size= remains.size（），

if （size==1）{∥如果只有一個元素，那么就只有直接用前面的組合跟這個元素進行拼合

line.add（remains.get（0》;

result.add（line）;

return，

）

for （inti=0;i

String one= remains.get（i）;//取出某一個元素

Lisr remains2=without（remains， one）;//剔除該元素的列表

permutation（one， cloneList（line），remains2， result）;

）

）

*計算出某一個元素與前面組合的拼合結(jié)果

* @param one某個元素（下一個加入的元素）

* @param line需要加入的隊列（某個組合）

* @param remains2剩余的元素

* @param result存儲最終的結(jié)果

*/，

private static void permutation（Stringone， List Iine， List remains2，List

line= cloneList（line）;

line.add（one）;

permutation（line， remains2， result）;

）

3.3 規(guī)則檢驗

有了上一小節(jié)的排列算法，我們可以每次先對房屋（或房屋主人的）國籍、顏色、飲料、香煙、寵物算出所有的排列組合，然后循環(huán)這些組合，每次針對這五個屬性各拿出一個組合進行校驗。題中的15條線索就是15個校驗規(guī)則，我們需要針對每個規(guī)則完成一個檢查方法，某一組合符合所有的規(guī)則，那么就是正解。以第一個規(guī)則為例方法如下：

*檢查條件：英國人住在紅房子里。

* @param nationList國籍列表

* @param colorList房屋顏色

* @retum檢查通過返回true，否則返回false

private static boolean checkEnglishInRedHouse（List nationList， ListcolorList）{

int index= nationList.indexOf（“英國”）;∥獲得英國人做在的房屋序號

String color= colorList.get（index）;//獲得同一序號的房屋顏色

retum紅”equals（color）;

）

3.4 窮舉算法

在以上的算法的基礎(chǔ)，最終的窮舉算法如下：

public static void main（String[] args）{

List

List

List

List

List

index=O：

long beginTime=System.currentTimeMillis（）;

int size= nationPermutations.size（）;//

//以下針對每個屬性循環(huán)，檢驗每個解

for （intn=O;n

List nationList=nationPermutations.get（n）;

for （int c=O;c

List colorLisr=colorPermutations.get（c）;

for （int d=O;d

List drinkList=drinkPermutations.get（d）;

for （inr s=O;s

List smokeList=smokePermutations.get（s）;

for （intp=0;p

Lisr petList=petPermutations.get（p）;

index++;

if （checkPass（narionLisr，colorList， drinkList， smokeList， petList》{

//檢驗通過

System.out.println（"計算用時：”+ （System.currentTimeMillis（） -beginTime）+“毫秒”）;

printResult（nationList，colorList， drinkList， smokeList， petList）;

retum，

） else{

//System.outprintln（"error at”+index）;

）

}

}

）

）

）

System.out.println（”程序運行結(jié)束！”）;

）

3.5 算法優(yōu)化

在上一小節(jié)中，依次用了5層循環(huán)來對檢驗每個解，前面說過這樣的解一共有24883200000個。這樣的數(shù)量對于計算機來說運算次數(shù)也還是非常大的。為了最大幅度的減少運算次數(shù)，可以在外層循環(huán)中就逐步加入一些校驗規(guī)則，篩選掉一些無用的解。大致如下：

for （intn=0;n

List nationLisr=nationPermutations.get（n）;

if（！ checkFirstHouseIsNorwegian（nationList》{//檢查第一間房是否是挪威人，這個只跟nationList有關(guān)系

continue，

}

for （int c=0;c

Lisr colorList=colorPermutations.get（c）;

if （！checkGreenLeftOfWhite（colorList》{∥檢查綠色房子是否在白色房子的左邊

contmue，

}

if（ ！checkEnglishInRedHouse（nationList， colorList》{//檢查英國人是否住紅色房子

contmue，

}

if（！ checkNearbyNorwegianWirhBlueHouse（nationList， colorList》{∥挪威人和住藍房子的人相鄰

contmue，

）

for （int d = 0;d

）

）

）

提前加入校驗的原則就是，在某一層循環(huán)加入的校驗算法只與前面幾層的屬性相關(guān)，這樣校驗方法才能正常執(zhí)行。

3.6 計算結(jié)果

4 總結(jié)

采用窮舉法來解題的最直接的優(yōu)點就是直觀、便于理解。從缺點方面來說，窮舉法最大的缺點就是通常計算量都很大，但本處解題由于對程序進行了優(yōu)化，提早加入校驗方法，已經(jīng)讓計算量大幅的降低，運算效率大大提高。（程序查看和下載地址：https：//giteecom/lizhenxia/einstein）.

參考文獻

[1]張傳鵬.高考數(shù)學(xué)進階特訓(xùn)[M]。浙江：浙江大學(xué)出版社，2016.

[2]白喜琇（韓）.狄利克雷教你學(xué)選擇和排列[M].安徽：黃山書社出版，2016.

[3]明日科技.Java從入門到精通（第4版）[M].北京：清華大學(xué)出版社，2016.

[4]宋娟.Java常用算法手冊（第3版）[M].北京：中國鐵道出版社，2016.

[5] Robert Sedgewick（美），KevlnWayne（美）著;謝路云譯，算法第4版Algorithms Fourth Edition[M].北京：人民郵電出版社，2012.