prolog - Wolf Goat Cabbage 拼图求解器中的堆栈溢出

Question

我尝试用 Prolog 编写一个程序来解决著名的狼山羊卷心菜难题。给一个想带着他的狼、山羊和卷心菜过河的农民。这条船只能同时容纳两个，他不能把狼和山羊或山羊和白菜分开。

我知道 Stackoverflow 上有针对此问题的有效解决方案。但出于学习目的，我想在我的代码中找出错误。这是我的代码。它导致所谓的本地堆栈溢出，我猜逻辑中存在错误。由于我对每个 block 都进行了注释，因此应该很容易理解。

% Helper function to check if first list
% is fully contained in second one.
subset([], []).
subset([E|Tail], [E|NTail]):-
    subset(Tail, NTail).
subset([_|Tail], NTail):-
    subset(Tail, NTail).

% There is space for two objects on the
% boat, but one of them must be the farmer.
crew(farmer).
crew(farmer, wolf).
crew(farmer, goat).
crew(farmer, cabbage).

% The riverside is safe if either the
% farmer is there, or not both wolf and
% goat or both goat and cabbage are there.
safe(Side) :-
    member(farmer, Side).
safe(Side) :-
    not(member(wolf, Side)),
    not(member(goat, Side)).
safe(Side) :-
    not(member(goat, Side)),
    not(member(cabbage, Side)).

% To embark, objects from one riverside,
% the crew must be valid an the riverside
% must stay safe. Disembarking is easy.
embark(Crew, Side, New) :-
    subset(Crew, Side),
    crew(Crew),
    safe(Side),
    delete(Side, Crew, New).
disembark(Crew, Side, New) :-
    append(Side, Crew, New).

% Crossing the river from one or the other side.
cross(Left, Right, Nextleft, Nextright) :-
    embark(Left, Crew, L),
    disembark(Right, Crew, R),
    cross(L, R, Nextleft, Nextright).
cross(Left, Right, Nextleft, Nextright) :-
    embark(Right, Crew, R),
    disembark(Left, Crew, L),
    cross(L, R, Nextleft, Nextright).

% Find solution to bring all objects from left
% riverside to right. Run this after consulting
% the file.
% cross([farmer, wolf, goat, cabbage], [], [], [farmer, wolf, goat, cabbage]).

这段代码有什么问题？我只是想更深入地了解 Prolog。

Answer 1

基于 SWI-Prolog 外部参照的编辑器强调了第一个问题:从未使用过 crew/2:

那么你可能需要这个定义:

crew([farmer]).
crew([farmer, wolf]).
crew([farmer, goat]).
crew([farmer, cabbage]).

编辑 我认为下一个问题在您调用 crew/1 的方式中很明显:

embark(Crew, Side, New) :-
    subset(Crew, Side),
    crew(Crew),
    safe(Side),
    delete(Side, Crew, New).

您传递的是已经组建的船员，而不是 subset/2 生成的船员。如果进入 Debug模式

?- leash(-all),trace.
true.
[trace] 3 ?- cross([farmer, wolf, goat, cabbage], [], [], L).
Call: (6) stackoverflow:cross([farmer, wolf, goat, cabbage], [], [], _G1474)
...

Exit: (8) stackoverflow:subset([farmer, wolf, goat, cabbage], [farmer, wolf, goat, cabbage])
Call: (8) stackoverflow:crew([farmer, wolf, goat, cabbage])
Fail: (8) stackoverflow:crew([farmer, wolf, goat, cabbage])
Redo: (11) stackoverflow:subset([cabbage], _G1560)
...
Exit: (8) stackoverflow:subset([farmer, wolf, goat, cabbage], [farmer, wolf, goat])
Call: (8) stackoverflow:crew([farmer, wolf, goat, cabbage])
Fail: (8) stackoverflow:crew([farmer, wolf, goat, cabbage])
Redo: (10) stackoverflow:subset([goat, cabbage], _G1557)
...

也就是说，crew总是失败...