CSE 415: Artificial Intelligence Winter 2006

Homework Assignment 1: Due Wednesday, January 18, 11:59pm

The assignment is to write a program that solves the Missionary-Cannibal Problem, using a depth-first tree search. The algorithm for general tree search is given on page 72 of your text. Use that as a guideline, but you don't have to use the exact code. The search should back up if it comes to a dead state. It should find all 4 solutions and should, for each, print the path from the start state to the end state. Then print the number of states searched. The output should look something like this:

Solution 1
(3,3,L) (X,X,X) (X,X,X) ... (X,X,X)

Solution 2
(3,3,L) (Y,Y,Y) (Y,Y,Y) ... (Y,Y,Y)
etc.

Number of States Searched: NN

• You may use Java, C++, Lisp or Lisp variant. Check with Tyler for permission to use anything else.
• 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 code and a file containing the output of running your program should be emailed to Tyler on the due date: trobison@cs.washington.edu