Diagonal 15-Puzzle is a modified version of the 15-Puzzle in which the blank square may slide about a diagonal axis in addition to horizontal and vertical axes. However, the cost of each diagonal slide is 3 whereas the cost of each horizontal or vertical slide is 1. The final state of the Diagonal 15-Puzzle is as follows:
1
2
3
4
12
13
14
5
11
15
6
10
9
8
7
In this project, you are required to implement the following search methods for solving the Diagonal 15-Puzzle:
a. Uniform Cost Search
b. Iterative Lengthening Search
c. A* Heuristic Search with the admissible heuristic h1 discussed in class (h1(n) = The number of misplaced tiles at node n)
d. A* Heuristic Search with the admissible heuristic h2 discussed in class (h2(n) = The sum of the city-block distances of each misplaced tile from its current location to its goal location)
e. A* Heuristic Search with the admissible heuristic h3 which provides better solutions than h2.
In order to compare performances of these methods, your program should be able to generate random puzzle instances such that the optimum solution is at the depth d of the tree. In order to generate random puzzle instances, you may start from the final state and randomly go backwards. Note that you should prevent cycles when generating random instances.
You have to provide the following outputs:
The total number of expanded nodes
d: depth of the solution
UCS
ILS
A*-H1
A*-H2
2
4
6
8
10
12
16
20
24
28
The maximum number of nodes stored in memory
d: depth of the solution
UCS
ILS
A*-H1
A*-H2
2
4
6
8
10
12
16
20
24
28
For each entry in the above tables, you have to generate 10 random instances and report the arithmetic average. You may not be able to fill every entry in the table since it may take too long. In this case leave the corresponding entries empty.
In addition to the tables above, for each of the three instances provided below and for each algorithm, you should submit:
i. The cost of the solution found.
ii. The solution path itself (from the given initial state to the final state). iii. The number of expanded nodes. a.
1
3
4
12
13
2
5
11
14
15
6
10
9
8
7
b.
1
3
5
4
2
13
14
15
11
12
9
6
10
8
7
c.
1
13
3
4
12
11
2
5
9
8
15
7
10
6
14
