倉庫番をゴールから逆向きに解く — pull-BFS によるデッドマス証明と押し手最適 BFS ソルバー

倉庫番 を、本物のアルゴリズム 2 本立てでブラウザに実装した。(1) デッドマスの静的証明 — 「箱がゴールに届く ⇔ ゴールから箱を引いてその位置に戻せる」という逆向きの発想で、探索開始前に pull-BFS 一発で証明付きの詰みマスを全列挙する（デモでオーバーレイ表示可能）、(2) 押し手最適 BFS — 状態を「箱の集合＋プレイヤーの到達領域」に正規化し、遷移を「1 プッシュ」にすることで、最初に見つかる解が押し手数最小になる。バンドルした 6 面は全てソルバーで可解性検証済み（テストが実際に 1 面の設計ミスを検出した）。数独(#33)→ライツアウト(#284)→15パズル(#285) に続くソルバー内蔵パズル第 4 弾。

🌐 ライブデモ: https://sen.ltd/portfolio/sokoban/
📦 GitHub: https://github.com/sen-ltd/sokoban

デッドマス: 逆向きに考える

前向きに「この箱はどこへ行ける?」と考えると高くつく。コツは逆向きだ: 箱がゴールに届く ⇔ ゴールの位置から箱を引っ張ってその位置まで戻せる。そして引きにはデッドロックがない。だから全ゴールを始点に、合法な「引き」で拡げる BFS を 1 回走らせれば、生きているマスが全部マークされる:

// from → to へ引くには、to のさらに先にプレイヤーが立てる必要がある
const to = from + d;
const playerSq = to + d;
if (walls[to] || walls[playerSq]) continue;   // 通れば to は pull 到達可能

マークされなかったマスがデッドマス: そこへ箱を押し込んだ瞬間、そのレベルは証明付きで詰み——探索不要。ゴールのない角はもちろん、ゴールのない壁際の辺全体も自動的に出てくる（テストで明示的に pin）。ソルバーはデッドマスへのプッシュを枝刈りし、デモではチェックボックスで赤く可視化できる。

ソルバー: (領域, 箱集合) 上の押し手最適 BFS

プッシュとプッシュの間、プレイヤーはただ歩くだけ——だから正確な位置は状態に要らず、どの領域に居るかだけが要る。探索状態は「箱の集合＋プレイヤー到達領域（最小セルで正規化）」:

const k = canon + ':' + boxes.join(',');   // 状態キー: 領域 + 箱集合

遷移は箱 1 プッシュ（箱の後ろにプレイヤーが回り込めること）。これで BFS の深さ＝プッシュ数になり、最初に見つかる解が押し手最適。ステータス行にプッシュ数・探索状態数・時間を出している（スクショでは 6 プッシュ最適解を 648 状態・11ms）。

もう 1 つの見せ場は、solve を現在局面から走らせていること。箱を角に押し込んでから Solve を押すと「provably unsolvable from here — try Undo」と返る。探索空間を使い切った上での結論なので、タイムアウトではなく証明だ。

アニメ再生は、各プッシュを「箱の後ろまでの歩行経路（BFS）＋押す 1 歩」に展開し（expandSolution）、テストがその全ステップを移動ルールに通して合法かつ勝利に到達することを確認する。

レベルはソルバーで検証してから出荷する

同梱 6 面は自作で、テストスイートは全レベルをソルバーが解けること＋解のリプレイが勝利に達することを要求する。制作中、右壁に接した箱が構造上二度と左に押せない——つまり本当に不可能なレベルを 1 面書いてしまい、このテストが即座に検出して再設計になった。「レベルは自分のソルバーを通してから出せ」を身をもって実践した形だ。

src/sokoban.ts      — 純粋エンジン: パーサ, 移動, pull-BFS デッドマス, 押し手最適 BFS, 歩行経路, 解展開
src/sokoban.test.ts — 17 ケース（ルール・デッドマス・ソルバー証明・リプレイ）
src/levels.ts       — 自作 6 面（全てソルバー検証済み）
src/main.ts         — DOM 殻: グリッド・入力・Undo・解アニメ・デッドマス表示

まとめ

倉庫番の面白さは「前向きの探索」と「逆向きの証明」が組み合わさるところにある。pull-BFS のデッドマス解析は探索前に不可能を確定させ、(領域, 箱集合) の BFS は押し手最適解を返す。ソルバー内蔵パズルはこれで 4 本目——数独・ライツアウト（GF(2)）・15パズル（パリティ+IDA*）・倉庫番（pull-BFS+押し手最適 BFS）。それぞれ数学の顔が違うのがこのシリーズの狙いだ。

🌐 ライブデモ: https://sen.ltd/portfolio/sokoban/
📦 GitHub: https://github.com/sen-ltd/sokoban