Mini-Project 1 Implement A* search

Comp 472 Mini-Project 1 
Goal: Implement A* search and test different heuristics for the 8-puzzle using the goal state from the book:
1 2 3
8 _ 4
7 6 5
Input: a state is a board configuration in form of a list. The board configuration of the goal state would be
represented as: ‘(1 2 3 8 B 4 7 6 5). Remember, that not all initial configurations can be transformed into this
goal configuration, take care with your test examples to be solvable.
Output: A list of successive states, beginning with the start state and ending with the goal state, and including
all states required to transform the start state into the goal state. For admissible heuristics this path should be
optimal.
Description:
1. Implement a general search as described on the slides, with OPEN and CLOSED lists. Implement different
OPEN list orderings (for best-first, depth-first, Best-First, and A* (2.5pts, Attrib. 5)
2. Implement a successor state generator for the 8-puzzle (2.5pts, Attrib 5)
3. Implement Hamming distance, Manhatten distance, Permutation Inversion heuristics for the 8-puzzle (2pts,
Attrib. 5)
4. Compare the length of the search path and the optimality of the solution found for Best-First and A* for
the three admissible heuristics mentioned above plus an inadmissible heuristic (you may use the one from
Assignment 1) (1pt, Attrib 1,4)
5. On March 10, 2022, I will post an initial configuration that you have to solve with your code. Report on
your solution in your report. (1pt, Attrib 5,4)
6. Provide ample and clear documentation in-line in your code and in a report. The report should be an
electronic document in .pdf that shows how the different heuristics perform on different test runs for both,
Best-First and A* (in tabular form) with some analysis and explanation. Explain what happens for the
inadmissible heuristic. (Make sure the marker knows which one is the inadmissible one in the code, too.)
Explain how many experiments you have run to compile the table (1pt, Attrib 1,4)
Submit your work in Moodle.