3*3の領域に、上下の面が白、左右の面が青、前後の面が赤の立方体を置く。
ここから、指定した一つの立方体を取り除き、空間を作る。
この空間に、隣接する立方体を転がして移動させる事によって、立方体の並びを変更していく。
上から見た色の並びを指定された物にする為には、最低何回の移動が必要か?
30回以内に到達する事が不可能なら、 -1と出力せよ。

枝刈り付き深さ優先探索で解くのが良い。
テンキーで言うの1379の位置を隅、2468の位置を辺、5を中心と呼び事にする。
t 回目の移動で隅から辺に移動するような、t回目までの動きのパターン数をn12(t)、
辺から隅のものを、n21(t)、辺から中央のものを、n25(t)、中央から辺のものをn52(t)とする。
元来た方向に引き返さないという枝狩りを入れると、
n12(t+1) = n21(t)
n21(t+1) = 2*n52(t) + n12(t)
n25(t+1) = n12(t)
n52(t+1) = 3*n25(t)
という式が成り立つ。
一番初めに5の位置にいるとしてこの式を解くと、t=30における n12(t)+n21(t)+n25(t)+n52(t) はおよそ4500万となり、t=1から30までの総和は、およそ1億となる。
あとは、上の面の揃っていない面の数-1は最低必要な手数となるので、既知の解と同じか、それより多くの手数が必要となる時などに枝狩りを入れると、高速に動作する。

3131.cpp