ABC 336 F — Rotation Puzzle

考察

初期盤面から20手先まで調べる代わりに、初期盤面と完成盤面から10手ずつ進み、同じ盤面に出会えるかを調べる。180度回転は同じ操作でもとに戻せるため、完成盤面からの探索結果を「あと何手で完成できるか」として使える。

まず、盤面全体を一つの状態、1回の回転を長さ1の辺と考える。求めるのは初期盤面から完成盤面までの最短距離であり、20手を超える場合は −1 を返す。1手の選択肢は、左上・右上・左下・右下に寄せた (H−1)×(W−1)(H-1)\times(W-1) 長方形の4種類だけである。

それでも、長さ20の操作列をそのまま列挙すると 4204^{20} 通りになる。同じ長方形を続けて2回回す無駄を除いても、長さ20の列だけで 4⋅3194\cdot3^{19} 通りあり、片側からの全列挙は難しい。ここで「20手以内」という上限を二つに分けられないか考える。

どの回転も2回行うともとに戻る。したがって、完成盤面からある盤面まで進めたなら、その操作列を逆順にたどって完成盤面へ戻れる。初期側と完成側でそれぞれ10手以内に到達できる盤面が見つかれば、そこを経由して20手以内で完成できる。

盤面を表し、四つの隣接盤面を作る

以下では行・列の添字を0始まりにする。盤面 CC は上の行から順に値を並べた長さ HWHW の配列で表し、マス (r,c)(r,c) の値を配列の位置 rW+crW+c に置く。初期盤面を SS、値が 1,2,…,HW1,2,\ldots,HW の順に並ぶ完成盤面を GG と呼ぶ。辞書のキーには、この配列全体を使えばよい。

一つの回転は、長方形の左上の位置 (x,y)(x,y) を x,y∈{0,1}x,y\in\{0,1\} から選ぶことで決まる。回転後の盤面 C′C' は、まず CC をコピーし、長方形の中だけ次のように書き換える。

Cx+a, y+b′=Cx+H−2−a, y+W−2−bC'_{x+a,\,y+b}=C_{x+H-2-a,\,y+W-2-b}

ここで 0≤a<H−10\leq a<H-1、0≤b<W−10\leq b<W-1 である。長方形の外側の値は変えず、右辺はすべて回転前の盤面から読む。四つの (x,y)(x,y) についてこれを行えば、隣接する4盤面を生成できる。

例えば完成した 3×33\times3 盤面の左上の 2×22\times2 を回すと、次のようになる。

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

同じ長方形をもう一度回すと左の盤面へ戻る。右の盤面を入力とすれば、完成までの最短手数は1である。

深さ10までの最短距離を保存して照合する

両側で距離付きの幅優先探索(BFS)を行う。辞書 distStart は初期盤面からの最短手数、distGoal は完成盤面からの最短手数を、盤面をキーとして保存する。具体的には次の手順になる。

  1. distStart に SS の距離0を登録し、キューへ入れる。
  2. キューから盤面を取り出す。距離が10なら保存したまま展開を止める。10未満なら4種類の回転で隣接盤面を作り、未登録の盤面だけ距離を1増やして辞書とキューへ追加する。
  3. キューが空になるまで繰り返す。同じ手順を GG からも行い、distGoal を作る。
  4. distStart の各盤面について distGoal にも登録されているかを調べる。共通盤面ごとに二つの距離を足し、その最小値を出力する。共通盤面が一つもなければ −1 を出力する。

各操作の長さは1なので、BFSで最初に登録した距離がその側からの最短距離になる。同じ盤面への別の操作列は以後の選択肢を増やさないため、再登録は不要である。ここで必要なのは操作列の組の総当たりではなく、二つの辞書に共通する盤面の検索である。

典型の発動条件

meet-in-the-middle探索

1手の分岐数が小さくても、操作数の上限まで片側から列挙すると指数的に増える。このとき、操作列を前半・後半に分け、それぞれの結果を中間状態で照合できないか考える。最短手数を求める場合は、到達の有無だけでなく、各状態への最短距離を残す。

involutionの逆向き探索

同じ操作を2回行うともとに戻る操作を自己逆操作(involution)という。自己逆操作なら、完成状態からも同じ遷移生成手順を使える。一般の有向遷移へ応用するときは、完成側からは逆向きの遷移を列挙できることを確認する。

問題固有の要素

盤面は最大64マスあり、配置全体の数は大きい。一方、長方形の大きさが (H−1)×(W−1)(H-1)\times(W-1) に固定されているため、その左上は4か所しかなく、探索の分岐数は4に収まる。盤面の大きさだけで全探索を諦めず、1手の選択肢と必要な深さを別々に数えることが着想の入口になる。

正当性

各回転は長さ1の辺なので、両側のBFSは、それぞれの出発盤面から10手以内の全盤面と、その最短距離を記録する。

共通盤面を PP とし、初期側・完成側の保存距離をそれぞれ dS(P),dG(P)d_S(P),d_G(P) とする。完成側の操作列を逆順にたどれば、自己逆性により PP から完成盤面へ進める。したがって距離和 dS(P)+dG(P)d_S(P)+d_G(P) は実現可能な手数であり、20以下である。

逆に、最短手数を D≤20D\leq20 とする。その最短操作列の先頭から min⁡(D,10)\min(D,10) 手進んだ盤面を PP に選ぶと、前半も残りも10手以内である。後半は逆向きにもたどれるので、PP は両方の辞書に必ず含まれる。保存距離はこの前半・後半の長さ以下だから、その和は DD 以下になる。一方、共通盤面の距離和は実現可能な手数なので DD 未満にはならない。よって、共通盤面における距離和の最小値が最短手数と一致する。

共通盤面がない場合は、20手以下の操作列が存在すればその途中に共通盤面があるはず、という議論に反する。従って −1 が正しい。初期盤面が完成盤面なら両側の距離0で照合でき、答えは0となる。

実装上の注意

  • 盤面のキーは、値をそのまま保持する長さ HWHW の配列や、各値を1文字に対応させた固定長文字列でよい。数値を区切りなしの十進表記で連結せず、各マスの値と順序を一意に復元できる表現にする。ハッシュ表でも、キーの一致は盤面全体で判定する。
  • 6 bitずつ詰める場合は、入力値 v∈{1,…,HW}v\in\{1,\ldots,HW\} を必ず v−1∈{0,…,63}v-1\in\{0,\ldots,63\} に変換する。8行8列の入力には64が含まれ、これをそのまま6 bitには収められない。一盤面には 6HW6HW bit、最大384 bitが必要なので、複数の整数へ分けるなどして保持する。
  • 隣接盤面は毎回もとの盤面から作る。直接書き換えてから別の回転を試す実装では、探索後に同じ回転でもとへ戻す。辞書へ登録したキー自体を後から変更しない。
  • 訪問済みの登録はキューへ入れる時に行う。距離10の盤面も照合に必要なので保存し、そこから先だけを生成しない。距離0も含めて、両側で同じキー表現を使う。

復習の核

  • 操作数が小さく、完成状態からも逆向きに進めるなら、操作列を両端から半分ずつ列挙できないか考える。
  • 中間状態で照合するために何を残すべきかを目的から決める。最短化では、同じ状態への複数の経路を最短距離にまとめられる。
  • 「1マスを何 bitで表せるか」と「盤面全体に何 bit必要か」を分けて数える。値の範囲の両端も確認する。

計算量と制約

時間

片側で保存する盤面数の上界を BB と置く。最短操作列では同じ回転を続けて2回行わないため、深さ d≥1d\geq1 の盤面数は高々 4⋅3d−14\cdot3^{d-1} である。従って、深さ0から10の総数は次で抑えられる。

B=1+∑d=1104⋅3d−1=118097B=1+\sum_{d=1}^{10}4\cdot3^{d-1}=118097

各盤面から高々4遷移を試し、盤面のコピー・回転・キーのハッシュ計算には O(HW)O(HW) かかる。ハッシュ表の検索・挿入が平均定数回のキー処理で済むとすれば、二つのBFSと最後の照合を合わせて期待 O(HWB)=O(HW⋅310)O(HWB)=O(HW\cdot3^{10}) 時間となる。配列をキーとする平衡二分探索木の辞書を使う場合は、比較1回に最悪 O(HW)O(HW) かかるため、全体で O(HWBlog⁡B)O(HWB\log B) 時間となる。

空間

二つの距離辞書と探索用キューに高々 O(B)O(B) 盤面を保存し、各盤面は O(HW)O(HW) の領域を使う。入力・隣接盤面を作る作業領域も含めて O(HWB)O(HWB) 空間である。

制約との対応

3≤H,W≤83\leq H,W\leq8、各値は 11 から HWHW までの相異なる整数であり、盤面は最大64マスとなる。探索する盤面は片側で高々118097個で、20手を片側だけで列挙する場合から大きく減る。深さ10で展開を止めても、ちょうど20手で完成する操作列の中間盤面は保存される。20手以内に完成できない場合は、さらに手数をかければ到達できる場合も含めて −1 とする。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Rotation Puzzle の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: meet-in-the-middle・半分全列挙

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: meet-in-the-middle・半分全列挙

    補助タグ: 状態グラフのモデリングと探索

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: meet-in-the-middle・半分全列挙

    • 探索空間を独立に列挙できる二集合へ分け、両側の結果を照合・合成できる。

    先に読む単元:

    • 状態グラフのモデリングと探索 — 暗黙状態と重みなし合法遷移を頂点・辺へ写し、探索目的・訪問条件・frontierに応じてBFS・DFS・backtrackingを選ぶ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題