/*
** The representation we use is  config(Man, Wolf, Goat, Cabbage),
** where each of the arguments is either east or west.
*/

solve(Moves) :-
    initial(Config), length(Moves, _), solve(Config, Moves).

initial(config(east, east, east, east)).
final(config(west, west, west, west)).

/* solve(+Config, -Moves) */
solve(Config, []) :- final(Config).
solve(Config, [Move|Moves]) :-
    move(Config, Move, NextConfig), safe(NextConfig), solve(NextConfig, Moves).

move(config(X,X,G,C), wolf, config(NewX,NewX,G,C)) :- opposite(X, NewX).
move(config(X,W,X,C), goat, config(NewX,W,NewX,C)) :- opposite(X, NewX).
move(config(X,W,G,X), cabbage, config(NewX,W,G,NewX)) :- opposite(X, NewX).
move(config(X,W,G,C), nothing, config(NewX,W,G,C)) :- opposite(X, NewX).

opposite(east, west).
opposite(west, east).

safe(config(Man,Wolf,Goat,Cabbage)) :-
    with_man_or_opposite(Man,Wolf,Goat), with_man_or_opposite(Man,Goat,Cabbage).

with_man_or_opposite(Coast,Coast,Coast).
with_man_or_opposite(_,Coast1,Coast2) :- opposite(Coast1,Coast2).