Java or C

The 8-puzzle is comprises of tiles numbered 0..8 in a 3 X 3 grid, as shown

alongside. Formulate the 8 puzzle problem in a manner similar to the 5-puzzle

problem given in question 1, that is, define a representation of a state, the

possible actions from each state, the goal test and the step cost.

a) Write a program to search for the goal state shown in Figure 3.4

(right), starting from a random state in the 8 puzzle using A* search with the

heuristic function h(n) = number of tiles that are not in the correct place in

state n.

Input Output (please change the below to match an 8 puzzle

Your program should first prompt the user to enter an initial state in the format XXXXXX, where each

X corresponds to a digit between 0 and 5; e.g., 431502 (no spaces between digits). The output of the

program should be printed on two lines the first line should print out the goal state as Goal State is 012345. On the second line it should print out the action sequence, each

move separated by a - (e.g., Solution: D-R-D-D) found by your algorithm.