スライドパズルのソルバーを実装しようとしていて、どのアルゴリズムを使うか迷っている場合、この記事では6つの代表的なアルゴリズムを、速度・メモリ・実装の複雑さ・快適に扱える盤面サイズの観点で比較します。3×3、4×4、5×5では答えが異なります。
1. 幅優先探索（BFS）
最も単純な正しいアルゴリズムです。ゴールが見つかるまで状態をレベル順に探索します。
- 時間 — 解の深さに対して指数的。8パズルなら一瞬で終わります。15パズルでは、コンピューターのRAMが尽きる前に終わりません。
- メモリ — 訪問済み状態のセット全体をメモリに保持します。難しい15パズルでは数千万状態になります。
- 実装の複雑さ — 20行。
- 結論 — 3×3には十分。それ以上では使い物になりません。
2. A* + マンハッタン距離
最初の本格的なアルゴリズムです。BFSと同じ構造ですが、状態は f = g + h（hはマンハッタン距離ヒューリスティック）で並べた優先キューから取り出されます。
- 時間 — 8パズルはミリ秒、15パズルは秒から分単位。
- メモリ — 探索済みのものをすべてメモリに保持。8パズルには問題ないが、15パズルでは重くなる。
- 実装の複雑さ — 50行。ほとんどは優先キューの実装。
- 結論 — 8パズルに最適。15パズルには境界線上。
3. A* + マンハッタン距離 + 線形衝突
同じ行にある2つのタイルが、互いにゴール行に入っているが順序が逆の場合（列も同様）、ヒューリスティックに2手を加算します。この2つは互いをすり抜けなければならず、マンハッタン距離ではそれが見えません。
- 時間 — 純粋なマンハッタンA*より通常5〜15%速い。
- メモリ — 変わらず。
- 実装の複雑さ — 60行。
- 結論 — 純粋なマンハッタンA*より厳密に優れています。常にこちらを使いましょう。
4. IDA* + マンハッタン距離 + 線形衝突
反復深化A*です。f-コストを深さの基準として深さ制限DFSを行い、各イテレーションでしきい値を引き上げます。再探索によって時間とメモリをトレードオフします。
- 時間 — 再探索によりA*より1ノードあたり若干遅いですが、メモリ圧力が低いため難しい15パズルでは通常有利。
- メモリ — O(探索状態数)ではなくO(深さ)。これが強みです。
- 実装の複雑さ — 80行（再帰DFS、しきい値管理）。
- 結論 — 4×4に最適。Korf 1985以来の標準。
5. IDA* + ウォーキング距離
ウォーキング距離はより厳密なヒューリスティックです。各タイル配置を行のみに射影した状態に対して、各タイルを正しい行に入れるために必要な行スワップ操作の最小数を事前計算します。列も同様に。両者を足します。
マンハッタンが見逃している「同じ行のタイルが同じスロットを争っている」状況を捉えます。
- 時間 — ヒューリスティックが厳密でIDA*の枝刈りが増えるため、難しい15パズルでマンハッタン+線形衝突の通常2倍速い。
- メモリ — 小さな事前計算テーブルを追加（4×4で約500KB）。
- 実装の複雑さ — 150行。事前計算は縮小状態空間でのBFS。
- 結論 — エンジニアリング予算があれば4×4に最適。最初の非自明な改善。
6. IDA* + 加法的分離パターンデータベース
スライドパズルで知られている最強のヒューリスティックです。タイルを分離したグループに分割します（15パズルの一般的な分割は7+8、または5+5+5）。各グループについて、そのグループのタイルをゴール位置に並べるためのコストを、そのグループの全配置に対して事前計算します。探索時には各グループの値を参照して合計します。
- 時間 — 最も難しい15パズルをミリ秒で解きます。ランダムな24パズルを秒単位で解きます。
- メモリ — 大きい。15パズルの7+8分割は約1GB。24パズルの5+5+5+9分割は約4GB。メモリがエンジニアリングの主要課題になります。
- 実装の複雑さ — 300行以上。事前計算ステップはグループ状態空間での後退BFSで、大部分の作業を占めます。
- 結論 — 5×5と6×6に最適。3×3には過剰。
推奨まとめ
今日ソルバーを書くなら：
- 3×3：A* + マンハッタン距離 + 線形衝突。それ以上はやりすぎです。
- 4×4：IDA* + ウォーキング距離。パターンデータベースはこのサイズでは微妙な改善しかなく、実装の複雑さに見合いません。
- 5×5：IDA* + 加法的パターンデータベース（5+5+5+9が標準）。パターンDBなしでは最も難しいケースでタイムアウトします。
- 6×6（35パズル）：同じアルゴリズムでランダムなインスタンスを解けますが、最難ケースはまだ研究課題です。多くのアプリは対応しません。
機械学習はどうか
2026年時点で妥当な質問です。ニューラルネットワークのヒューリスティックは少なくとも2014年から研究されており、スライドパズルに対して高速なヒューリスティックを生成できます。問題は、通常許容的でないこと — 過大評価が可能で、その結果アルゴリズムが最適解を保証しなくなります。難易度調整のために保証された最適解が必要なアプリ開発者には、古典的なパターンデータベースが依然として正しいツールです。
研究への興味としては、ニューラルネットワークで訓練されたパターンデータベースが最も難しい15パズルインスタンスでわずかな高速化をもたらします。学術論文には有用ですが、製品リリースには些末な改善です。
実際のアプリに搭載されるもの
ヒント生成のためにソルバーが必要なモバイルアプリは、ほぼ常に次の構成に行き着きます：
- 4×4にはIDA* + ウォーキング距離。
- 5×5にはIDA* + 小さなパターンDB。
- ヒントボタンからは次の1手だけを呼び出す。
- すべてオンデバイスで動作。ソルバー全体は数百キロバイトのコードと数メガバイトの事前計算テーブル。
これが落ち着いたスマホアプリのための適切なスタックです。Slide Puzzleのヒントボタンはまさにこの方法で動作しています。