ソルバーと解法

15パズルソルバー — 実際に機能するヒューリスティック

15パズル（および大きな盤面）を解くための実践ガイド — 手動では行と列の方法、コンピュータではマンハッタン距離を使ったIDA*、そしてさらに先には歩行距離とパターンデータベース。

更新日 2026-05-20 9 分で読めます

スライドパズルソルバー

「シャッフル」でランダムな盤面、「編集」で自分の盤面を入力できます。「解く」を押すと手順を1手ずつ再生します。3×3 の解は最短手順です。

15パズルの解き方には2つある。1つは、すべてのプレイヤーが最終的に発見する方法だ。上の行を解き、左の列を解き、再帰する。もう1つはコンピュータのやり方だ。残り手数の賢い下限推定値に導かれながら、何百万もの状態をヒューリスティック探索する。

このガイドでは、ほとんどの人が学ぶ順序でその両方を説明する。

15パズルとは（1段落で）

4×4の盤面、15枚の番号付きタイル、1つの空きマス。タイルをすき間にスライドして、数字が順番に並ぶようにする。1から15まで、空きマスは右下の角に来る。この盤面は1874年にNoyes Chapmanが発明し、サム・ロイドが解けない変形問題に1000ドルの賞金をかけた1880年代に国際的なブームとなった。基本的には8パズルと同じパズルで、ただ1行1列だけ大きい。

手動での解き方：行と列の方法

すべての人間が最終的に発見するテクニックはこれだ：

第1行を解く。 1と2を配置する。次に3を右上の角に配置する。「L字形マヌーバー」—4を位置3に持ってきて、3をその下に滑らせ、2枚を角に回転させる—が角を可能にするコツだ。
第1列を解く。 5、次に9、次に13を左下の角に配置する。同じL字形マヌーバーを使う。
再帰する。 残るのは3×3の部分パズル（右下の列と行を含む）で、これはすでに解き方を知っている8パズルだ。

慣れたプレイヤーなら手動で15パズルを3〜5分で解ける。初心者は初回に20分かかるかもしれないが、3回目には3分の1になる。

同じ方法は5×5や6×6にもスケールする。再帰は常に3×3のエンドゲームで終わる。

最適ソルバー：マンハッタン距離を使ったA*

コンピュータは行と列の方法よりずっとうまくできる。具体的には、最短解を見つけることができる。これは人間がプレイするものとは大きく異なる。

数学的な事実：15パズルの中央値は、最適に解いた場合に約52手かかる。最悪のケースは80手だ。行と列の方法では同じ盤面で通常100〜150手かかる。

最適解を見つけるため、A探索では各盤面状態をノード、各手をエッジとして扱い、「最低でもあと何手でゴールか？」を問う。残り手数の最小値は実際には解かないと計算できないが、良い下限推定値があればAは速くなる。

古典的な下限推定値がマンハッタン距離だ：

各タイルについて、現在位置からゴール位置までの行距離と列距離の合計を求める（空きマスを除く）。

マンハッタン距離は許容的だ。各タイルは最低でもその距離を移動しなければならないので、真の距離を過大評価しない。A*とマンハッタン距離を組み合わせると、8パズルはマイクロ秒で解け、15パズルは数秒で解ける。

IDA*：メモリに優しい兄弟

A*は探索したすべての状態を記憶する必要がある。15パズルでは、最難関の盤面では数百MBのRAMが必要だ。反復深化A（IDA）**はヒューリスティックを使った深さ制限DFSを行い、毎ラウンドで深さ制限を引き上げることで、時間とメモリをトレードオフする。

IDA*はすべての15パズルの参照ソルバーが実際に使っているものだ。Richard Korfの1985年の論文は、1980年代初頭のハードウェアで15パズルを最適に解くために、まさにこれを紹介した。

マンハッタン距離を超えて：歩行距離とパターンデータベース

マンハッタン距離は速いが粗い。タイルが自由に互いをすり抜けられると仮定している。実際にはすり抜けられない。同じ行にある2枚のタイルは交互に移動する必要があり、余分な手数がかかる。

歩行距離はその余分な手数を数える。各行のペアについて、タイルを正しい行に並べ替えるのに必要な「行スワップ」の最小数を事前計算する。列についても同様。両者を足す。結果はマンハッタン距離より証明可能に精密で、通常約25%大きい。つまりA*/IDA*が展開するノードが25%少なくなる。

15パズルで最強のヒューリスティックは加算型非重複パターンデータベースだ：

タイルを非重複グループに分割する（一般的な分割は5-5-5プラス空きマス）。
各グループについて、盤面上のそのグループのタイルの全配置について、他のすべてのタイルを無視しながらそのタイルをゴール位置に置くのに必要な最小手数を事前計算する。
探索時に、各グループのルックアップを加算する。

15パズルの7+8分割は格納に約1GBを要するが、IDA*で任意の15パズルをミリ秒で解けるようになる。24パズル（5×5）では、パターンデータベースが実質的に唯一の実用的なアプローチだ。

手動解法がほとんどの場合速い理由

簡単な現実確認：A*実装を書き、ヒューリスティックを選び、実行を待つのは、15パズルを1枚手で拾い上げて解くより時間がかかる。数学は面白いが、行と列の方法を知る人なら5分でどんな盤面でも解ける。

ソルバーが重要なのは集計のためだ。数千のランダムインスタンスでヒューリスティックを比較する研究論文、15パズルをベンチマークとして使うAIの教科書、そして難易度調整のためにN手程度で解けることが保証されたパズルを生成する必要があるアプリだ。