Description

On a $3\times 3$ board, there are eight tiles, each labeled with a digit from $1$ to $8$. One cell is left empty and is denoted by $0$. A tile adjacent to the blank can be moved into the blank. The task is: given an initial layout (initial state) and a target layout (to simplify the problem, the target state is set to $123804765$), find a sequence of moves with the minimum number of steps to transform the initial state into the target state.

Input Format

Input the initial state: nine numbers in one line, with the blank denoted by $0$.

Output Format

Output a single line containing one integer, the minimum number of moves required to reach the target state from the initial state. It is guaranteed that in the testdata there are no unsolvable initial states.

283104765

4

Hint

Sample Explanation

In the figure, the cell labeled $0$ is the blank. The green cell is the position of the blank, and the orange cells are the positions that can be moved into the blank in the next step. As shown, the target state can be reached in four moves.

Moreover, it can be proven that no better strategy exists.

Translated by ChatGPT 5