狼、羊與捲心菜問題 Prolog

狼、羊、捲心菜。

同樣的益智問題,不曉得寫過多少次。只要網路上的技術論壇,當有人提起這個問題時,就像將釣鉤丟進池子裡,釣起一堆忙著動腦的閒人。

昨晚因為看到陳鍾誠寫了 JavaScript 版本,就跟著寫我的 Prolog 版本。完成的程式位於 https://github.com/YauHsien/work/blob/master/src/wolf_sheep_cabbage.prolog

問題的形式分析都是最有趣的體驗。

我採取三個物件分別放在兩岸的觀點,看這問題只有八個狀態( 2^3 = 8 )。這問題真的很小。(主人的位置不算數,因為我們只需要觀看任何一個狀態是不是安全的,若有個狀態是不安全的,就應該避開它。)

八個狀態,可以列為四個階段。起始階段只有 [wolf, sheep, cabbage], [none, none, none] 的情況。終止階段只有 [none, none, none], [wolf, sheep, cabbage] 的情況。而其他二個階段,分別代表已經移動了一個物件過去對岸的階段,以及已經移動了二個物件過去對岸的階段。

於是,第二個階段有三種狀態:

  • [none, sheep, cabbage], [wolf, none, none];
  • [wolf, none, cabbage], [none, sheep, none];
  • [wolf, sheep, none], [none, none, cabbage]

而第三個階段也有三種狀態:

  • [none, none, cabbage], [wolf, sheep, none];
  • [none, sheep, none], [wolf, none, cabbage];
  • [wolf, none, none], [none, sheep, cabbage]

以程式中的 forward/4 或 step/5 ,能列出安全地移動一個物件到對岸的情況,而且這個步驟只會在介於第一、二階段之間,或介於第三、四階段之間。而第二、三階段之間,只有從第二階段的 [wolf, none, cabbage], [none, sheep, none] 轉換為第三階段的 [none, sheep, none], [wolf, none, cabbage] ,是保證安全的階段轉換,而這樣的階段轉換隱含了好幾個移動步驟:我們需要將狼送過去,將羊帶回來,然後將捲心菜送過去。

經過整理之後,移動的步驟分為二大類:一類是主人運送一個物件過去對岸,然後從對岸帶回零或一個物件;另一類步驟則是主人運送最後一個物件過去對岸,並且結束全部的行程。

因此,移動的策略有三種:

策略一,安全地移動一個物件到對岸,並且從對岸帶回零個物件。

策略二,安全地移動最後一個物件到對岸。

策略三,以移動一個物件過去對岸,並且從對岸帶回一個物件,使狀態從第二、三階段轉變為同一階段的另一個狀態,而在後來的那個狀態,可以進行策略一的移動策略。

心得

狼、羊與捲心菜問題非常小,小到當你在寫程式時,可能會拿捏不定要寫一個比較大的深度搜尋程式,還是寫一些比較小而直接有效的程式。

我較喜歡用不通用化的邏輯敘述來勾勒這個問題的邊界,包括:不著急於使用迭代程式來處理 list ,而是將每個 ground 敘述句寫得清楚一點,就已經足夠呈現這個小小的邏輯系統。

廣告

About 黃耀賢 (Yau-Hsien Huang)

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