1

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

2
  • 1
    Did you look at the Cannibals/Missionaries question? It's extremely similar. Mar 6, 2014 at 5:31
  • @DanielLyons - Thanks for the link, it was extremely helpful in finishing my program. Mar 9, 2014 at 2:11

1 Answer 1

0

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.
1
  • Thanks, this was the answer that got me passed my road block. Mar 9, 2014 at 2:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.