% Wolf, goat and cabbage puzzle, adapted from Eyelet's
% input/wolf-goat-cabbage.pl.
%
% A configuration is [man, wolf, goat, cabbage], where each item is on the west
% bank w or east bank e.  The recursive search keeps a visited list so Eyelog
% explores the finite state space without looping.

memoize(solve, 4).

solution(Moves) :-
  solve([w, w, w, w], [e, e, e, e], [[w, w, w, w]], Moves),
  length(Moves, 7).

solve(Config, Config, _Visited, []).

solve(Config, Goal, Visited, [Move|Rest]) :-
  move(Config, Move, NextConfig),
  safe(NextConfig),
  not_member(NextConfig, Visited),
  solve(NextConfig, Goal, [NextConfig|Visited], Rest).

% Each move transforms one configuration into another.
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).

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

% Safe if the goat is not left alone with the wolf or cabbage without the man.
safe([Man, Wolf, Goat, Cabbage]) :-
  one_eq(Man, Goat, Wolf),
  one_eq(Man, Goat, Cabbage).

one_eq(X, X, _).
one_eq(X, _, X).

triple(puzzle, solution, Moves) :-
  solution(Moves).

triple(puzzle, solved, true) :-
  solution(_Moves).