狼山羊白菜拼图解算器中的堆栈溢出

Question

我试图在Prolog中编写程序来解决众所周知的狼山羊白菜拼图。鉴于一个想用狼，山羊和卷心菜过河的农民。船只同时举行两次，他不能与山羊或山羊一起离开狼。

我知道这里有Stackoverflow的工作解决方案。但我想在我的代码中找到用于学习目的的错误。这是我的代码。它导致了所谓的本地堆栈溢出，我想逻辑中有一个错误。由于我评论了每个区块，所以应该很容易理解。

% 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的基于外部参照编辑器突出了第一个问题：船员/ 2是从未使用过：

那么你也许想这样的定义：

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

编辑我认为下一个问题是明显的，你调用船员/ 1的方式：

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

你通过已经形成了船员，而不是由子集/ 2生成的船员。 如果你进入调试模式

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

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

Answer 2

原来有几个问题与程序，最做不局限于深度优先搜索，并允许（[F，G，W，C]，[]） - >（[W，C]，[F，G]） - >（[F，G，W，C]，[]）这将无限下降。在安全的方面也存在一些小的逻辑错误（不允许山羊或狼叶很少选择）。

作为一种学习体验，我经历了这种工作方式。我喜欢它捕获的思维过程，并希望看到它的发展。在过程中，我重新组织了一下，但它仍然应该是可识别的。我添加了一个“无撤消”移动检查与prev和“没有空右侧”检查，以切断搜索骨头路径。我还为prolog解释器添加了一些更简单的原语。但也许看到这将有助于另一个。

最终在SWI-Prolog上测试。

member(X, [X|_]). 
member(X, [_|Tail]) :- member(X, Tail). 

subset([],_). 
subset([X|L],Set):- 
    member(X,Set), 
    subset(L,Set). 

delete([], _, []). 
delete(List, [], List). 
delete([X|Tail], [X|STail], Res) :- 
    delete(Tail, STail, Res). 
delete([X|Tail], Sublist, Res) :- 
    member(X, Sublist), 
    delete(Tail, Sublist, Res). 
delete([X|Tail], Sublist, [X|Res]) :- 
    not(member(X, Sublist)), 
    delete(Tail, Sublist, Res). 

append([],L,L). 
append([H|T],L,[H|TL]) :- append(T,L,TL). 

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

safe([]). 
safe(Side) :- 
    member(farmer, Side). 
safe(Side) :- 
    not(subset([goat, wolf], Side)), 
    not(subset([goat, cabbage], Side)). 

embark(Side, Crew, Remain, Prev) :- 
    crew(Crew), 
    subset(Crew, Side), 
    not(Crew = Prev), 
    delete(Side, Crew, Remain), 
    safe(Remain). 
disembark(Side, Crew, Remain) :- 
    append(Side, Crew, Remain), 
    safe(Remain). 

cross([], Right, [], _) :- 
    subset([farmer, wolf, goat, cabbage], Right). 
cross(Left, Right, Move, Prev) :- 
    embark(Left, Crew, NewLeft, Prev), 
    disembark(Right, Crew, NewRight), 
    cross(NewLeft, NewRight, Othermoves, Crew), 
    Move = [[toright|Crew]|Othermoves]. 
cross(Left, Right, Move, Prev) :- 
    embark(Right, Crew, NewRight, Prev), 
    not(NewRight = []), 
    disembark(Left, Crew, NewLeft), 
    cross(NewLeft, NewRight, Othermoves, Crew), 
    Move = [[toleft|Crew]|Othermoves]. 

solve(Left, Right, Moves) :- 
    cross(Left, Right, Moves, []).