8パズルはコンパクトな見た目に反して、大きな名声を誇ります。1から8までの番号が付いた8枚の正方形タイルが3×3の盤面に並び、1マスだけ空いています。空きマスにタイルをスライドさせ、1手ずつ動かして、数字を順番に並べるのが目標です——通常は上段に1-2-3、中段に4-5-6、下段に7-8-空きとなります。
これはNパズルファミリーの最小メンバーです。15パズルの方が知名度は高いですが、子供も学生も探索アルゴリズム研究者も、たいてい8パズルからスタートします。
1手の動かし方
実際にコントロールできるのは空きマスだけです。空きマスの真上・真下・真左・真右にあるタイルしかスライドさせられません。斜め移動は不可。タイルを持ち上げて別の場所に置くことも不可。すべての手は、隣接する1枚のタイルを1マス空きマスへスライドさせるものです。
このシンプルなルールがパズルを面白くしています。いつでも使える手は1〜2手しかないように感じますが、3×3の盤面には181,440通りもの解ける配置が隠されています。（もう半分——解けない配置——については転倒数（パリティ）の解説記事をご覧ください。）
標準的な攻略法
多くの人が自力で気づき、4×4・5×5・6×6以上にもスケールする方法はこれです：
- まず上段を揃える — 1・2・3を上段に配置し、二度と崩さない。
- 次に左列を揃える — 4と7を配置する。これで上段と左列がロックされる。
- 残りの2×2 — タイル3枚と空きマス1つ——は「揃っている」か「1枚ずれている」かの2状態しかない。1枚ずれている場合、2×2内だけの操作では解けません。パズル全体に手を戻す必要があります。（だから偶奇性が重要です。）
難しいのは各行・各列の最後のタイルの配置です。3を右上隅に入れるには、まず2を右上隅に入れ、その下に3を回り込ませ、ペアを回転させて配置する必要があります。この「L字型」の動きは、15パズルや24パズルなど、あらゆるサイズで使う手筋と同じです。
最適解は短い
最も難しい8パズルの最適解は31手です。181,440通りすべての開始状態の中で、最悪のケースでもゴールまで31手以内です。
平均的な盤面は約22手で解けます。良いヒューリスティックを使ったA*探索なら、コンピュータはミリ秒で最適解を見つけます。手動でも、上段攻略法を知っていれば、パターンをつかんだ人なら1分かからずに解けます。
コンピュータサイエンスが8パズルを愛する理由
8パズルはヒューリスティック探索の標準的な入門ベンチマークです。全探索できるほど小さく、力まかせの探索が非効率なほど大きく、2つの有名なヒューリスティックの違いを示すのに十分なリッチさを持っています：
- ずれたタイル数 — ゴール位置にないタイルの数を数える。計算コストは低いが、案内力は弱い。
- マンハッタン距離 — 各タイルについて、ゴールまでの行距離と列距離の和。案内力が強く、計算コストも低い。
マンハッタン距離を使った教科書的なA*実装は、どんな8パズルもマイクロ秒で解きます。15パズルになると高速化のためにパターンデータベースが必要になりますが——それはより大きな話で、15パズル ソルバーのガイドで扱っています。
8パズルを遊ぶシーン
3×3の盤面はちょうどいい気持ちよさがあります。考える手はそれほど多くなく、クリア条件は明確で、1〜2分で完了します。こんな場面に最適です：
- 「1手先を考える」感覚を学ぶ子供。
- バスに乗っていて長いパズルを手元に持ちたくない大人。
- 15パズルに挑戦する前の練習。
また、スライドパズルアプリでほぼ常に無料で遊べるサイズでもあります。大きい盤面はプレイ時間が長くセッションが増えるため有料になりがちですが、3×3はどのアプリでも入門として提供されています。
4×4になると何が変わるか
攻略法はすべて同じです。上段を揃え、左列を揃え、残りの3×3に再帰します。変わるのは時間——8パズルの30秒が15パズルの5〜10分になります。5×5や6×6では本格的な忍耐が必要です。
1週間で8パズルが物足りなくなってきたら、それがサイズアップのサインです。