Program 5

Missionaries and Cannibals

due Thursday, April 27^th by the start of lab

Lab Partners

Everyone is encouraged to work with one lab partner (who is in the same lab section as yourself) on this assignment. If you do work with a partner, submit one solution with both of your names on it. Also, please look at the class collaboration policy so that you know what is and what isn't allowed.

Problem Description

Three missionaries, three cannibals and a boat all begin on the left bank of a wide, crocodile-infested river. The object of this problem is to figure out how to transport everyone safely to the right bank of the river. The boat must have at least one person in it to cross the river, but can carry no more than two. Also, if the cannibals ever outnumber the missionaries on either side of the river, the cannibals will eat the missionaries. For the purposes of counting, when the boat touches a bank, count the people in the boat as being on that side of the river.

Assignment

Use a queue to search for a solution using a simplified version of breadth-first search. Once a solution is found, print it. The purpose of this assignment is to give you experience with the queue abstract data type (ADT).

Simplified Breadth-First Search Algorithm

1. Initialize the queue to contain the start state
2. While the queue is not empty
   1. Remove the first item in the queue
   2. If this item is the goal state, quit the loop
   3. Otherwise figure out all legal states that this state can produce in one move. Add any legal state to the queue, unless it is already present in the queue.
3. If a solution was found, print it

Requirements and Grading

• 50 points. A correct solution is found using the simplified version of breadth-first search described above. Your solution should be general enough to be easily modifiable to solve problems where the number of cannibals and missionaries who start on the left bank of the river are 3, 2, 1 or 0.
• 10 points. The solution path is displayed in an easy to read format, starting with the start state and then going step-by-step to the goal state.
• 20 points. The built-in LinkedList class that implements the Queue interface is used effectively.
• 20 points. The program uses good style. This includes factors such as appropriate commenting (including Javadoc), good object oriented design, readable code that is high quality, etc.

Extra Credit

• 5 points. Display the solution to the problem using a GUI.
• 5 points. Enhance the breadth-first search algorithm so that it never places the same state into the queue more than once.

What to Submit

E-mail your code to your lab TA in one message. The subject of the message should be: CS221-xx program5 your-names. The xx is the number of your lab section. Your lab TA must receive your e-mail by the start of your lab period on the date on which the assignment is due. No late programs will be accepted for this assignment.