I am trying to solve the The Farmer, Goat, Wolf, Cabbage riddle in Prolog using the Breadth First technique and I am running into some issues. When I try to gather all the valid combinations for the second level of the tree it fails. Here is the relevant code,
extend([Node|Path], NewPaths) :-
bagof([NewNode, Node|Path],
(s(Node, NewNode), not(member(NewNode, [Node|Path]))),
NewPaths),
!.
extend(Path, []).
s(state(X,X,W,C), state(Y,Y,W,C))
:- opp(X,Y), not(unsafe(state(Y,Y,W,C))).
s(state(X,G,X,C), state(Y,G,Y,C))
:- opp(X,Y), not(unsafe(state(Y,G,Y,C))).
s(state(X,G,W,X), state(Y,G,W,Y))
:- opp(X,Y), not(unsafe(state(Y,G,W,Y))).
s(state(X,G,W,C), state(Y,G,W,C))
:- opp(X,Y), not(unsafe(state(Y,G,W,C))).
s(state(F,G,W,C), state(F,G,W,C))
:- fail.
opp(e,w).
opp(w,e).
unsafe(state(X,Y,Y,C)) :- opp(X,Y).
unsafe(state(X,Y,W,Y)) :- opp(X,Y).
not(P) :-
P, !, fail
;
true.
The extend predicate is where I am seeing the issues. When I run it on the first level, it works fine,
?- extend([state(e,e,e,e)],[X]).
X = [state(w,w,e,e),state(e,e,e,e)]
When I run the second level, it fails,
?- extend([state(w,w,e,e)],[X]).
no
It should return something like the following,
X = [state(e,w,e,e),state(w,w,e,e),state(e,e,e,e)]
Thanks in advance for all your help, as it is much appreciated.
Regards,
Darian
If I query your code I get
?- extend([state(w,w,e,e)],X).
X = [[state(e, e, e, e), state(w, w, e, e)], [state(e, w, e, e), state(w, w, e, e)]]
X is a list of lists. Then I simplified the extend/2 predicate,
extend([Node|Path], [Node|NewPaths]) :-
bagof(NewNode,
(s(Node, NewNode), not(member(NewNode, Path))),
NewPaths).
and I get
?- extend([state(w,w,e,e)],X).
X = [state(w, w, e, e), state(e, e, e, e), state(e, w, e, e)].
Note that I'm not using [X]
querying extend/2.
BTW this clause is useless
s(state(F,G,W,C), state(F,G,W,C))
:- fail.