6. Consider the 8-puzzle problem where the goal state is: 2 3 1 8 7 4 6 5 Write a program (preferably in C, C++, or Java; your program must compile with one of the standard compilers such as gcc, g++, or javac running under Unix/Lynux) that takes as input the initial state of the 8-puzzle and uses A search to find a path from the initial state to the goal state. The program's input (i.e., the initial state of the 8-puzzle) will be a sequence of 9 digits (1 through 9) representing the location (from left to right, top to bottom) of each one of the 8 blocks (1 through 8) and the blank (9) in the initial state of the 8-puzzle. For example, the following input: 28 31 6 4 7 9 5 represents the following initial state: 283 164 7 5 Your program's output should include one line for each state in the path from the initial to the goal state. For example, when your program is run with the initial state above as input, your program's output will be as follows: 28 31 6 4 7 9 5 1238 947 6 5 where the dashed line represents all the states (one per line) in the path from the initial (i.e., the first line) to the goal (i.e., the last line). Use h(n) = number of misplaced tiles as the heuristic for A. As discussed in class, for the actions, rather than think about which tiles can move into the blank spot, try considering where the blank spot can move. Make sure you keep track of repeated states. Follow the programming guidelines and program submission instructions (if you are not using C++, ignore the parts of the guidelines that are specific to C++). Your program must compile with one of the standard compilers (e.g., gcc, g++, javac) running under Unix/Lynux