change(e, w).
change(w, e).
 
move([X,X,Goat,Cabbage], wolf, [Y,Y,Goat,Cabbage]) :- change(X,Y).
move([X,Wolf,X,Cabbage], goat, [Y,Wolf,Y,Cabbage]) :- change(X,Y).
move([X,Wolf,Goat,X], cabbage, [Y,Wolf,Goat,Y]) :- change(X,Y).
move([X,Wolf,Goat,Cabbage], nothing, [Y,Wolf,Goat,Cabbage]) :- change(X,Y).

oneEq(X, X, _).
oneEq(X, _, X).

safe([Man, Wolf, Goat, Cabbage]) :-
  oneEq(Man,Goat,Cabbage),
  oneEq(Man,Wolf,Goat).

solution([e,e,e,e], []).
solution(Config, [Move|Rest]) :-
  move(Config,Move,NextConfig),
  safe(NextConfig),
  solution(NextConfig, Rest).