22156_NineDigits

Nine tiles, each with a number from 1 to 9 on it, are packed into a 3 by 3 frame. Your task is to arrange the tiles so that they are ordered as:

1 2 3
4 5 6
7 8 9

At each step, you can do the following operation to the tiles: Choose 2 by 2 tiles, rotate the tiles in clockwise order. For example:

1 2 3    4 1 3       1 2 3    1 2 3
4 5 6 => 5 2 6   or  4 5 6 => 4 8 5
7 8 9    7 8 9       7 8 9    7 9 6

Write a program to find the minimum number of steps.

Input contains multiple test cases.

Each test case is a description of a configuration of the nine tiles. The description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and from left to right within a row, where the tiles are represented by numbers 1 to 9. For example:

9 8 7
6 5 4
3 2 1

is described by this list:

9 8 7 6 5 4 3 2 1

Output the minimum number of steps on a single line for each test case.

1 2 3 4 5 6 7 8 9
4 1 3 5 2 6 7 8 9

0
3