$1.$ The problem description. The $8-$puzzle problem is played on $3-$by$-3$ grid with $8$ square blocks labeled $1$ through $8$ and a blank square. The goal is to rearrange the blocks so that they are in order, using as few moves as possible. 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 $($left$)$ to the goal board $($right$).2.$ Brief introduction of A$-$star search on $8-$puzzle problem We define a search node of the game to be a board, the number of moves made to reach the board, and the previous search node. First, insert the initial search node $($the initial board, $0$ moves, and a null previous search node$)$ into a priority queue $($the queue is an implementation of frontier$).$ Then, delete from the priority queue the search node with the minimum priority $($select the one with minimal evaluation function values$),$ and insert onto the priority queue all neighboring search nodes $($those can be reached in one move from the dequeued search node$).($make expansion$)$ Repeat this procedure until the search node dequeued corresponds to a goal board $($goal test$).$ The success of this approach hinges on the choice of heuristic function for a search node.