Description
In this homework, you’ll solve a variant of the following classical puzzle:
1
MISSIONARIES & CANNIBALS: A group consisting of 3 cannibals and 3 missionaries
seeks to cross a river. A boat is available which will hold up to 2 people. If the
missionaries on either side of the river are outnumbered at any time by the cannibals
on that side, even momentarily, the cannibals will do away with the unfortunate,
out-numbered missionaries. What schedule of crossings can be devised to permit the
entire party to cross safely? (Assume that the group and the boat are on the west
bank initially and that they would like to end up on the east bank eventually.)
The instance you’ll solve (by implementing a program) is as follows:
There are 6 cannibals, 6 missionaries, and a boat holding 5.
Your program must use Nondeterministic Search (Winston, Chapter 4). It must check for
repeated states. Explain, in painstaking detail, how you’ve implemented nondeterminism and
how you’ve avoided paths with loops.
What should be the output of your program? Some such sequence of moves resembling the
following will be just fine (N.B. the following solution is for the classical version, viz. 3 cannibals,
3 missionaries, and a boat holding 2):
1 See the reference on the next page for a solution. (Obviously, you should first try to come up with your
own solution. Study the reference only after that.)
REFERENCE
There are several papers that you can read about the M&C problem. I think the following is
especially well-written and you should definitely take a close look at it:
● Fraley, Robert, et al. “Graphical Solution of Difficult Crossing Puzzles.” Mathematics
Magazine, vol. 39, no. 3, 1966, pp. 151–157. www.jstor.org/stable/2689307. Accessed 1
Feb. 2021.
CAVEATS
It is crucial that you explain, in the body of your code and using block comments, how your
program does what it does. Include many inline comments too (but they shouldn’t be
trivialities).
Your program should have a means (a switch or a flag that can be set/reset) for ‘single stepping’
mode (also known as ‘tracing’) so that the TAs can inspect the intermediate stages of the
problem-solving process in an incremental fashion. This is also useful when you are debugging
the code during the development stage.
10 pts. of this homework will be awarded for the AI aspects. 3 pts. will be awarded for the SWE
aspects.
For the AI part: 7 pts. for finding a loop-free solution. 3 additional pts. if this solution
consists of 7 river crossings.
For the SWE part: 3 (good quality software), 2 (average quality software), 1 (poor quality
software).
Late submissions will first have 2 points deducted categorically. Then they’ll have 1 point
deducted for every late day. (A new day begins at midnight.)
