Three missionaries and three cannibals must cross a river in a boat that holds one or two people. On either bank, missionaries may never be outnumbered by cannibals. EyeProlog searches the space of safe states and returns a crossing plan.
Run it in the playground · Source
A state records how many missionaries and cannibals are on the left bank and
where the boat is. The start is state(3, 3, left) and the goal is
state(0, 0, right). Which sequence of safe crossings connects them?
move(1, 0).
move(0, 1).
move(2, 0).
move(0, 2).
move(1, 1).
bank_safe(0, _c).
bank_safe(M, C) :- (M > 0), (M >= C).
Five possible boat loads. A bank is safe if it has no missionaries, or at least as many missionaries as cannibals.
crossing(state(Mleft, Cleft, left), state(Nextm, Nextc, right), carry(Movem, Movec)) :-
move(Movem, Movec),
(Nextm is Mleft - Movem),
(Nextc is Cleft - Movec),
state_safe(state(Nextm, Nextc, right)).
journey(Goal, Goal, Visited, Visited).
journey(State, Goal, Visited, Path) :-
crossing(State, Next, _carry),
\+ member(Next, Visited),
journey(Next, Goal, [Next|Visited], Path).
A crossing applies one boat load and keeps both banks safe. The journey never revisits a state, which keeps the search finite.
eyeprolog examples/missionaries-cannibals.pl
missionaries_cannibals_answer(first_solution, [state(3, 3, left), state(3, 1, right), state(3, 2, left), state(3, 0, right), state(3, 1, left), state(1, 1, right), state(2, 2, left), state(0, 2, right), state(0, 3, left), state(0, 1, right), state(1, 1, left), state(0, 0, right)]).
missionaries_cannibals_answer(state_count, 10).
missionaries_cannibals_answer(step_count, 11).
The classic 11-crossing solution. Only 10 left-bank configurations of missionaries and cannibals are safe on both banks, which is why the search is small.
step(crossing(state(0, 1, right), state(1, 1, left), carry(1, 0)),
rule(10),
['Mleft' = 0, 'Cleft' = 1, 'Nextm' = 1, 'Nextc' = 1, 'Movem' = 1, 'Movec' = 0],
[move(1, 0), 1 is 0 + 1, 1 is 1 + 0, state_safe(state(1, 1, left))]).
Near the end, one missionary rows back to the left bank, leaving one missionary and one cannibal there, a safe state. Every crossing in the plan has a step like this one.
condition('C1', resolution, ok, 53).
condition('C5', re_decision, ok, 43).
condition('C6', boundary_consistency, ok, 0).
steps(97).
verified(53).
recomputed(42).
trusted(1).
verdict(checked_with_obligations).
Rule steps replay. The arithmetic and the 11 “this state was not visited yet”
tests (\+ member/2 over a list written out in the step) are recomputed by
the checker itself. The one trusted step left is the countall/2 that counts
the safe states: it is the single obligation.
move(3, 0), move(2, 1), and move(0, 3). Is
the shortest plan shorter?once(solution(Path)) with findall/3 and count how many distinct
solutions the search finds.Learn more in The Art of EyeProlog, Chapter 24.