/***********************************************************
taken from "Extension Table Built-ins for Prolog", 
by Chang-Guan Fa & Suzanne W. Dietrich
Software Practive and Experience, Vol22, No.7, 573-597, 1992.
Modified by Neng-Fa Zhou to find all solutions
***********************************************************/

go:-
    cputime(Start),
    state(s,s,s,s,Path,Len),
    cputime(End),
    write(Path),nl,
    T is End-Start,
    write('TIME:'),write(T),nl.

:-table state(+,+,+,+,-,min).
state(n,n,n,n,Path,Len):-Path=[],Len=0.
state(F,F,G,C,Path,Len):-
    safe(F,F,G,C),
    Path=[takes(farmer,wolf)|Path1],
    opp(F,F1),
    state(F1,F1,G,C,Path1,Len1),
    Len is Len1+1.
state(F,W,F,C,Path,Len):-
    safe(F,W,F,C),
    Path=[takes(farmer,goat)|Path1],
    opp(F,F1),
    state(F1,W,F1,C,Path1,Len1),
    Len is Len1+1.
state(F,W,G,F,Path,Len):-
    safe(F,W,G,F),
    Path=[takes(farmer,cabbage)|Path1],
    opp(F,F1),
    state(F1,W,G,F1,Path1,Len1),
    Len is Len1+1.
state(F,W,G,C,Path,Len):-
    safe(F,W,G,C),
    Path=[go_alone(farmer)|Path1],
    opp(F,F1),
    state(F1,W,G,C,Path1,Len1),
    Len is Len1+1.

opp(n,s).
opp(s,n).

safe(F,W,F,C).
safe(F,F,G,F):-
    opp(F,G).