change(o, l).
change(l, o).

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, Wolf, Goat),
  oneEq(Man, Goat, Cabbage).

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