prolog - 狼山羊卷心菜谜题解算器中的堆栈溢出

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)
...

也就是说，船员总是失败......