Apparently, many generations of computer scientists have been concerned with the problem of letting cannibals and missionaries crossing a river with the very same boat.
Before them, logicians were looking for a way to have married couples doing the very same thing with slightly different inherent problems.
Centuries ago, the problem was that no woman should be with another man without her husband being present (this is now called a threesome). However, since women now are emancipated and nobody cares if a woman is with another man (with the possible exception of her own husband, especially when there are no football matches on TV), the cannibal problem seems more interesting.
It is widely accepted that if missionaries outnumber cannibals, they convert the cannibals. Since we believe in freedom of cult, no cannibal shall be converted. Someone may be familiar with another version of this problem, since once having people converted was considering a good thing, while having missionaries eaten was
bad.
However, recently cannibals became vegans and until Churches will develop soy-missionaries the problem is how to let cannibals retain their own religion.
Basically, this is the job for a Prolog interpreter. Though humans solved this problem long ago, a human can only solve the problem for small numbers of cannibals and missionary (and though we hope both populations remain small in number, cannibals can always mate and missionaries can convert new people).
This is a short Prolog program that given an initial state (all cannibals and all missionaries on the same side of the river) and the desired final state (all cannibals and missionaries on the other side of the river), computes the strategy our poor bootman has to pursue in order to carry over the whole lot of people.
initial_state(mc, mc(left, bank(3,3), bank(0,0))).
final_state(mc(right, bank(0,0), bank(3,3))).
Above we say that the initial state has the boat on the left, three cannibals and three missionaries are on the left bank and no one is on the other one. The final state encodes what we have already said.
Now we have to describe possible moves:
move(mc(left, L, _R), Boat) :-
choose_passengers(L, Boat).
move(mc(right, _L, R), Boat) :-
choose_passengers(R, Boat).
choose_passengers(bank(C, _M), boat(2, 0)) :-
C > 1.
choose_passengers(bank(_C, M), boat(0, 2)) :-
M > 1.
choose_passengers(bank(C, M), boat(1, 1)) :-
C > 0, M > 0.
choose_passengers(bank(C, _M), boat(1, 0)) :-
C > 0.
choose_passengers(bank(_C, M), boat(0, 1)) :-
M > 0.
Basically, when the boat is on the left bank, we choose passengers from the left bank. When the boat is on the right bank, we choose passengers from the right bank. We can only take 2 people on the boat. That means that, provided there is enough people on the bank, we can only carry 2 cannibals, 2 missionaries, 1 cannibal, 1 missionary or 1 cannibal and 1 missionary. Since the boatman is usually agnostic, the cannibal aboard with one missionary is not going to be converted.
The Prolog system choses one of the possible moves and proceeds. If the move is wrong, it back-tracks and tries another solution. Until the number of choices is small, it is rather efficient.
The predicates that describe how the system changes when one move is performed are:
update(mc(B, L, R), Boat, mc(B1, L1, R1)) :-
update_boat(B, B1),
update_banks(Boat, B, L, R, L1, R1).
update_boat(left, right).
update_boat(right, left).
update_banks(alone, _B, L, R, L, R).
update_banks(boat(C, M), left,
bank(LC, LM), bank(RC, RM),
bank(LC1, LM1), bank(RC1, RM1)) :-
LM1 is LM - M,
RM1 is RM + M,
LC1 is LC - C,
RC1 is RC + C.
update_banks(boat(C, M), right,
bank(LC, LM), bank(RC, RM),
bank(LC1, LM1), bank(RC1, RM1)) :-
LM1 is LM + M,
RM1 is RM - M,
LC1 is LC + C,
RC1 is RC - C.
Eventually, we have to tell legal and illegal configurations apart. Basically, if in the bank we leave there are more missionaries than cannibals, we are breaking the law. If not, everything is fine (since the boatman works for free, so he does not have to pay taxes).
legal(mc(left, _L, R)) :-
\+ illegal(R).
legal(mc(right, L, _R)) :-
\+ illegal(L).
illegal(bank(C, M)) :-
M > C.
The solution algorithm is trivial:
solve_dfs(State, _History, []) :-
final_state(State).
solve_dfs(State, History, [Move|Moves]) :-
move(State, Move),
update(State, Move, State1),
legal(State1),
\+ member(State1, History),
solve_dfs(State1, [State1|History], Moves).
print_moves([]).
print_moves([M|Ms]) :-
writeln(M),
print_moves(Ms).
go :-
initial_state(mc, State),
solve_dfs(State, [State], Moves),
print_moves(Moves).
We generate new moves and check if the updated state would be legal and if we did not get in the same state before (if it happens we are looping, the boatman becomes hungry and eats whoever is on his boat -- that’s the main reason why he does not travel with the empty boat).
The full source is here:
