8 パズルは１つの空白を含む $3 \times 3$ のマス上に 8 枚のパネルが配置され、空白を使ってパネルを上下左右にスライドさせ、絵柄を揃えるパズルです。
この問題では、次のように空白を 0、各パネルを 1 から 8 の番号でパズルを表します。
1 3 0 4 2 5 7 8 6
1 回の操作で空白の方向に１つのパネルを移動することができ、ゴールは次のようなパネルの配置とします。
1 2 3 4 5 6 7 8 0
８パズルの初期状態が与えられるので、ゴールまでの最短手数を求めるプログラムを作成してください。
入力はパネルの数字あるいは空白を表す $3 \times 3$ 個の整数です。空白で区切られた 3 つの整数が 3 行で与えられます。
最短手数を１行に出力してください。
1 3 0 4 2 5 7 8 6
4