8パズルは、ヒューリスティック探索を学んだ日に最初に書くプログラムです。ほぼどんなアプローチでも動くほど小さく、粗いアプローチと優れたアプローチの差がはっきり見えるほど大きい。この記事では、標準的な解法を上から下まで丁寧に解説します。
状態の表現
盤面を9個の整数の配列で表します。行優先順で0〜8のインデックスを付けます。
位置: インデックス:
1 2 3 0 1 2
4 5 6 ←→ 3 4 5
7 8 _ 6 7 8
空きマスはセンチネル値で表します——通常は0を使います。ゴール状態は [1, 2, 3, 4, 5, 6, 7, 8, 0] です。
移動の定義
空きマスのインデックスを e とすると、空きマスと上下左右の隣接タイルを入れ替えられます：最上行でなければ e-3（上）、最下行でなければ e+3（下）、最左列でなければ e-1（左）、最右列でなければ e+1（右）です。
neighbors(state) という関数は、1手で到達できる最大4つの状態を返します。
ヒューリスティック：マンハッタン距離
各タイル（空きマスは除く）について、現在位置からゴール位置までの行距離と列距離の和を計算し、全タイルで合計します。この合計は残り手数の下限です——各タイルは少なくともその距離を移動しなければなりません。
疑似コードで表すと：
h(state) = タイル t のすべての和:
abs(row(現在) - row(ゴール)) + abs(col(現在) - col(ゴール))
マンハッタン距離は許容的（過大評価しない）かつ一貫性がある（三角不等式を満たす）です。A*にとって両方の性質が重要です。
A*の12行実装
A*は f = g + h の順で並べられた状態の優先度付きキューを管理します。g はこれまでの手数（深さ）、h は残り手数のヒューリスティック推定値です。各イテレーションで：最小f値の状態をポップし、展開し、更新されたfで近傍をプッシュします。
open = priority_queue()
open.push(start, f=h(start))
came_from = {}; g = {start: 0}
while open is not empty:
state = open.pop()
if state == goal: return reconstruct_path(came_from, state)
for n in neighbors(state):
tentative_g = g[state] + 1
if n not in g or tentative_g < g[n]:
g[n] = tentative_g
came_from[n] = state
open.push(n, f=tentative_g + h(n))
これがソルバーの全体です。h と neighbors を実装すれば、どんな8パズルも解けます。
性能
マンハッタン距離を使ったAは、最難のインスタンスでも数百〜数千の状態を展開するだけで、数百マイクロ秒で8パズルを解きます。状態空間が十分小さいため、このサイズではAがIDAより優位です——3×3ではAが正解で、4×4以上ではIDA*に切り替えます。
よくある落とし穴
最初の実装で必ずやらかす3つのこと：
状態のハッシュ化。 Pythonのタプルはうまくハッシュ化されますが、Javaのint配列はそうではありません。どの言語を使っても、閉集合・開集合が機能するよう状態をハッシュ化可能にする必要があります。よく使われる手法は、9タイルの状態を1つの32ビット整数にエンコードすることです（セルは0〜8なので1セルあたり4ビット）。
偶奇性（パリティ）チェックの見落とし。 シャッフルによってランダムな8パズルを生成すると、半分の確率で解けない盤面になります。Aは存在しない経路を求めて181,440状態の半空間全体を探索してしまいます。Aを実行する前に簡単な転倒数チェックを追加するか、ゴールから逆順に歩くことで生成してください。
ヒューリスティックで空きマスをタイルとして扱う。 マンハッタン距離は実際のタイルのみを対象に合計します。空きマスを含めるとヒューリスティックが過大になり許容性が壊れます（空きマスは1手で「無料で」移動できます）。
マンハッタン距離を超えて
8パズルではマンハッタン距離より良くすることはできますが、改善幅は大きくありません：
- 線形矛盾（リニアコンフリクト） — 同じ行にある2つのタイルがどちらもゴール行に入っているが順番が逆の場合、互いを入れ替えるために最低2手余分に必要です。矛盾1件ごとに2を加算します。マンハッタン距離を5〜15%改善します。
- パターンデータベース — タイルのサブセットに対して最適コストを事前計算します。8パズルではメモリコストが大きく速度向上が微小です。15パズル ソルバーでは有効ですが、ここでは不要です。
8パズルでは、マンハッタン距離＋線形矛盾が実用上の最良点です。
次に作るもの
8パズル ソルバーを書いたなら、自然な拡張として：
- 15パズル ソルバー — IDA* + ウォーキングディスタンス。同じ基本的なアイデア、より深い探索。（ガイドはこちら。）
- 汎用Nパズル ソルバー — パターンデータベース使用。週末プロジェクト向け。
- 解けるかチェック — 盤面がゴールから到達可能かどうかを返す30行の関数。アプリ開発に有用。（転倒数定理に基づく。）
8パズルは小さい。しかし解く過程で学ぶ技術は、ずっと大きな問題にもそのままスケールします。