8 puzzle solver using a*

Problem: Write a program to solve the 8-puzzle problem (and its natural generalizations) using the A* search algorithm. The 8-puzzle is played on a 3-by-3 grid with 8 square blocks labeled 1 through 8 and a blank square. Your goal is to rearrange the blocks so that they are in order. You are permitted to slide blocks horizontally or vertically into the blank square. The following shows a sequence of legal moves from an initial board position (left) to the goal position (right). 1 3 1 3 1 2 3 1 2 3 1 2 3 4 2 5 => 4 2 5 => 4 5 => 4 5 => 4 5 6 7 8 6 7 8 6 7 8 6 7 8 6 7 8 Initial Goal Write a program [login to view URL] that reads the initial board from standard input and prints to standard output a sequence of board positions that solves the puzzle in the fewest number of moves (Hint Use Best First Search). Also print out the total number of moves and the total number of states ever enqueued. The input will consist of the board dimension N followed by the N-by-N initial board position. The input format uses 0 to represent the blank square. As an example, % more [login to view URL] 3 0 1 3 4 2 5 7 8 6 % java Solver < [login to view URL] 1 3 4 2 5 7 8 6 1 3 4 2 5 7 8 6 1 2 3 4 5 7 8 6 1 2 3 4 5 7 8 6 1 2 3 4 5 6 7 8 Number of states enqueued = 10 Minimum number of moves = 4 Note that your program should work for arbitrary N-by-N boards (for any N greater than 1), even if it is too slow to solve some of them in a reasonable amount of time. Not all initial board positions can lead to the goal state. Modify your program to detect and report such situations. % more [login to view URL] 3 1 2 3 4 5 6 8 7 0 % java Solver < [login to view URL] No solution possible Other details are attached