斑馬問題 Zebra Puzzle 的簡單解答

給五幢房子,設定十五則條件,問誰養斑馬。所謂斑馬問題。

對於斑馬問題,有比較一般的解題方式,說,那就遞迴吧,所以她打算要闖過 120^6 的排列取樣,找到僅有的一、二則成立的案例。

我覺得問題其實是很簡單的,即使用紙筆計算,將這一個 Horn Clause 展開出幾個案例,所需要處理的內容也不會需要寫上萬字。想了一陣子,我想可以用一份簡單、有道理的演繹系統來操作。

物件:每個物件是一筆記錄,分別代表一個房子及相關存在事物。一個物件擁有一些屬性,包括國籍、顏色、位置、飲料、寵物、煙等。

物件合併:給二個物件 A, B ,假如 A, B 能合併,則得到新物件 C 。

世界:是一些物件的集合,任何一個世界最多包含五個物件。世界可以接受輸入,而改變自己的內含,但是除此之外,世界與其他世界不能交換任何資訊。

配換函數 (commute) :給一些世界 W 以及一個物件 a ,並且稱 W 中任何一個世界為 w , a 跟 w 中的物件放在一起,成為 w’  ,稱為「配換」。如果 w’ 所包含的物件超過五個,則 w 與 w’ 都消滅。配換的結果,有更多新世界會加入 W。

吸收函數 (absort) :給一些世界 W 以及一個物件 a ,並且稱 W 中任何一個世界為 w ,則對於 w 中的任何一個物件 b,假如 a, b 能合併為 c ,則 c 取代 w 中的 b ,而使 w 變成新世界 w’ ,稱為「吸收」。假如在 w 中沒有物件能與 a 合併,則 w 消失。吸收的結果, W 中的世界數目會減少。

鄰接函數 (next-to) :給一些世界 W 以及二個物件 a, b ,並且稱 W 中任何一個世界為 w ,則 a 先對 w 做 commute 和 absorb ,得到 w’ ,接著由 b 對 w’ 做 commute 和 absorb ,最後得到 w" 。由於房子編號只有 1, 2, 3, 4, 5 ,所以當我們稱 a, b 鄰接的時候,應該要把 a, b 複製為四組,分別將各組的物件位置填上 {1, 2}, {2, 1}, {2, 3}, {3, 2}, {3, 4}, {4, 3}, {4, 5}, {5, 4} 等具體的數字。

演算法:

  1. 解題空間 S 是一些世界的集合,不過從一開始,解題空間只有一個世界,而世界是空集合。 ( S = {{}} )
  2. 第一句「英國人住紅色房子」,產生一個物件 a ,國籍「英國」,顏色「紅色」。
  3. commute(S, a) 得到 {{a}} , absorb(S, a) 得到 {} ,二者合併得到 S1 = {{a}} 。
  4. 接下來二句,「瑞典人養狗」,「丹麥人喝茶」,依序經過 commute 及 absorb 處理,最後得到 S3 = {{a,b,c}} 。
  5. 第四句,「住綠色房子的在白色房子左邊」,雖然只有指定一個方向,但是且用 next-to(S3, d, e) 省一點事。首先 d, e 實例化,依序將位置填上 {1, 2}, {2, 1}, {2, 3}, {3, 2}, {3, 4}, {4, 3}, {4, 5}, {5, 4} 等配對,然後做 next-to(S3, d, e) 所產生的全部世界合併起來。
  6. 經過若干步驟得到 S15 ,之後看 S15 中擁有非空集合的世界 w ,並且若在 w 中只有一個物件沒有填寵物屬性,則這個物件是養斑馬的一家,而且這個世界 w 是解答。
廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Problem 並標籤為 。將永久鏈結加入書籤。