EE 562: Artificial Intelligence for Engineers

Autumn 2023

HW ASSIGNMENT 1 (Warmup): due Monday, Oct 9th at 11:59 pm (15 pts)

Solve the Missionary-Cannibal Problem (with 3 missionaries and 3 cannibals) with 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 should use Python 3 for this assignment. It is a Python warmup.
Please comment on each method, describing its purpose, arguments, and return value.
Please comment on 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.

Turn In: here

You should turn in the following:

Your well-commented code
the solutions your program finds, each being an ordered list of states from initial 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 (10 pts)
3 counters work and counts are printed at the end; THEY DO NOT HAVE TO BE THE SAME AS IN THE SAMPLE OUTPUT! (3 pts)
code is readable and well commented (2 pts)

LATE POLICY: Programs may be turned in until Thursday night, October 12 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. Having the same code with different names for the variables doesn't work either. We check. Thanks.