Let's play a puzzle using eight cubes placed
on a <!-- MATH
$3 \times 3$
-->
3 x 3 board leaving one empty square.

Faces of cubes are painted with three colors. As a puzzle step, you
can roll one of the cubes to the adjacent empty square. Your goal is
to make the specified color pattern visible from above by a number of
such steps.

The rules of this puzzle are as follows.

1. Coloring of Cubes:
   All the cubes are colored in the same way
   as shown in Figure 3.
   The opposite faces have the same color.
   
   Figure 3: Coloring of a cube

2. Initial Board State: Eight cubes are placed on the 3 x 3 board leaving one empty square. All the cubes have the same orientation as shown in Figure 4. As shown in the figure, squares on the board are given x and y coordinates, (1, 1), (1, 2), ..., and (3, 3). The position of the initially empty square may vary.
   
   Figure 4: Initial board state

3. Rolling Cubes: At each step, we can choose one of the cubes adjacent to the empty square and roll it into the empty square, leaving the original position empty. Figure 5 shows an example.
   
   Figure 5: Rolling a cube

4. Goal: The goal of this puzzle is to arrange the cubes so that their top faces form the specified color pattern by a number of cube rolling steps described above.

Your task is to write a program that finds the minimum number of steps required to make the specified color pattern from the given initial state.