Problem Description
For some unknown reason, three cannibals and
three missionaries are traveling together and come to river that they must
cross. There is a boat on their side of the river that can be used,
but unfortunately, it only holds two people at a time. And,
while the cannibals will cooperatively share the task of river crossing,
if the number of cannibals on either bank is greater than the number of
missionaries at any time, old habits will kick in and the outnumbered
missionaries will be eaten!
Can you plan the crossings necessary to
successfully get all 6 travelers across the river in good
condition?
Background & Techniques
A few weeks ago, I received an email from a student studying C, (poor
fellow!) inquiring about a program to solve this problem. I sent him
text description of the approach I'd take but decided not to code the
program right away. No sense of making his homework assignment too
easy! I guess it must have been due by now, so I coded
it up, "just for fun".
I skipped the animation in this version, but it does allow user play by
specifying the boat occupants for each crossing. And of
course, the program will search for (and find) a solution. Four
solutions actually.
Moves are made by clicking one of the 5 possible combinations of boat
occupants for the crossing (1 or 2 cannibals, 1 or 2 missionaries, or one of each).
The game is over when cannibals exceed missionaries on either bank or all six
members are on the right bank.
Non-programmers are welcome to read on, but may
want to skip to the bottom of this page to
download an executable version of the program.
The fun part in coding this puzzle is defining
the search mechanism to find the moves that get all across the river
safely.
This is a typical graph search problem that is
most easily solved by a recursive depth first
search. The first step in these problems is to
find a good data representation for the game states. In this case, a
state is defined by the number of cannibals and missionaries are on each
bank, and where the boat is located. Since there are only two
positions for the boat and they alternate, we can always tell where the
boat by whether the current move count is odd or even. And we do not
need to keep track of occupancy of both river banks - knowing one tells us
the other. So, a single pair of numbers representing left bank
cannibals and missionary counts and the current move count is all we
need.
Google returns about a hundred hits for cannibals
missionaries recursive depth first, so I
won't re-chew that cabbage
here. There are a couple of tricks worth mentioning: