change(w, e).
change(e, w).

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

guarded_or_separated(M, M, M).
guarded_or_separated(_, A, B) :- A \= B.

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

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

solve() :-
  length(Moves, _N),
  solution([w, w, w, w], Moves),
  write(Moves), nl.