Stack overflow in solver for Wolf Goat Cabbage puzzle

Question

I tried to write a program in Prolog to solve the well known Wolf Goat Cabbage puzzle. Given a farmer who wants to cross the river with his wolf, goat and cabbage. The boat only holds two at the same time and he cannot leave wolf with goat or goat with cabbage.

I'm aware that there are working solutions to this problem here on Stackoverflow. But I would like to find the fault in my code for learning purpose. This is my code. It results in a so called local stack overflow and I guess there is an error in the logic. Since I commented every block, it should be easy to understand.

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

What is wrong with this code? I just try to understand Prolog more in depth.

Answer 1

SWI-Prolog xref-based editor highlights the first problem: crew/2 is never used:

Then you maybe want this definition:

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

edit I think the next problem is apparent in the way you call crew/1:

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

you're passing an already formed crew instead of the one as generated by subset/2. If you enter debug mode

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

that is, crew always fails...

Answer 2

It turns out there were several problems with the program, most to do with not limited the depth-first search and allowing cycles like ([F,G,W,C], [])-->([W,C], [F,G])-->([F,G,W,C], []), which will descend infinitely. There were also some small logic errors in things like safe (not allowing either goat or wolf leaves few options).

As a learning experience, I went through and got this approach to work. I liked the thought process it captures, and wanted to see it developed. In the course of things, I've re-organized it a bit, but it should still be recognizable. I added a "no undo" move check with prev, and an "no empty right side" check, to cut off search on bone-headed paths. I've also added some primitives for prolog interpreters that are more bare-bones. But maybe seeing this will help another.

Tested on SWI-Prolog in the end.

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, []).