**QUESTION**

**Use only Java, or C++ for implementation**.

The A* search can be used to solve the 8-puzzle problem. There are two candidate heuristic functions:

h1 = the number of misplaced tiles

h2 = the sum of the distances of the tiles from their goal positions

You are to implement the A* using both heuristics and compare their efficiency in terms of depth of the solution and search costs. To test your program and analyze the efficiency, you should generate random problems (>1000 cases) with a variety of solution depths. Collect the data on the different solution depths that you have tested, with their corresponding search cost (# of nodes generated); and average the search costs by depth. A good testing program should test a range of possible cases (2 <= d <= 24).

Note that the average solution depth for a randomly generated 8-puzzle instance is approximately 22. A* Search Costs (nodes generated) d h1 h2 2 6 6 4 13 12 6 20 18 8 39 25 10 93 39 12 227 73 14 539 113 16 1301 211 18 3056 363 20 7276 676 22 18094 1219 24 39135 1641 Comparison of the average search costs for the A* algorithm using heuristics h1 and h2 . This data was averaged over 100 instances of the 8-puzzle for each depth.

**User Interface**: Provide at least two menu
options for your program:

1) An option to generate a solvable random 8-puzzle problem (generated by your program) then solve it using both heuristics. It should output the optimal sequence of states that result from the search, the solution depth and the search cost for each heuristic.

2) An option to input a specific 8-puzzle configuration. The input will contain the configuration for only one puzzle, in the following format (where 0 represents the empty tile and the digits are separated by a space): 1 2 4 0 5 6 8 3 7 This option should solve the entered puzzle and output the optimal sequence of states that result from the search, the solution depth and the search cost for each heuristic. Your program must test the puzzle to be sure that it is solvable. You must handle the input/output gracefully―handle exceptions.