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.

One error for sure is the way you call `crew(Crew)`, or rather how you define `crew`. I think you want to make that lists: `crew([farmer, wolf])`. — Christian Fritz, Jan 16 '14 at 17:23
Before running it, use 'trace.', which will allow you to step through the execution and see the point at which it is starting to run in a loop - really useful learning tool. — magus, Jan 16 '14 at 17:31
@Amicable Alright, I didn't knew that not working code is on-topic on Code Review. — danijar, Jan 16 '14 at 18:33
@magus That is a useful feature. Using `trace.` on the program, the same line is printed many times `1 1 Call: cross([farmer,wolf,goat,cabbage],[],[],[farmer,wolf,goat,cabbage]) ?`. — danijar, Jan 16 '14 at 18:35
@mbratch Actually, the last paragraph in my code is what I use as query input, as state in the comment right above. — danijar, Jan 17 '14 at 10:39
@Amicable Wait, so he's getting a __stack overflow__ but it's not on topic for _StackOverflow_? — SQB, Jan 17 '14 at 12:36

CapelliC · Accepted Answer · 2014-01-16T19:37:40.600

4

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

enter image description here

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

edited Jan 16 '14 at 19:37

answered Jan 16 '14 at 17:23

CapelliC

59,646
5
47
90

Okay, with defining the `crew` term over lists, the program prints `no` for the input `cross([farmer, wolf, goat, cabbage], [], [], [farmer, wolf, goat, cabbage]).`. – danijar Jan 16 '14 at 18:30
1

did you tried `crew(Side)` ? maybe tracing this change could suggest how to fix the problem – CapelliC Jan 17 '14 at 10:49
Trying `crew(Side)` still results in a stack overflow error and the tracing output remains the same. I would need a way to represent that the crew consists of a subset of the objects on the river side, not all of them... – danijar Jan 18 '14 at 16:25
1

I think you have a more fundamental problem. How do you avoid to visit the **same** state again ? Your solution is declarative, but remind that Prolog has limited capability (depth first search) – CapelliC Jan 18 '14 at 17:03

score 1 · Answer 2 · answered Oct 29 '14 at 17:19

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

Stack overflow in solver for Wolf Goat Cabbage puzzle

2 Answers2