用 Prolog 解狼、羊、捲心菜問題

因為網友提到「狼羊與捲心菜」的問題,回憶了一下過去所想過的,這個問題的特質,同時也想了一下 Prolog 的特性,然後寫了解題程式。

農夫帶著三樣物品要過河,一艘船只能讓農夫運送一樣物品。如果農夫不在場,那麼,狼狗可能會咬羊,而羊可能會吃掉捲心菜。所以,在 Prolog 中,物件設定如下:有羊、有狼狗,有捲心菜,還有一個農夫。安全的情況是,只要農夫在,一切都安全,否則,狗羊共處有危險,或者羊菜共處也有危險。

object(sheep).
object(dog).
object(cabbage).
object(peasant).

objects(List) :- bagof(X, object(X), List).

safe(List) :- member(peasant, List), !.
safe(List) :- member(sheep, List), member(dog, List), !, fail.
safe(List) :- member(sheep, List), member(cabbage, List), !, fail.
safe(_).

移動及問題構成的方式如下:移動物品的狀態,牽涉到兩岸物品的狀態 ([List, List1]) 和移動的紀錄 (History) 。移動的方式,分為去程與返程。當去程時,農夫的意願是都要帶上一件物品。而當返程時,則是農夫在確定沒有危險情況時,寧願自己一個人駛回。每一個移動步驟的產生,都需要做二次確認,第一次是確認農夫上船之後,岸上剩餘的生物不會受到侵害,第二次是確認所打算產生的運送動作,所造成的兩岸狀態,過去從來沒有出現過。否則假如持續產生了曾經出現的兩岸狀態,問題就會陷入無窮的循環。

move(List, List1) :-
    move(List, [], [], List1).

move([[],_], _, Acc, List) :- !,
    list:reverse(Acc, List).
move([List,List1], History, Acc, List3) :- member(peasant, List), !,
    safe_to_leave(peasant, X, List, List4),
    Stage = [List4,[peasant,X|List1]],
    not(member(Stage, History)),
    move(Stage, [Stage|History], [[peasant,X]|Acc], List3).
move([List,List1], History, Acc, List3) :- member(peasant, List1),
    safe_to_leave(peasant, List1, List4), !,
    Stage = [[peasant|List],List4],
    not(member(Stage, History)),
    move(Stage, [Stage|History], [[peasant]|Acc], List3).
move([List,List1], History, Acc, List3) :- member(peasant, List1),
    safe_to_leave(peasant, X, List1, List4),
    Stage = [[peasant,X|List],List4],
    not(member(Stage, History)),
    move(Stage, [Stage|History], [[peasant,X]|Acc], List3).

safe_to_leave(peasant, List, List1) :-
    bagof(Z, (member(Z,List), Z \= peasant), List1),
    safe(List1).

safe_to_leave(peasant, X, [peasant,X], []) :- !.
safe_to_leave(peasant, X, [X,peasant], []) :- !.
safe_to_leave(peasant, X, List, List1) :-
    member(X,List), X \= peasant,
    bagof(Z, (member(Z,List), Z \= peasant, Z \= X), List1),
    safe(List1).

question :-
    objects(List),
    move([List,[]], Answer),
    format('~p~n', [Answer]).

值得一提的是,狼羊與捲心菜問題是一連串狀態變化,而函數語言或 Prolog 邏輯語言都有一種程式格式,稱為 Accumulating Parameters ,即上述 move/4 的參數 Acc 。 Acc 除了是遞迴所需要的 accumulator 之外,同時也代表所產生的解題步驟。

Prolog 程式列在 https://github.com/YauHsien/puzzles/blob/master/src/boat.pl

廣告

About 黃耀賢 (Yau-Hsien Huang)

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