考察
初期盤面から20手先まで調べる代わりに、初期盤面と完成盤面から10手ずつ進み、同じ盤面に出会えるかを調べる。180度回転は同じ操作でもとに戻せるため、完成盤面からの探索結果を「あと何手で完成できるか」として使える。
まず、盤面全体を一つの状態、1回の回転を長さ1の辺と考える。求めるのは初期盤面から完成盤面までの最短距離であり、20手を超える場合は −1 を返す。1手の選択肢は、左上・右上・左下・右下に寄せた 長方形の4種類だけである。
それでも、長さ20の操作列をそのまま列挙すると 通りになる。同じ長方形を続けて2回回す無駄を除いても、長さ20の列だけで 通りあり、片側からの全列挙は難しい。ここで「20手以内」という上限を二つに分けられないか考える。
どの回転も2回行うともとに戻る。したがって、完成盤面からある盤面まで進めたなら、その操作列を逆順にたどって完成盤面へ戻れる。初期側と完成側でそれぞれ10手以内に到達できる盤面が見つかれば、そこを経由して20手以内で完成できる。
盤面を表し、四つの隣接盤面を作る
以下では行・列の添字を0始まりにする。盤面 は上の行から順に値を並べた長さ の配列で表し、マス の値を配列の位置 に置く。初期盤面を 、値が の順に並ぶ完成盤面を と呼ぶ。辞書のキーには、この配列全体を使えばよい。
一つの回転は、長方形の左上の位置 を から選ぶことで決まる。回転後の盤面 は、まず をコピーし、長方形の中だけ次のように書き換える。
ここで 、 である。長方形の外側の値は変えず、右辺はすべて回転前の盤面から読む。四つの についてこれを行えば、隣接する4盤面を生成できる。
例えば完成した 盤面の左上の を回すと、次のようになる。
1 2 3 5 4 3
4 5 6 → 2 1 6
7 8 9 7 8 9
同じ長方形をもう一度回すと左の盤面へ戻る。右の盤面を入力とすれば、完成までの最短手数は1である。
深さ10までの最短距離を保存して照合する
両側で距離付きの幅優先探索(BFS)を行う。辞書 distStart は初期盤面からの最短手数、distGoal は完成盤面からの最短手数を、盤面をキーとして保存する。具体的には次の手順になる。
distStart に の距離0を登録し、キューへ入れる。
- キューから盤面を取り出す。距離が10なら保存したまま展開を止める。10未満なら4種類の回転で隣接盤面を作り、未登録の盤面だけ距離を1増やして辞書とキューへ追加する。
- キューが空になるまで繰り返す。同じ手順を からも行い、
distGoal を作る。
distStart の各盤面について distGoal にも登録されているかを調べる。共通盤面ごとに二つの距離を足し、その最小値を出力する。共通盤面が一つもなければ −1 を出力する。
各操作の長さは1なので、BFSで最初に登録した距離がその側からの最短距離になる。同じ盤面への別の操作列は以後の選択肢を増やさないため、再登録は不要である。ここで必要なのは操作列の組の総当たりではなく、二つの辞書に共通する盤面の検索である。
典型の発動条件
meet-in-the-middle探索
1手の分岐数が小さくても、操作数の上限まで片側から列挙すると指数的に増える。このとき、操作列を前半・後半に分け、それぞれの結果を中間状態で照合できないか考える。最短手数を求める場合は、到達の有無だけでなく、各状態への最短距離を残す。
involutionの逆向き探索
同じ操作を2回行うともとに戻る操作を自己逆操作(involution)という。自己逆操作なら、完成状態からも同じ遷移生成手順を使える。一般の有向遷移へ応用するときは、完成側からは逆向きの遷移を列挙できることを確認する。
問題固有の要素
盤面は最大64マスあり、配置全体の数は大きい。一方、長方形の大きさが に固定されているため、その左上は4か所しかなく、探索の分岐数は4に収まる。盤面の大きさだけで全探索を諦めず、1手の選択肢と必要な深さを別々に数えることが着想の入口になる。
正当性
各回転は長さ1の辺なので、両側のBFSは、それぞれの出発盤面から10手以内の全盤面と、その最短距離を記録する。
共通盤面を とし、初期側・完成側の保存距離をそれぞれ とする。完成側の操作列を逆順にたどれば、自己逆性により から完成盤面へ進める。したがって距離和 は実現可能な手数であり、20以下である。
逆に、最短手数を とする。その最短操作列の先頭から 手進んだ盤面を に選ぶと、前半も残りも10手以内である。後半は逆向きにもたどれるので、 は両方の辞書に必ず含まれる。保存距離はこの前半・後半の長さ以下だから、その和は 以下になる。一方、共通盤面の距離和は実現可能な手数なので 未満にはならない。よって、共通盤面における距離和の最小値が最短手数と一致する。
共通盤面がない場合は、20手以下の操作列が存在すればその途中に共通盤面があるはず、という議論に反する。従って −1 が正しい。初期盤面が完成盤面なら両側の距離0で照合でき、答えは0となる。
実装上の注意
- 盤面のキーは、値をそのまま保持する長さ の配列や、各値を1文字に対応させた固定長文字列でよい。数値を区切りなしの十進表記で連結せず、各マスの値と順序を一意に復元できる表現にする。ハッシュ表でも、キーの一致は盤面全体で判定する。
- 6 bitずつ詰める場合は、入力値 を必ず に変換する。8行8列の入力には64が含まれ、これをそのまま6 bitには収められない。一盤面には bit、最大384 bitが必要なので、複数の整数へ分けるなどして保持する。
- 隣接盤面は毎回もとの盤面から作る。直接書き換えてから別の回転を試す実装では、探索後に同じ回転でもとへ戻す。辞書へ登録したキー自体を後から変更しない。
- 訪問済みの登録はキューへ入れる時に行う。距離10の盤面も照合に必要なので保存し、そこから先だけを生成しない。距離0も含めて、両側で同じキー表現を使う。
復習の核
- 操作数が小さく、完成状態からも逆向きに進めるなら、操作列を両端から半分ずつ列挙できないか考える。
- 中間状態で照合するために何を残すべきかを目的から決める。最短化では、同じ状態への複数の経路を最短距離にまとめられる。
- 「1マスを何 bitで表せるか」と「盤面全体に何 bit必要か」を分けて数える。値の範囲の両端も確認する。
計算量と制約
時間
片側で保存する盤面数の上界を と置く。最短操作列では同じ回転を続けて2回行わないため、深さ の盤面数は高々 である。従って、深さ0から10の総数は次で抑えられる。
各盤面から高々4遷移を試し、盤面のコピー・回転・キーのハッシュ計算には かかる。ハッシュ表の検索・挿入が平均定数回のキー処理で済むとすれば、二つのBFSと最後の照合を合わせて期待 時間となる。配列をキーとする平衡二分探索木の辞書を使う場合は、比較1回に最悪 かかるため、全体で 時間となる。
空間
二つの距離辞書と探索用キューに高々 盤面を保存し、各盤面は の領域を使う。入力・隣接盤面を作る作業領域も含めて 空間である。
制約との対応
、各値は から までの相異なる整数であり、盤面は最大64マスとなる。探索する盤面は片側で高々118097個で、20手を片側だけで列挙する場合から大きく減る。深さ10で展開を止めても、ちょうど20手で完成する操作列の中間盤面は保存される。20手以内に完成できない場合は、さらに手数をかければ到達できる場合も含めて −1 とする。
出典