Sliding Puzzle

Interview

Time limit1sMemory limit32 MB

Summary

Find the minimum number of moves to solve a 3x3 sliding puzzle into a fixed goal state, or report -1 if unsolvable.

Level: Medium4 of 10
Topics: BFS, Implementation, Brute force
Solved: No attempts yet

Problem

A 3x3 board contains the numbers from 0 to 8, one number in each cell. The number 0 represents the empty cell. The goal state is:


1	2	3
4	5	6
7	8	0

In one move, you may swap the empty cell with one number directly above, below, left, or right of it. A move cannot go outside the board.

Given an initial board, find the minimum number of moves needed to reach the goal state.

Input

The current board is given over three lines. Each line contains three integers separated by spaces. The empty cell is written as 0, and each number from 0 to 8 appears exactly once.

Output

Print the minimum number of moves needed to reach the goal state. If the goal state cannot be reached, print -1.

Examples2

Example 1
Input
```
1 0 3
4 2 5
7 8 6
```
Expected output
```
3
```
Example 2
Input
```
3 6 0
8 1 2
7 4 5
```
Expected output
```
-1
```