1. Write programs to solve the 8-puzzle problem using
(a) Iterative Deepening search up to one million nodes expanded, or when a goal node is reached.
(b) A search using the two di erent heuristics mentioned in the book, i.e. num-ber of misplaced tile, and sum of Manhattan distances.
You should also report the number of moves used in each search method and the paths found.
Your program should get input from keyboard (or by input redirection) a list of 9 numbers, the rst number will be the rst tile in the rst row, the second number the second tile in the rst row, the fourth number the rst tile in the second row
. Input 0 for the empty tile.
Use the initial and goal states as in g 28, p.24 of lecture notes of chapter 4.
You can use either C++, Java or Python for programming. Discuss with the tutor if you want to use other programming languages.
2. The missionary and cannibals problem: Three missionaries and three cannibals are on one side of the river, along with a boat that can hold one or two people. Find a way to get everyone to the other side without ever leaving a group of missionaries in one place outnumbered by the cannibals in that place.
Formulate the problem as a state-space search problem, and solve the problem by a suitable searching strategy, using either C++, Java or Python implementation, and report the path found.
1
