P2578 [ZJOI2005] Nine-Digit Puzzle Game


The input consists of nine integers arranged in three rows and three columns. In each row, adjacent integers are separated by a space, representing the number on each square in the initial state. The initial state will not be the goal state.

If the goal state is unreachable, output UNSOLVABLE (without quotes). Otherwise, the first line contains an integer $S$, the minimal number of moves. Then output $4 \times (S + 1)$ lines. Every four lines represent one state: the first three lines each contain three integers separated by a space, representing the numbers on the squares; the fourth line is a blank line used as a separator. The first state must be the initial state, and the last state must be the goal state.

SPJ provided by @FlierKing. Translated by ChatGPT 5