(Solved): sample input and output 1 2 5 4 3 6 7 8 1 4 2 5 3 6 7 8 Sample input: 1 4 2 -1 5 3 6 7 8 //a seque ...

sample input and output

1 2
5 4 3
6 7 8

1 4 2
5 3
6 7 8

Sample input:
1 4 2 -1 5 3 6 7 8 //a sequence of 9 numbers representing the initial state.
1 2 -1 5 4 3 6 7 8 //a sequence of 9 numbers representing the final state.
Sample output:
PATH FOUND // if no path exists print: “NO PATH FOUND” and end output
Moves: RIGHT -> UP -> RIGHT
Path:
1 4 2
-1 5 3
6 7 8
--->
1 4 2
5 -1 3
6 7 8
--->
1 -1 2
5 4 3
6 7 8
--->
1 2 -1
5 4 3
6 7 8

In this problem you are to output the solution to the 8 -puzzle problem, i.e., to find the sequence of moves from some initial configuration/state of the puzzle to a final state. As for the moves consider moving the blank tile moving UP, DOWN, LEFT, RIGHT in that order. Each move has cost \( =1 \). Figure 1 below shows example initial and final states. Initial State: Final State: Figure 1: an example initial and final state b. [25 points] Write a code to implement the algorithm to solve the 8-puzzle problem. Input format: To input the instance of the problem, assume the cell numbers are as shown in figure 2 . Then the initial state in figure 1 can be input by the following sequence: 142 -153678, where the i-th cell of the puzzle contains the ith number in the sequence and \( -1 \) represents the blank tile. The final state of the example above can be input as: 12 - 15 \( 43678 . \) Figure2: Cell numbering