15パズルは1960年代からAI探索アルゴリズムのベンチマークとして使われてきた。各世代のアルゴリズムは、前世代がぶつかった壁を突破するために生まれた。この記事では発明順に各アルゴリズムを紹介し、それぞれの強みと次世代が必要になった理由を解説する。
1960年代 — 幅優先探索（BFS）
誰もが最初に試すアルゴリズム。状態を深さのレベルごとに探索する。深さ1では4状態、深さ2では16状態、深さ3では64状態…というように探索を続け、ゴールが見つかるまで繰り返す。
8パズルではBFSはすぐに終わる。最悪の深さが31なので、実際には状態の重複を考慮するとずっと少ない状態しか探索しない。しかし15パズルでは最大深さが80で、4⁸⁰の状態がある。これは観測可能な宇宙の原子数より多い。BFSでは終わらない。
限界：指数的な状態爆発。未informed探索で3×3より大きいパズルを解くのは絶望的だ。
1968年 — A*探索
Hart、Nilsson、Raphaelが『最小コスト経路のヒューリスティックな決定のための形式的基礎』を発表。アイデアは単純だ：状態を「スタートからの距離」順ではなく f = g + h 順で探索する。ここで h は残り距離の下限推定値だ。
15パズルでは h にマンハッタン距離を使う。各タイルのゴール位置までの行距離と列距離の合計だ。マンハッタン距離は許容的（真の距離を過大評価しない）かつ一貫的（三角不等式を満たす）。これらの性質により、A*は最適解を見つけられる。
15パズルでの性能：あらゆる盤面を解けるが、最難関の問題では数百万の状態を探索し、数百MBのメモリを消費する。限界：メモリ。
1985年 — IDA*
Richard Korfの『反復深化深さ優先探索：最適な許容ツリー探索』。洞察は次の通りだ。A*の優先度付きキュー（探索済み全状態を保持）の代わりに、深さ制限を深さではなくfコストにした反復深化DFSを行う。
IDAはAが探索する状態をほぼ同じ順序で探索するが、イテレーション間で状態を記憶しない。各「深さ優先スイープ」は探索した状態数ではなくO(深さ)のメモリしか使わない。
15パズルでの性能：1985年代のハードウェアで任意の盤面を数秒で解け、数KBのメモリで動作する。限界：ヒューリスティックがまだマンハッタン距離。探索を高速化するにはより精密なヒューリスティックが必要だ。
1990年代 — 線形競合
Hansson、Mayer、Yungの『緩和モデルへの解の批判が強力な許容ヒューリスティックを生む』。マンハッタンヒューリスティックはタイルが互いをすり抜けられると仮定している。実際にはすり抜けられない。
線形競合は、同じ行にあって両方ともその行が目標行だが順序が逆のタイルの組ごとに、2手をヒューリスティックに加算する。一方が他方を通過させるためにいったん行の外に出る必要があるからだ。列についても同様。
効果：難しい15パズルで展開するノード数が通常5〜15%削減される。純粋なマンハッタン距離に対して厳密な改善で、実質的なデメリットはない。
1996年 — 歩行距離
パズルの構造をより深く捉えるヒューリスティック。タイルの配置を行のみに射影したもの（行内での位置は無視）を考え、各タイルを正しい行に収めるために必要な最小の行スワップ操作数を事前計算する。列についても同様。
歩行距離は許容的で、マンハッタン距離＋線形競合よりかなり精密だ。典型的にはマンハッタン距離の1.5〜2倍の値を返すため、IDA*が展開するノードが大幅に減る。
実装コスト：小さな事前計算テーブル（4×4で約500KB）。15パズルにとってベストな選択肢だ。
2002年 — 加算型非重複パターンデータベース
KorfとFelnerの『非重複パターンデータベースヒューリスティック』。スライドパズルで最強と知られるヒューリスティック。
アイデア：タイルを非重複グループに分割する（15パズルでは7+8分割が標準）。各グループについて、そのグループのタイルだけをゴール位置に移動する最適コストを、他のタイルを無視して事前計算し、グループの全配置をテーブル化する。
探索時に各グループの値を参照して合計する。グループが非重複で各グループに必要な手が競合しないため（慎重な議論が必要だが）、合計値は許容的だ。
メモリコスト：15パズルで約1GB。性能：最難関の15パズルを数千ノードの展開、つまりミリ秒で解く。
2005年以降 — より大きなパズルへのパターンデータベース
同じ手法は24パズル（5×5）以降にもスケールする。24パズルでの5+5+5+9分割は約4GB。これにより、任意のランダムな24パズルが数秒で解ける。
35パズル（6×6）は実用的な限界に位置する。最難関の6×6問題は2026年時点でも未解決の研究課題だ。
2010年代以降 — ニューラルネットワークヒューリスティック
ニューラルネットワークはスライドパズルのマンハッタン距離的な値を予測するように学習でき、手作業のものより精密なヒューリスティックを生み出す場合もある。ただし問題がある：NNヒューリスティックは一般に許容性が証明できないため、それに基づくソルバーはおそらく最適な答えしか返せない。
研究論文では興味深いが、最適性が重要なソフトウェア（ゲームの難易度調整など）では、古典的なパターンデータベースが依然として正しい選択だ。
この歴史が重要な理由
スライドパズルのアルゴリズム研究の各波は、同じ圧力によって駆動されてきた。このパズルはアルゴリズムのベンチマークに十分なほど小さく、悪いアルゴリズムがタイムアウトするのに十分なほど大きい。15パズルは、A*、IDA*、パターンデータベースなど、ヒューリスティック探索の一般的な発展のテストベッドとなり、今や経路計画、定理証明、その他多くの分野で活用されている。
アプリでヒントボタンを使って15パズルを解くとき、あなたはまさにこのゲームのために開発され、その後あらゆる場所に一般化されたアルゴリズムを使っているのだ。
まとめ表
| 年 | アルゴリズム | 難しい15パズルの解法時間 | メモリ | 実現した技術 |
|---|---|---|---|---|
| 1960年代 | 幅優先探索（BFS） | 終わらない | 膨大 | — |
| 1968年 | A* + マンハッタン距離 | 数分 | 数百MB | ヒューリスティック探索 |
| 1985年 | IDA* + マンハッタン距離 | 数秒 | KB | 反復深化 |
| 1996年 | IDA* + 歩行距離 | 1秒未満 | +500KB事前計算 | より精密なヒューリスティック |
| 2002年 | IDA* + 7+8パターンDB | ミリ秒 | +1GB事前計算 | 部分集合の列挙 |
各行は本当に定性的な飛躍であり、わずかな改善ではない。15パズルを解く歴史は、現代のヒューリスティック探索の歴史でもある。