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:
- A recursive search does not really needed to
keep track of game states since each call just makes it's move and
calls itself to make the next move. But i wanted to allow manual
play to be able to also retract a move and for that I used a
"trick" that can simplify things at time - the Objects
array associated with a stringlist can also hold a list of
integers, In this case, 10 times the number of left-bank
cannibals + the number of left-bank missionaries forms an integer that
will allow us to move back up the move list.
- The "Visited" array which keeps us from looping is
a 4 X 4 X 2 array of boolean (true-false) values representing the 32
possible game states. Cells are set to true when a move
results in that state (e.g. Visited[2,3,true] is set to
true to indicate that we have 2 cannibals, 3 missionaries and the boat
on the left bank).
Enjoy!
Running/Exploring the Program
Suggestions for Further Explorations
 |
Animated
graphics of crossings. |
|
Variations
- multiple boats, more (or fewer) cannibals and missionaries. |
| Original Date: April 25, 2004 |
Modified: July 21, 2006
|
|
