In this assignment(IN PYTHON), you are going to write a program that solves the eight puzzle problem. You will solve it using 1) [20 points] Iterative deepening depth-first search (100 cases in the given file) 2) [20 points] A* with the Misplaced Tile heuristic (100 cases in the given file) 3) [20 points] A* with the Manhattan Distance heuristic (100 cases in the given file) 4) [20 points] Breadth First Search (only required for graduate students, first 20 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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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