背景
満車の駐車場から車を全部出す、というパズルゲームを作っています。
車は自分の向きの軸にしか動けず、前向きでしか外へ出られない。
面ごとに「最短何手で全部出せるか」を画面に出していて、これを幅優先探索で求めています。
ただ、全部の手を素直に展開すると、台数が増えたときに状態が爆発します…
ゲームでは枝刈りを1つ入れていて、それで状態数が桁で減るので、その理屈と実測を書いておきます。
ルールと、探索の形
盤面はマス目で、車は長さ2〜5の棒だ。
1手は「1台を、1方向へ、好きなマス数だけ動かす」。3マス滑らせても1手と数える。
車の鼻先の向きが前で、前方向に辺まで空いていれば、その1手で外へ出られる。
バック（後ろ向きの移動）は場所を空けるためだけに使えて、後ろからは出られない。
幅優先探索（BFS）は、スタートの盤面から「1手で行ける盤面」「2手で行ける盤面」…と距離の近い順に広げていく探索です。
最初に「全台が外にいる盤面」に着いたときの手数が、そのまま最短手数になる。
その代わり、途中で出てきた盤面を全部覚えておく必要があって、盤面の数（状態数）がそのままメモリと時間になります。
枝刈り: 出せる車があるなら、その1手だけを見る
いま前が空いていて出られる車 X がいるとき、X を出す手だけを候補にして、ほかの手は展開しません。
これで最短手数が変わらない理由は、ゲームのコメントにこう書いてあります（要約です）。
- X を出すと、盤面の占有は「X が残っている盤面」より減るだけなので、あとの手は全部そのまま打てる
- X はどのみち最後に1手使って出る。だから X の途中の移動を捨てて先に出す手順は、元の手順より長くならない
- つまり「出せるときに出す」を含む最短手順が必ず存在する
ここで大事なのは、このルールでは車を出しても誰かの邪魔にならないことです。
逆に「出た車が出口の前に置かれる」ようなルールだと、この理屈は成り立たない（先に出すと損をする場合がある）ので、枝刈りも使えません。
動かして確かめる
ゲームの本体は出口の開閉や動かせない車まで扱っていて長いので、探索の骨組みだけを縮めて書き直したのが下記です。
盤面は文字列の配列で、. が空き、# が柱、英字が車（同じ文字が1台、大文字のマスが鼻先）。
外周はどこでも出口として扱っています。
状態は「各車の先頭座標」の配列で、外へ出た車は -1 にする。
// parkout-mini.js
// 駐車場から全部の車を出す最短手数を、幅優先探索で求める（縮小版）
function parse(rows) {
const h = rows.length, w = rows[0].length, bag = {};
const wall = [];
for (let y = 0; y < h; y++) for (let x = 0; x < w; x++) {
const ch = rows[y][x];
wall[y * w + x] = ch === '#';
if (ch === '.' || ch === '#') continue;
const k = ch.toLowerCase();
(bag[k] = bag[k] || { cells: [], nose: null }).cells.push({ x, y });
if (ch !== k) bag[k].nose = { x, y };
}
const cars = Object.keys(bag).sort().map((k) => {
const cs = bag[k].cells, xs = cs.map((c) => c.x), ys = cs.map((c) => c.y);
const axis = new Set(ys).size === 1 ? 0 : 1; // 0=横 1=縦
const pos = axis === 0 ? Math.min(...xs) : Math.min(...ys);
const len = cs.length, lane = axis === 0 ? ys[0] : xs[0];
const front = axis === 0 ? (bag[k].nose.x === pos ? -1 : 1) : (bag[k].nose.y === pos ? -1 : 1);
return { name: k, axis, len, lane, front, pos };
});
return { w, h, wall, cars };
}
// 状態は「各車の先頭座標」の配列。出た車は -1。
function occ(B, st) {
const o = B.wall.map((v) => (v ? 1 : 0));
st.forEach((p, i) => {
if (p < 0) return;
const c = B.cars[i];
for (let k = 0; k < c.len; k++) o[c.axis === 0 ? c.lane * B.w + p + k : (p + k) * B.w + c.lane] = 1;
});
return o;
}
// 車 i を sign 方向へ何マス動けるか、辺まで抜けられるか
function slide(B, st, o, i, sign) {
const c = B.cars[i], lim = c.axis === 0 ? B.w : B.h;
let p = sign > 0 ? st[i] + c.len : st[i] - 1, steps = 0;
while (p >= 0 && p < lim && !o[c.axis === 0 ? c.lane * B.w + p : p * B.w + c.lane]) { steps++; p += sign; }
return { steps, exit: (p < 0 || p >= lim) && sign === c.front };
}
function moves(B, st, prune) {
const o = occ(B, st), out = [];
if (prune) {
// 出せる車がいれば、その1台を出す手だけを返す
for (let i = 0; i < st.length; i++) if (st[i] >= 0 && slide(B, st, o, i, B.cars[i].front).exit) return [[i, 'out']];
}
for (let i = 0; i < st.length; i++) {
if (st[i] < 0) continue;
for (const sign of [1, -1]) {
const r = slide(B, st, o, i, sign);
for (let d = 1; d <= r.steps; d++) out.push([i, sign * d]);
if (r.exit) out.push([i, 'out']);
}
}
return out;
}
function solve(B, prune) {
const st0 = B.cars.map((c) => c.pos), seen = new Map([[st0.join(','), null]]);
const queue = [st0];
for (let head = 0; head < queue.length; head++) {
const st = queue[head];
for (const [i, d] of moves(B, st, prune)) {
const ns = st.slice();
ns[i] = d === 'out' ? -1 : ns[i] + d;
const key = ns.join(',');
if (seen.has(key)) continue;
seen.set(key, [st.join(','), B.cars[i].name + (d === 'out' ? ' 出庫' : (d > 0 ? ' +' : ' ') + d)]);
if (ns.every((p) => p < 0)) {
const path = [];
for (let k = key; seen.get(k); k = seen.get(k)[0]) path.unshift(seen.get(k)[1]);
return { len: path.length, states: seen.size, path };
}
queue.push(ns);
}
}
return null;
}
const board = parse([
'c...Bb',
'C.....',
'...Fff',
'gGd.a.',
'.ED.A.',
'.eHhh.',
]);
for (const prune of [false, true]) {
const r = solve(board, prune);
console.log(prune ? '枝刈りあり' : '枝刈りなし', '最短', r.len, '手 / 登録した状態', r.states);
if (prune) console.log(r.path.join(' → '));
}
moves() の prune が枝刈りのスイッチで、ゲーム側の successors() と同じことをしています。
solve() は、見たことのある盤面を seen に覚えながらキューで広げ、全車が -1 になった盤面に着いたら、親をたどって手順を組み立てる。
この盤面は、c・g・d・h・e の5台がお互いの前をふさいで輪になっています。
c は下の g に、g は右の d に、d は下の h に、h は左の e に、e は上の g にふさがれている。
Node.js v24.11.1 で実行した結果が下記です。
$ node parkout-mini.js
枝刈りなし 最短 10 手 / 登録した状態 177953
枝刈りあり 最短 10 手 / 登録した状態 647
f 出庫 → a -2 → d -2 → g 出庫 → c 出庫 → b 出庫 → e 出庫 → h 出庫 → a 出庫 → d 出庫
最短手数はどちらも10手で同じ、登録した状態は 177,953 から 647 に減りました。
手順を見ると、f を出して空いた行へ a と d を2マスずつバックさせ、d がいなくなった行から g を出して輪を切っています。
8台に対して10手なので、バック2回ぶんが「考えどころ」になっている面、という感じです。
ゲーム本体の探索関数そのものでも確かめました。
<script> から探索まわりを切り出して、実際の面 easy-1（6台・最短8手）にかけると、登録した状態は枝刈りありで 38、枝刈りなしで 1,937 でした。
どちらも画面に出している最短手数 8 と一致しています。
なぜこれが要るのか
ゲームでは、この探索を面の読み込み時だけでなく、ヒントボタンを押すたびにも走らせています。
ヒントは「いまの盤面からの最短手順の1手目」なので、プレイヤーが寄り道した盤面からもう一度解き直す必要がある。
ヒントの探索には上限（22万状態）を付けていて、超えたら「読み切れませんでした」と返すだけです。
スマホで押した瞬間に返ってこないと使い物にならないので、状態数を減らすことがそのまま遊び心地になります（上限に当たると、ヒントが出ないボタンになってしまう…）。
もう1つ、面を自動生成する無限モードでは「最短手数が分かっている面」しか出せません。
最短手数から制限手数を決めているからで、探索が打ち切りになった面は捨てて作り直している。
コードのコメントには、この枝刈りで14台の面でも数万状態で解ける、と書いてあります。
トレードオフとしては、枝刈りの正しさがルールに依存していることです。
「出庫しても他の車の邪魔にならない」が崩れるルールを足すと、この枝刈りは黙って間違った最短手数を返すようになる。
なのでゲームのリポジトリには、枝刈りありの探索と枝刈り無しの素の幅優先探索が同じ最短手数を出すこと、全部の面の表示中の最短手数が探索結果と一致すること、を確かめるテストを置いています。
全車を外へ出す型のパズルで BFS が重いときは、まず「出せる車は先に出す」の1手に絞れないかを疑ってみてください。
本記事はAI補助で執筆した、個人開発の紹介記事です。