Description

HOMEWORK #1 (6.5% OR 13 POINTS )

Your group for this homework should coincide with your term project group. In any case, indicate clearly the members who are submitting the homework. Your contact person must upload the solution (along with all the original code written) to Moodle. Just a single submission per group! Our TAs will soon send you a note explaining the mechanics of submissions.
Any programming language can be used as long as you have it up-and-running on your computer. Any group member should be prepared to give a demo (using their own computer) when requested to do so by our TAs.

In this homework, you’ll solve a variant of the following classical puzzle:
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):

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:
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).