CSE 473: Introduction to Artificial Intelligence

Winter 2019

HW ASSIGNMENT 1 (Warmup): due Wednesday, January 16 at 11:59 pm (10 pts)

Solve the Missionary-Cannibal Problem (with 3 missionaries and 3 cannibals) with a RECURSIVE DEPTH-FIRST SEARCH as follows:

Requirements:

You MUST use a recursive depth-first search. No frontier. Just simple recursion, up and down the search tree. It is usually called a backtracking search.
No repeated states. When you reach a state for which there is an identical ancestor on the same path, the search backs up. For this, you will need to keep a stack of the path above the current state.
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 MUST use Python 2.7 for this assignment. It is a Python warmup.
Please comment each method, describing its purpose, arguments and return value.
Please comment important sections of code; 'This is the main search', 'This checks for repeated states', etc.
Your program should print out all paths it finds to the goal state and the three counts for the search as a whole.

Note:

Don't count invalid states, e.g., (-1, 2, R), (2, -2, L), etc., as the illegal states, since these states don't exist.

Turn In: here

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 the search as a whole.

Evaluation:

search works and produces correct solutions (6 pts)
3 counters work and counts are printed at the end (2 pts)
code is readable, well commented, and follows the submission format on Canvas (2 pts)

LATE POLICY: Programs may be turned in until Friday night, January 18 at 11:59pm. 10% off for each day late.

CHEATING POLICY: All work on this assignment must be your own. You may discuss the assignment with other members of the class, but your code should not look like anyone else's code in this class, any other class or on the web. Having the same code with different names for the variables doesn't work either. We check. Thanks.