倉庫番ソルバーアルゴリズム:探索で解を見つける方法
倉庫番ソルバーは箱を押すパズルを盤面状態の探索に変換します。箱の位置、歩ける床、可能な押し、既知の状態を記録します。
このガイドはソルバーの仕組みを説明します。ASCII盤面を入力して経路を得たい場合はオンラインソルバーを使ってください。
ソルバーは画像だけでなく状態グラフとして盤面を評価します。
倉庫番ソルバーが実際に探索するもの
倉庫番で重要な単位は、通常、矢印キーの一歩ではなく箱を押す操作です。押す合間の歩行はプレイヤーの位置を変えますが、箱は動かしません。そのため盤面をグラフとして扱えます。節点は既知の状態、辺は合法な一押しと、次の箱の後ろに立つために必要な歩行です。
押す操作は元に戻せるとは限らないため、グラフは大きくなります。箱を動かすには反対側に立つ必要があり、悪い隅に入った箱を引き戻すことはできません。探索では各節点で、どの箱がどの床を占めているか、箱を動かさずにどの床へ歩けるかを判断できる情報を保持します。
すべてのゴールが埋まると、親状態へのリンクを開始位置までたどり、手順を復元します。方向の列には多数の歩行が含まれていても、重要な判断は状態を変えた押しです。
盤面状態の表現方法
盤面には固定データと変化するデータがあります。壁とゴールは動かないので一度だけ解析できます。変化するのは箱の座標集合とプレイヤーの到達可能領域です。箱を越えずに行き来できる二つのプレイヤー位置は、多くの場合同じ状況を表します。これを正規化すると、探索待ちの列が同等の歩行位置で埋まるのを防げます。
| 状態の要素 | 記録する内容 | 役割 |
|---|---|---|
| 壁とゴール | 固定された盤面の形 | 移動可能な床とクリア条件を定義します。 |
| 箱の配置 | 各箱の座標 | 可能な押しとゴールへの割り当てを決めます。 |
| プレイヤーの領域 | 箱を押さずに到達できる床 | 箱のどちら側に立てるかを示します。 |
| 親状態と操作 | 直前の状態と押した方向 | 可否だけでなく、見つかった手順を再現できます。 |
置換表、または訪問済み集合には、正規化した状態ごとのキーを保存します。同じ箱配置と到達可能領域が再び現れても、再探索で新しい続きは見つかりません。これはメモリーを使って速度を得る仕組みです。
説明用の盤面図:箱を動かす順序によって、その後に到達できる状態が変わります。ソルバーのコード画面ではなく、考え方を示す図です。
探索フロンティアの広がり方
状態を解析したら、塗りつぶし探索で歩ける範囲を求めます。各箱について上下左右を調べ、移動先が空いた床で、反対側の立ち位置へプレイヤーが到達できる場合だけ、押しを許可します。その後、箱を移動して到達可能領域を計算し直した新しい状態を作ります。
探索順序によって保証も変わります。幅優先探索は押し数の少ない列から調べるため、各辺のコストが等しければ最少押し数の解を見つけられます。深さ優先探索は一つの分岐を深くたどり、待機状態のメモリーを節約しますが、無益な分岐に時間を費やす場合があります。一様コスト探索やA*探索では押しのコストとヒューリスティックを組み合わせられますが、その推定の品質と性質が結果の保証を左右します。
- 解析。壁、ゴール、箱、プレイヤーを読み取り、個数の不整合や未対応の記号を拒否します。
- 到達範囲。箱を動かさずに歩ける床をすべて記録します。
- 展開。立ち位置と移動先が有効な押しを生成します。
- 枝刈りと記録。重複や明らかな行き詰まりを除き、新しい状態の親と押しを保存します。
- 終了。全ゴールが埋まったら停止し、上限内で解が見つからなければその旨を伝えます。
すべての歩行経路を別々に保存する必要はありません。押した後の正規化された到達可能領域が一つあれば、次の押しを生成できます。この圧縮によって、小さなブラウザーソルバーでも実用的に動作します。
デッドロックの枝刈りが重要な理由
枝刈りがないと、解に到達できない配置の探索に時間を浪費します。最も簡単な規則はゴールでない隅です。直角に交わる二つの壁に接した箱は出られないため、その分岐をすぐ除外できます。対応するゴールのない壁際、動かない2×2の箱群、幅一マスの通路を塞ぐ箱も、よく確認するパターンです。
箱が固定されなくても、必要な場所へ行けなくなる場合があります。正しいゴールに置いた箱が、別の箱を押すための唯一の立ち位置を塞ぐこともあります。二つの箱は動いても、それらを分ける側へプレイヤーが回れないこともあります。検出が難しいため、実用的なソルバーは単純な規則、重複状態の確認、有限の探索予算を組み合わせます。
隅のデッドロックは深く探索する前に判定できるため役立ちます。より複雑な到達不能の問題には、広い範囲の状態確認が必要です。
枝刈りには正しさの検討が必要です。強すぎる規則は、例外的に成功する手順まで削除しかねません。小さなブラウザーツールは、すべての「解なし」を証明と呼ばず、適用する枝刈りの範囲を説明するべきです。
押し数、歩数、ヒューリスティック
「最短の解」と言う前に、何を最小にするかを定義する必要があります。押し数最適は箱を押す回数を減らし、総手数最適は歩行も含めます。部屋を遠回りして歩けば押しを一回節約し、安全な箱配置を維持できるなど、目的は競合します。ソルバーは優先するコストを決め、結果にもその基準を示す必要があります。
ヒューリスティックは完成までの距離を推定します。単純な方法では格子上の距離で箱とゴールを対応付け、壁際の箱に追加コストを与えます。ただし壁、立ち位置、箱の順序があるため、実際の手順は単純な距離より複雑です。推定は有望な状態を優先する手掛かりであり、正確な距離を証明するものではありません。
小さな盤面では、操作列、押し数、歩数、確認した状態数を示すと役立ちます。読者は未証明の最適解と思い込まず、自分の計画と比較できます。
小さな盤面を追ってみる
箱が一つの例です。#は壁、.はゴール、$は箱、@はプレイヤーを表します。
##### # . # # $ # # @ # #####
最初の到達可能領域にはプレイヤーのマスと箱の下側の床があります。プレイヤーは箱の下に立ち、上のゴールへ押せるため、合法な押しが一つ見つかります。箱の新しい座標を記録し、到達可能領域を計算し直すと、全ゴールが埋まったと分かります。親状態へのリンクをたどれば、必要な歩行と一押しからなる短い手順を復元できます。
難しい盤面では、探索フロンティアに複数の押し候補が残ります。隅に入る分岐は枝刈りで消え、動かせる分岐は列に残ります。これが、無作為な試行と、確認済みの情報を記憶する探索との違いです。
ソルバーが停止する場合
ブラウザーソルバーが停止する理由は複数あります。箱とゴールの数が違う、未対応の記号がある、プレイヤーがいないといった無効な入力が考えられます。有効な盤面でも、安全のための行数、列数、箱数、訪問済み状態数の上限を超える場合があります。また、制限付き探索で候補を調べ尽くしても解が見つからない場合があります。
数学的に「解けない」と強く言えるのは、完全かつ無制限の探索で最後のケースに至った場合です。小さなオンラインツールは通常、画面の応答を保つため処理量を制限します。上限の表示が出たら、盤面を切り出す、デッドロックを点検する、逆算で考えるなどしてください。関連する倉庫番ソルバーは、小さな盤面向けの制限を明記し、無限に実行する代わりに理由を表示します。
ステージ制作者はソルバーで解の手順を確認し、その後に人間の試遊で狙いが伝わるか確認できます。倉庫番ステージ設計ガイドはその流れを説明し、この記事は基盤となる探索を説明しています。
倉庫番ソルバーアルゴリズム FAQ
倉庫番ソルバーのアルゴリズムとは何ですか?
箱とプレイヤーの状態を表現し、合法な押しを生成し、既知の行き詰まりを除外して、すべてのゴールを埋められたときに手順を復元する探索方法です。
矢印キーの操作を一手ずつ探索するのですか?
通常は歩行をプレイヤーの到達可能領域にまとめ、押しを重要な辺として展開します。これにより、同じ結果になる多数の歩行経路を探索から除けます。
デッドロックの枝刈りで速くなるのはなぜですか?
ゴールではない隅、動けない箱の集まり、塞がれた通路などの分岐を、その先の状態を調べる前に除外できるためです。
最初に見つかった解は最短ですか?
探索順序とコストモデルがそれを保証する場合に限ります。制限付きのブラウザーソルバーは、押し数や総手数の最適性を証明せずに、実行可能な解を返すことがあります。
探索上限に達したとはどういう意味ですか?
解の存在や不可能性を証明する前に、安全のための処理上限で停止したという意味です。盤面を小さくするか状態を手動で確認してください。解なしの証明とは扱わないでください。
参考資料と関連文献
状態と到達可能領域の考え方は倉庫番Wikiのソルバー資料を参照しています。探索順序の例は倉庫番の基本探索アルゴリズム解説に基づきます。状態空間の拡大と距離推定の制約は、Pavel Klavikによる倉庫番ソルバーの文書で論じられています。これらは標準的な倉庫番の資料であり、このサイトのツール固有の上限はリンク先のZeekソルバーに基づきます。