CSE 473: Introduction to Artificial Intelligence Autumn 2007

Hw Assignment 2 (Program): Due Monday, October 8th at 11:59 pm (25 pts)

Turn In Here

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

• First with a blind depth-first search using a stack and/or recursion.
• Second with a blind breadth-first search that uses a queue.

Requirements

• 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 the FIRST solution. Then have your search go on to find the other solutions. There are 4 solutions. 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
  • everything else
• You may use Java, C++, Lisp or Lisp variant.
• 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 it should find all possible paths that don't repeat states).

• 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: normal count, repeat count, dead count

Evaluation:

• depth-first search works and produces correct solutions (7 pts)
• breadth-first search works and produces correct solutions (7 pts)
• 3 counters work and counts are printed (6 pts)
• code is readable and well commented (5 pts)