% Missionaries-and-cannibals river crossing as guarded state-space search.
%
% A state records missionaries and cannibals on the left bank plus the boat side.
% crossing/3 applies one legal boat load and state_safe/1 checks both banks.
% journey/4 carries a visited list to avoid loops in the finite state graph.
query(missionaries_cannibals_answer(X0, X1)).

% Boat loads: one or two passengers, with at least one passenger per crossing.
move(1, 0).
move(0, 1).
move(2, 0).
move(0, 2).
move(1, 1).

% A bank is safe if there are no missionaries or missionaries are not outnumbered.
bank_safe(0, _c).
bank_safe(M, C) :- gt(M, 0), ge(M, C).

state_safe(state(Mleft, Cleft, _boat)) :-
  between(0, 3, Mleft),
  between(0, 3, Cleft),
  sub(3, Mleft, Mright),
  sub(3, Cleft, Cright),
  bank_safe(Mleft, Cleft),
  bank_safe(Mright, Cright).

crossing(state(Mleft, Cleft, left), state(Nextm, Nextc, right), carry(Movem, Movec)) :-
  move(Movem, Movec),
  sub(Mleft, Movem, Nextm),
  sub(Cleft, Movec, Nextc),
  state_safe(state(Nextm, Nextc, right)).
crossing(state(Mleft, Cleft, right), state(Nextm, Nextc, left), carry(Movem, Movec)) :-
  move(Movem, Movec),
  add(Mleft, Movem, Nextm),
  add(Cleft, Movec, Nextc),
  state_safe(state(Nextm, Nextc, left)).

journey(Goal, Goal, Visited, Visited).
journey(State, Goal, Visited, Path) :-
  crossing(State, Next, _carry),
  not_member(Next, Visited),
  journey(Next, Goal, [Next|Visited], Path).

solution(Path) :-
  journey(state(3, 3, left), state(0, 0, right), [state(3, 3, left)], Reversepath),
  reverse(Reversepath, Path).

missionaries_cannibals_answer(first_solution, Path) :- once(solution(Path)).
missionaries_cannibals_answer(state_count, Count) :- countall(state_safe(state(_m, _c, _boat)), Count).
missionaries_cannibals_answer(step_count, Steps) :-
  once(solution(Path)),
  length(Path, States),
  sub(States, 1, Steps).