The Eight Puzzle, A Star Search you are going to write a program in Python 3 that solves the eight puzzle problem. You will solve it using 1) [20 points] A* with the Misplaced Tile heuristic (100 cases in the given file) 2) [20 points] A* with the Manhattan Distance heuristic (100 cases in the given file) To test your program and analyze the efficiency, you need to test your program on the 100 different input cases. (20 cases for BFS since BFS will take much longer than the others, 100 cases for Iterative deepening depth-first search and the two types of A* searches). The input data is Input8PuzzleCases.txt. This file contains a hundred different states of 8-puzzle. All of the given cases are solvable.

For example, 3, 2, 4, 5, 8, 6, 0, 1,

You need to find solutions for all 100 different states to the goal state. The Goal state is

0, 1, 2, 3, 4, 5, 6, 7, 8,

(Note: File name with the data)

(Note: There are 100 line, but to make it easy I have put few lines only)

Input8PuzzleCases.txt

8, 7, 5, 4, 1, 2, 3, 0, 6 7, 8, 6, 0, 2, 5, 1, 4, 3 1, 0, 7, 5, 3, 6, 8, 4, 2 3, 8, 4, 0, 1, 7, 5, 2, 6 6, 1, 2, 7, 0, 8, 5, 4, 3 2, 5, 3, 1, 4, 6, 8, 0, 7 6, 8, 5, 3, 4, 7, 2, 1, 0 2, 7, 8, 0, 1, 5, 4, 3, 6 6, 5, 2, 1, 4, 8, 0, 7, 3 0, 6, 1, 3, 4, 7, 8, 5, 2 8, 5, 1, 7, 3, 2, 4, 6, 0 4, 2, 7, 1, 5, 0, 8, 6, 3 2, 7, 5, 8, 4, 6, 3, 0, 1 6, 5, 8, 0, 2, 1, 7, 4, 3 8, 5, 6, 2, 7, 0, 1, 4, 3 2, 0, 7, 5, 1, 8, 6, 3, 4 4, 2, 5, 7, 3, 1, 6, 8, 0 7, 2, 0, 1, 3, 4, 6, 5, 8