15パズルを置換の偶奇性と IDA* で解く — Sam Loyd の 14-15 問題を探索なしで「不可能」と証明する

古典 15パズル を、本物のアルゴリズム 2 本立てでブラウザに実装した。(1) 可解判定は置換の偶奇性（パリティ）で、探索ゼロ — Sam Loyd が 1890 年代に賞金を懸けた「14 と 15 を入れ替えた盤面」は O(n²) の算術で証明付きの不可能と判定できる、(2) ソルバーは IDA*（反復深化 A*）＋ Manhattan 距離＋linear conflict で、最短解を求めてアニメ再生する。テストは BFS の厳密最適値との照合まで。#33 数独・#284 ライツアウトに続く「ソルバー内蔵パズル」第 3 弾。

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

パリティ: 探索なしで不可能を証明する

スライドは毎回「空白とタイル 1 枚の互換（transposition）」だ。盤面の 転倒数（順序が逆のタイル対の数）を数えると、横スライドでは変わらず、縦スライドではタイル 1 枚がちょうど n-1 枚を追い越す。ここで規則が盤の幅の偶奇で分岐する:

• 奇数幅（3×3）: n-1 が偶数なので、転倒数の偶奇だけが不変量 — 可解 ⇔ 転倒数が偶数。
• 偶数幅（4×4）: 縦スライドごとに転倒数の偶奇が反転し、同時に空白が 1 行動く — 転倒数 + 空白の行距離 が不変量。

Sam Loyd の懸賞パズル——完成盤で 14 と 15 だけ入れ替えたもの——は互換 1 回ぶんパリティがズレているので解けない。1 ページの算術で証明でき、デモの Loyd trap ボタンで実際に試せる。ソルバーは 1 ノードも展開せずに "provably unsolvable" と返す。

実装中に踏んだ罠

最初の実装は偶数幅の規則を 3×3 にも適用していた。ランダム化テスト（50 個のランダムウォーク盤が全可解のはず）と BFS との照合テストが即座に検出。「パリティ規則は幅で違う」は教科書にも書いてある古典的な罠で、テストが仕様の誤解を捕まえた良い例だった。

IDA*: O(深さ) メモリで最短解

A* は最短解を出すが、フロンティアが指数的にメモリを食う。IDA*（反復深化 A*）は f = g + h の上限付き深さ優先探索を、超過した最小の f を次の上限にして繰り返す——最適性はそのまま、メモリは解の深さに比例:

for (;;) {
  const t = dfs(0, -1);          // f > bound で枝刈りする DFS
  if (t === -1) return { moves: path, nodes };
  bound = t;                     // 旧上限を超えた最小の f が次の上限
}

ヒューリスティックは Manhattan 距離 + linear conflict。同じ行（列）が定位置で順序だけ逆のタイル対は、互いを追い越すために最低 2 手余計にかかる——これを足しても admissible（過大評価しない）で、Manhattan 単体よりはるかに鋭い。medium シャッフルなら 1 秒未満で最適解が出る。ステータス行に手数・展開ノード数・時間を表示している（スクショでは 44 手最適解を 70 万ノード・529ms）。

テスト: BFS との突き合わせ

vitest 18 ケース。パリティ分類（Loyd 盤含む）、ランダムウォークが常に可解、3×3/4×4 の解のリプレイ検証、ヒューリスティックの admissibility——そして一番強いのが ランダム 8 パズルで IDA の解長が BFS の厳密最適値と一致*することの確認だ:

const opt = bfs(b);            // 総当たりの厳密最短
const r = solve(3, b);
expect(r.moves!.length).toBe(opt);

「最適と主張するなら、別アルゴリズムで検証する」——ソルバー内蔵パズルシリーズで一貫させている方針だ。

src/puzzle.ts      — 純粋エンジン: パリティ判定, Manhattan+linear conflict, IDA*, スクランブル
src/puzzle.test.ts — 18 ケース（パリティ・admissibility・リプレイ検証・BFS 照合）
src/main.ts        — DOM 殻: グリッド・クリック操作・解アニメ・Loyd trap

まとめ

15パズルは「不可能の証明（パリティ）」と「最短解の探索（IDA）*」という 2 つの古典が 1 つの盤面に同居する稀有な題材だ。数独(#33)・ライツアウト(#284) に続くソルバー内蔵パズル第 3 弾。デモの Loyd trap で 130 年前の賞金問題が一瞬で「不可能」と判定される様子をぜひ。

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