15パズル — 「fifteen puzzle」「Mystic Square」または単に「4×4スライダー」とも呼ばれる — はスライドパズルの代名詞だ。4×4の盤面に15枚の正方形の番号付きタイルと1つの空きマス。タイルを空きマスに1手ずつスライドして、数字が順番になるようにする：1‑2‑3‑4が最上段に、5‑6‑7‑8、9‑10‑11‑12、13‑14‑15と右下に空きマスが来る。
どこから来たのか
このパズルは1874年、ニューヨーク州カナストタの郵便局長Noyes Palmer Chapmanによって発明された。1880年にはボストンの学校に到達し、1880年半ばにはアメリカで大流行し、秋にはイギリス、フランス、ドイツに渡って熱狂を巻き起こした。新聞には解法コーナーが設けられ、労働者は仕事を離れてパズルに没頭した。ドイツのいくつかの都市の当局は、政府の職員が他のことを何もしなくなったため、公共の場でのパズルを禁止したと伝えられている。
サム・ロイド — ニューヨークのパズル制作者、自己宣伝に事欠かない人物 — は自分が発明したと主張したが、それは事実ではなく、14と15が入れ替わった特定の変形問題を解いた人に1000ドルの賞金を申し出た。その変形問題は数学的に解けないことが証明されている（証明は15パズルのパリティを参照）。誰も勝てなかった。ロイドは満足した。
遊び方
3つのルール：
- 空きマスに隣接するタイルのみスライドできる — 直接真上、真下、真左、真右。斜めは不可。
- スライドでタイルが空きマスに移動する。空きマスはタイルが元あった場所になる。
- タイルが数字順に並んだら完成。
それだけだ。時間制限も、スコアも、他の目標もない。ゲームはこの3文に尽きる。
どれくらい難しいか
15パズルには到達可能な配置が16!/2 ≈ 10兆4,600億通りある（偶奇性ルールにより全16!の半分）。最難関の出発状態からの最短解は80手。中央値は約52手だ。
初心者は試行錯誤で最初の15パズルを15〜30分で解く。8パズルから行と列の方法を学んだプレイヤーは、どんな15パズルでも3〜7分で解く。最適手を選んで競うスピード競技者なら90秒以内でできる。
4×4が「ちょうどいい」理由
世界的な現象になったのが8でも24でもなく15パズルである理由がある。4×4の盤面は：
- 満足感を得るのに十分な長さがある。 8パズルはすぐに解けてしまい、本当の達成感がない。15パズルは完成した盤面の小さな安堵感を味わえる長さがある。
- ダラダラしない長さ。 24パズルは自信があるソルバーでも15分以上かかる。35パズルは30分以上。4×4はコーヒーブレイクに収まる。
- ちょうど考えさせる難しさ。 戦略は最初接触しただけでは明らかではない。「L字形のコーナーマヌーバー」は発見するか教わる必要があり、それがわかるとパズル全体が開ける。
このちょうどよさが、15パズルがファミリー全体の代名詞として使われるサイズになった理由だ。「スライドパズル」と言えば、人は4×4を思い浮かべる。
コンピュータ科学における位置づけ
何十年もの間、15パズルはヒューリスティック探索アルゴリズムの標準ベンチマークだった。Richard Korfの1985年のIDAを紹介した論文では、Aに対するスピードアップを示すために100枚のランダムな15パズルが使われた。現代のパターンデータベースの論文でも15パズルの結果が報告される。このパズルはアルゴリズムがタイムアウトしないほど十分小さく、悪いアルゴリズムがタイムアウトするほど十分大きい。
「AI入門」コースを受講したことがあれば、プログラミング演習として15パズルを解いたことがあるはずだ。おそらくA*とマンハッタン距離ヒューリスティックを使って。（より深い内容はソルバーガイドを参照。）
現代のアプリにおける変形
15パズルにはいくつかの一般的な現代の変形がある：
- ナンバータイル — オリジナル。タイルに数字だけが書かれている。
- ピクチャータイル — N×Nに分割された写真が数字の代わりになる。画像を組み立て直すことで解く。
- ハイブリッド — タイルの場所のヒントを欲しいプレイヤーのために、小さな数字が重ねられたピクチャータイル。
一部のアプリはさらに進んで、六角形グリッド、大きな盤面（5×5 = 24パズル、6×6 = 35パズル）、タイルが回転できる回転パズルなどを提供している。4×4の数字版が共通言語だ。
どこで遊ぶか
スマートフォンでは、ネイティブアプリの方が快適だ。アップロードも、分析も、タイルスライドの途中での広告もない。Slide Puzzleはクラシックな番号版に加え、300枚の写真カバーと4つのサイズ（3×3、4×4、5×5、6×6）を搭載している。
ウェブでは、ブラウザベースの15パズルが数十種類存在する。便利だが、通常は写真をアップロードしてアナリティクスを実行する。数回だけ遊んで自分の写真をインポートしたくない場合は問題ない。
以前に解いたことがなければ、8パズルで30秒だけ始めてみてください — ただ手の感覚をつかむために — その後15パズルに戻ってきてください。小さな盤面で身につけた戦略はそのまま大きい盤面に適用できる。