CSE 473: Introduction to Artificial Intelligence

Autumn 2009

Solve the Missionary-Cannibal Problem (with 3 missionaries and 3 cannibals) by writing blind search methods as follows:

Requirements

You may use either depth-first search or breadth-first search.
No repeated states. When you reach a state for which there is an identical ancestor on the same path, the search backs up.
Count how many states are searched to find each solution; there are four. For your counting keep track of 3 kinds of states you generate:
- illegal states in which the cannibals eat the missionaries,
- repeated states that are the same as an ancestor state on the same path,
- total states searched (ie. all states except the illegal and repeated ones).
You may use Java, C++, or Lisp. Java is the default language and the one the TAs will write it in.
Please comment each method, describing its purpose, arguments and return value.
Please comment important sections of code; 'This is the main loop', 'This checks for repeated states', etc.
Your program should print out all paths it finds to the goal state and the three counts for each path.

You should turn in the following:

your well-commented code
the solutions your program finds, each solution being an ordered list of states from initial state to goal state. Format as follows:
(3,3,L)(3,1,R)(3,2,L)...(0,0,R)
The 3 counts: illegal count, repeat count, total count for each solution.

Evaluation: