駐車場パズルの最短手数をBFSで出す — 出せる車は即出す枝刈りの正しさ

スライドパズル系のブラウザゲームを作ると、遊びの部分より先に片づけないといけないものが1つある。探索である。

出題した面が本当に解けるのか。解けるとして最短で何手なのか。プレイヤーが「もう無理」と言ったときに、それが本当に詰みなのか、まだ道があるのか。これらは全部、盤面の探索から出てくる答えだ。ここが弱いと、解けない面を出す、詰み表示が嘘をつく、ヒントが返ってこない、という形でゲームそのものが壊れる。

この記事では、hashito.biz で公開している駐車場パズル パークアウト の探索まわりを実装から読む。題材としては素直な幅優先探索（BFS）だが、実際に手を動かすと効いてくる工夫が2つある。「出せる車があるなら、その手だけを見る」という枝刈りと、状態キーの基数を面の大きさから決めることである。前者は探索する盤面の数を数百分の1にし、後者は放っておくと「探索が嘘をつく」バグになる。

記事の最後に、この2つを含む最小の探索器を1ファイル（依存なし）で置いてある。実際の面をそのまま解かせて、枝刈りのあり／なしを比べられる。

ルールと「1手」の定義

このゲームは、ラッシュアワー型の「自分の車を1台だけ出す」パズルではなく、盤上の動く車を全部出すルールになっている。

• 車は自分の軸に沿ってしか動かない（横向きの車は左右だけ、縦向きの車は上下だけ）。
• 車には前がある。出口から出られるのは前向きに進んだときだけで、バックは場所を空けるためにしか使えない。
• 出口は外周の一部にしかない。辺まで空いていても、その行／列に出口が無ければ出られない。
• 大文字を持たない車は動かせない（持ち主が不在の駐車車両）。これは占有だけを盤面に焼き込み、出す対象にも探索の状態にも入れない。

面はこういう文字列で書かれている。外周1文字が枠で、. が出口、# が壁である。

#...####
#fFhHj..
#..aaje.
#.GddJe.
.Ig.Kkk#
.icc...#
..bb...#
####...#

aA のように大文字のマスが鼻先（前）を表す。bb のように大文字が無い車は動かない。

ここで重要なのが1手の数え方で、このゲームは「1台を、1方向へ、好きなマス数だけ動かす」で1手である。3マス滑らせても1手。これは指で操作するゲームとしては当然の数え方だが、探索から見ると分岐が増える方向に効く。1台につき「前へ1〜n マス」「後ろへ1〜m マス」「出口から出る」が全部別の手になるからだ。

実装では、この1手を数値1個に詰めている。数十万個を配列に積むので、オブジェクトを作りたくないためだ。

var MV_BASE = 64, MV_ZERO = 32;
function mkMove(i, d){ return i * MV_BASE + (d + MV_ZERO); }
function mvCar(mv){ return (mv / MV_BASE) | 0; }
function mvStep(mv){ return (mv % MV_BASE) - MV_ZERO; }

d === 0 を「出口から出る」に割り当てているのがポイントで、0マス動かす手は存在しないので符号の空きをそのまま使える。

枝刈り: 出せる車があるなら、それを出す

素朴にやると、探索の各盤面で「全部の車 × 全部の距離 × 前後」を展開することになる。13台の面ならこれが数十通りになり、深さ19手まで潜ると持たない。

パークアウトの探索は、ここに1つだけ枝刈りを入れている。

function successors(L, st){
  var occ = occupancy(L, st), i, r;
  // 出せる車がいるなら、いちばん若い番号の車を出す1手だけ返す
  for (i = 0; i < L.cars.length; i++){
    if (st[i] < 0) continue;
    r = slide(L, st, occ, i, faceSign(L.cars[i]));
    if (r.exit) return [mkMove(i, 0)];
  }
  return legalMoves(L, st, occ);
}

いま出せる車が1台でもあれば、その車を出す1手だけを見る。ほかの手は一切展開しない。

これが最短手数を壊さないことは、交換論法で説明できる。いま車 X が出せる状態だとして、最短手順 S が X をすぐには出さなかったとする。X を先に出した盤面は、X が残っている盤面より占有が真に少ない。車が1台消えるだけで、新しい障害物は生まれない。したがって S に含まれる残りの手は、X を先に出したあとでもそのまま全部打てる。X はどのみち最後に1手を使って出るのだから、S から「X の途中の移動」と「X の出る手」を抜き、先頭に「X を出す手」を置いた手順は、S より長くならない。つまり出せるときに出す手順の中に、必ず最短が存在する。

同じ理屈から、このゲームでは詰みが起こらないことも言える。車を出すことで他の車が出られなくなることはなく、動かす手はすべて戻せるからだ。これはゲーム設計にも効いていて、「詰んだからリセット」が無い代わりに、面ごとに使える手数の上限（閉場までの手数）で締めている。上限は探索で分かった最短手数に余裕を足して決めているので、面ごとに公平になる。

効き目は実測すると分かりやすい。同じ面を、枝刈りありとなしで解いて、展開した盤面の数を数えたのが次である（この記事の最後のコードがそのまま出す）。

面	動く車	最短	展開（枝刈りあり）	展開（枝刈りなし）
easy-1	6台	8手	38	1,937
hard-6	13台	19手	540	219,576

13台の面で 406倍 の差がある。さらに大きい面（15台の 8×8）では、枝刈り無しの探索は300万盤面を超えても終わらず、手元では Node がヒープを使い切って落ちた。枝刈りありなら同じ面が 2,315 盤面・数ミリ秒で解ける。

この差はゲーム体験に直結している。ヒントは遊んでいる最中にその場で探索して出しているので、押して返ってこない探索は使えない。無限モードの面づくりでも、生成した面を実際に解いてみて探索が重すぎる面は捨てるという選び方をしている。

状態キーの基数を決め打ちにしない

もう1つは、地味だが壊れ方がたちの悪い話である。

BFSは「もう見た盤面か」を判定するために、状態をキーに変換する。パークアウトの状態は「動く車それぞれの位置」の並びで、位置は -1（出た）から 辺の長さ-1 までしか取らない。つまり 辺の長さ+1 通りである。ならば、この通り数を基数にして数値1個に詰められる。

function stateKey(L, st){
  var i, k;
  if (st.length <= L.keyMax){
    k = 0;
    for (i = 0; i < st.length; i++) k = k * L.keyBase + (st[i] + 1);
    return k;
  }
  var s = '';
  for (i = 0; i < st.length; i++) s += String.fromCharCode(st[i] + 1);
  return s;
}

文字列キーでも動くが、探索1回あたり数十万回のハッシュ計算になるので、数値キーのほうがはっきり速い。

問題は基数を何にするかだ。基数を 13 と決め打ちにすると、12×12 までは正しいが、それより大きい面を足した瞬間に別の盤面が同じキーに潰れる。潰れた盤面は「もう見た」として捨てられるので、探索は本当の最短より短い手数を返したり、解けない面を「解けた」と言ったりする。しかも見た目には何も起きないので気づきにくい。

実際に衝突を作ってみると、こうなる。

function keyOf(st, base){ var k = 0; for (var i = 0; i < st.length; i++) k = k * base + (st[i] + 1); return k; }
// 14マス幅の盤面では位置は -1..13 を取る（15通り）
console.log(keyOf([12, 0], 13), keyOf([11, 13], 13));   // 170 170  ← 別の盤面が同じキー
console.log(keyOf([12, 0], 15), keyOf([11, 13], 15));   // 196 194  ← 基数が足りていれば別

そこで実装は基数を面から決め、数値に詰められる台数の上限も計算で出している。

// 面の生成時
keyBase: Math.max(w, h) + 1,
keyMax: keyLimitOf(Math.max(w, h) + 1),

// base^n <= 2^53 を満たす最大の n
function keyLimitOf(base){
  return Math.floor((53 * Math.LN2) / Math.log(base) - 1e-9);
}

2^53 は倍精度浮動小数点が整数を正確に表せる範囲で、これを超えると加算の下位桁が落ちて、やはり別の盤面が同じ値になる。- 1e-9 は Math.log の丸め誤差で1つ多く見積もらないための保険である。台数がこの上限を超える面だけ、文字列キーに落ちる。

面の大きさが基数を決めるので、6×6 なら基数7で18台まで、8×8 なら基数9で16台まで数値キーで扱える。実際の面はこの範囲に収まっている。

なお、動かせない車を状態に入れない設計もここに効いている。動かない車は占有として盤面に焼き込むだけなので、状態の長さは「動く車の台数」で済む。状態が短ければ数値キーに収まる台数の上限にも余裕ができるし、探索空間そのものも小さくなる。

検証をどう担保しているか

このゲームの回帰テスト（test/park-out.test.js）は、固定18面と機械生成した無限モードの面を実際にBFSで解いて、画面に出している最短手数と突き合わせている。枝刈りについては、枝刈りありと素のBFSで同じ最短手数になることを比較して確かめている。基数の話も、大きい面でキーが衝突しないことをテスト項目に入れてある。

「解ける面しか出さない」はゲームの根幹であり、目視では絶対に守れない種類の性質なので、テストで押さえるしかない。手元で node --test test/park-out.test.js を回すと45件が通る（実行に10秒強かかるのは、全面を本当に解いているためである）。

実際に試す

前提は Node.js 18 以上（動作確認は v20.17.0）だけで、依存パッケージは無い。ブラウザで動かしたければ、この中身をそのまま <script> に貼れば同じように動く。

parkout-solver.js として保存する。

'use strict';
// 「全車を出す」駐車場パズルの最短手数を幅優先探索で求める最小実装。
// 面の記法: 外周1文字が枠（'.'=出口 / '#'=壁）、内側の英字が車（同じ文字が1台ぶん・
// 大文字のマスが鼻先＝前）。大文字を持たない車は動かせない（壁として焼き込む）。

var D_R = 0, D_D = 1, D_L = 2, D_U = 3;

// base^n <= 2^53 を満たす最大の n。これを超える台数は数値キーに詰められない。
function keyLimitOf(base) { return Math.floor((53 * Math.LN2) / Math.log(base) - 1e-9); }

function parseLevel(rows) {
  var h = rows.length - 2, w = rows[0].length - 2, x, y;
  var L = { w: w, h: h, wall: new Uint8Array(w * h), cars: [],
            gate: [new Uint8Array(h), new Uint8Array(w), new Uint8Array(h), new Uint8Array(w)] };
  for (y = 0; y < h; y++) {
    if (rows[y + 1].charAt(0) === '.') L.gate[D_L][y] = 1;
    if (rows[y + 1].charAt(w + 1) === '.') L.gate[D_R][y] = 1;
  }
  for (x = 0; x < w; x++) {
    if (rows[0].charAt(x + 1) === '.') L.gate[D_U][x] = 1;
    if (rows[h + 1].charAt(x + 1) === '.') L.gate[D_D][x] = 1;
  }
  var bag = {};
  for (y = 0; y < h; y++) for (x = 0; x < w; x++) {
    var ch = rows[y + 1].charAt(x + 1);
    if (ch === '#') { L.wall[y * w + x] = 1; continue; }
    if (ch === '.' || ch === ' ') continue;
    var key = ch.toLowerCase();
    if (!bag[key]) bag[key] = { cells: [], nose: null };
    bag[key].cells.push({ x: x, y: y });
    if (ch !== key) bag[key].nose = { x: x, y: y };   // 大文字＝鼻先
  }
  Object.keys(bag).sort().forEach(function (k) {
    var cs = bag[k].cells;
    var xs = cs.map(function (c) { return c.x; }), ys = cs.map(function (c) { return c.y; });
    var minX = Math.min.apply(null, xs), maxX = Math.max.apply(null, xs);
    var minY = Math.min.apply(null, ys), maxY = Math.max.apply(null, ys);
    var axis = (maxX - minX) >= (maxY - minY) ? 0 : 1;          // 0=横 1=縦
    var len = axis === 0 ? maxX - minX + 1 : maxY - minY + 1;
    var lane = axis === 0 ? minY : minX, pos = axis === 0 ? minX : minY;
    if (!bag[k].nose) {                                          // 動かせない車は壁にする
      for (var i = 0; i < len; i++) {
        var bx = axis === 0 ? pos + i : lane, by = axis === 0 ? lane : pos + i;
        L.wall[by * w + bx] = 1;
      }
      return;
    }
    var dir = axis === 0 ? (bag[k].nose.x === maxX ? D_R : D_L)
                         : (bag[k].nose.y === maxY ? D_D : D_U);
    L.cars.push({ axis: axis, len: len, lane: lane, pos: pos, dir: dir });
  });
  L.keyBase = Math.max(w, h) + 1;          // 位置は -1..(辺の長さ-1) の (辺+1) 通り
  L.keyMax = keyLimitOf(L.keyBase);
  return L;
}

function faceSign(c) { return (c.dir === D_R || c.dir === D_D) ? 1 : -1; }
function dirOf(c, sign) { return c.axis === 0 ? (sign > 0 ? D_R : D_L) : (sign > 0 ? D_D : D_U); }
function laneLimit(L, c) { return c.axis === 0 ? L.w : L.h; }
function initState(L) { return L.cars.map(function (c) { return c.pos; }); }
function isSolved(st) { return st.every(function (p) { return p < 0; }); }

function occupancy(L, st) {
  var occ = Uint8Array.from(L.wall);
  for (var i = 0; i < L.cars.length; i++) {
    if (st[i] < 0) continue;                       // 出た車は盤面から消える
    var c = L.cars[i];
    for (var k = 0; k < c.len; k++) {
      var x = c.axis === 0 ? st[i] + k : c.lane, y = c.axis === 0 ? c.lane : st[i] + k;
      occ[y * L.w + x] = 2 + i;
    }
  }
  return occ;
}

// sign 方向へ何マス進めるか、そしてそのまま盤外へ出られるか。
function slide(L, st, occ, i, sign) {
  var c = L.cars[i], lim = laneLimit(L, c);
  var p = (sign > 0 ? st[i] + c.len - 1 : st[i]) + sign, steps = 0;
  while (p >= 0 && p < lim) {
    var x = c.axis === 0 ? p : c.lane, y = c.axis === 0 ? c.lane : p;
    if (occ[y * L.w + x] !== 0) break;
    steps++; p += sign;
  }
  // 出られるのは「辺まで空き」「前向き」「その辺に出口」の3つがそろったときだけ
  var exit = (p < 0 || p >= lim) && sign === faceSign(c) && !!L.gate[dirOf(c, sign)][c.lane];
  return { steps: steps, exit: exit };
}

// 1手 = 1台を1方向へ好きなマス数。数値1つに詰める（0マス＝出口から出る）。
var MV_BASE = 64, MV_ZERO = 32;
function mkMove(i, d) { return i * MV_BASE + (d + MV_ZERO); }
function mvCar(mv) { return (mv / MV_BASE) | 0; }
function mvStep(mv) { return (mv % MV_BASE) - MV_ZERO; }

function legalMoves(L, st, occ) {
  var out = [];
  for (var i = 0; i < L.cars.length; i++) {
    if (st[i] < 0) continue;
    for (var s = 0; s < 2; s++) {
      var sign = s === 0 ? 1 : -1, r = slide(L, st, occ, i, sign);
      for (var d = 1; d <= r.steps; d++) out.push(mkMove(i, sign * d));
      if (r.exit) out.push(mkMove(i, 0));
    }
  }
  return out;
}

// 枝刈り: 出せる車が1台でもあるなら、その車を出す1手だけを見る。
function successors(L, st, prune) {
  var occ = occupancy(L, st);
  if (prune) {
    for (var i = 0; i < L.cars.length; i++) {
      if (st[i] < 0) continue;
      if (slide(L, st, occ, i, faceSign(L.cars[i])).exit) return [mkMove(i, 0)];
    }
  }
  return legalMoves(L, st, occ);
}

function applyMove(L, st, mv) {
  var ns = st.slice(0), i = mvCar(mv), d = mvStep(mv);
  if (d === 0) ns[i] = -1; else ns[i] += d;
  return ns;
}

function stateKey(L, st) {
  if (st.length <= L.keyMax) {
    var k = 0;
    for (var i = 0; i < st.length; i++) k = k * L.keyBase + (st[i] + 1);
    return k;
  }
  return st.join(',');
}

function solve(L, prune, cap) {
  var st0 = initState(L), start = stateKey(L, st0);
  if (isSolved(st0)) return { len: 0, seen: 1 };
  var prevKey = new Map(), prevMv = new Map();
  var queue = [st0], keys = [start], head = 0, seen = 1;
  prevKey.set(start, null);
  while (head < queue.length) {
    var st = queue[head], key = keys[head]; head++;
    var mvs = successors(L, st, prune);
    for (var k = 0; k < mvs.length; k++) {
      var ns = applyMove(L, st, mvs[k]), nk = stateKey(L, ns);
      if (prevKey.has(nk)) continue;
      prevKey.set(nk, key); prevMv.set(nk, mvs[k]); seen++;
      if (isSolved(ns)) {
        var path = [], cur = nk;
        while (cur !== start) { path.push(prevMv.get(cur)); cur = prevKey.get(cur); }
        return { len: path.length, seen: seen, moves: path.reverse() };
      }
      if (cap && seen > cap) return { over: true, seen: seen };
      queue.push(ns); keys.push(nk);
    }
  }
  return null;                                     // 解けない
}

// ── 実行 ────────────────────────────────────────────────
var EASY1 = ['#...####', '#fFhHj..', '#..aaje.', '#.GddJe.',
             '.Ig.Kkk#', '.icc...#', '..bb...#', '####...#'];
var HARD6 = ['#.......#', '.edIiiac.', '.ed.b.ac.', '.EDkbMa..', '.gGKlmp..',
             '.ooOlNpf.', '.hhHLnpf.', '.jjjJnPF.', '#.......#'];

[['easy-1', EASY1], ['hard-6', HARD6]].forEach(function (e) {
  var L = parseLevel(e[1]);
  var a = solve(L, true), b = solve(L, false, 3000000);
  console.log(e[0] + ': ' + L.w + 'x' + L.h + ' / 動く車 ' + L.cars.length + '台' +
    ' / キーの基数 ' + L.keyBase + '（数値キーの上限 ' + L.keyMax + '台）');
  console.log('  枝刈りあり: 最短 ' + a.len + '手 / 展開 ' + a.seen);
  console.log('  枝刈りなし: 最短 ' + b.len + '手 / 展開 ' + b.seen);
  console.log('  最短手数は一致: ' + (a.len === b.len));
});

実行する。

node parkout-solver.js

出力はこうなる。

easy-1: 6x6 / 動く車 6台 / キーの基数 7（数値キーの上限 18台）
  枝刈りあり: 最短 8手 / 展開 38
  枝刈りなし: 最短 8手 / 展開 1937
  最短手数は一致: true
hard-6: 7x7 / 動く車 13台 / キーの基数 8（数値キーの上限 17台）
  枝刈りあり: 最短 19手 / 展開 540
  枝刈りなし: 最短 19手 / 展開 219576
  最短手数は一致: true

ここに出ている 8手 と 19手 は、ゲーム側が画面に表示している最短手数と一致する。この2面は本番の面データをそのまま持ってきたものである。

試しどころを3つ挙げておく。

1. もう一回り大きい面を足してみる。次は 8×8・動く車15台の面（ゲーム内の big-1）である。枝刈りありなら 最短17手・展開2,315・十数ミリ秒で解けるが、枝刈りなしにすると300万盤面を打ち切っても答えが出ない（打ち切りを外すと手元では Node がヒープを使い切って落ちた）。

   var BIG1 = ['#...#....#', '.n.cAaa...', '.N.CpiiI..', '...dphhhH.', '.goDp..rr#',
               '.gOLllqqq.', '#GmmMB....', '..fF.bkkK.', '.EeeebJjj#', '#........#'];

2. stateKey の基数を 13 に決め打ちにして、上の keyOf の例（[12, 0] と [11, 13]）を通してみる。辺が14マス以上ある盤面では別の状態が同じキーになる。BFSは「もう見た」として捨てるので、そこから先の答えは信用できなくなる。落ちも例外も出ないのが厄介なところである。

3. 面の文字列を自分で書き換えてみる。出口（外周の .）を1つ潰すと、最短手数がどう跳ね上がるか、あるいは null（解けない）になるかが分かる。出口の位置が難易度をほぼ決めていることが見えてくる。

まとめ

全車を出すタイプの駐車場パズルは、状態空間としては素直だが、そのまま素のBFSに投げると大きい面で破綻する。実装で効いたのは、アルゴリズムの置き換えではなく2つの小さい判断だった。

出せる車があるならそれだけを見るという枝刈りは、交換論法で最短を壊さないことが言え、13台の面で展開数を406分の1にした。状態キーの基数を面の大きさから決めるのは速度の話ではなく正しさの話で、決め打ちにすると探索が静かに嘘をつく。どちらも動いているうちは見えず、テストでしか押さえられない種類の性質である。

実際の手ざわりを確かめたい場合は パークアウト を遊んでみてほしい。画面に出ている「この面の最短は N 手」は上と同じ探索の出力で、ヒントもその場で解き直して1手目を返している。ほかのブラウザゲームも、遊びの裏に1つずつ実装上の主題を置いてある。