スライドパズル徹底解説：可解性とパリティから最適解探索までのアルゴリズムと実装のコツ
エバープレイ編集部概要
スライドパズル（滑りパズル、sliding puzzle）は、格子状の盤面上で1つまたは複数の空きマスを利用してタイル（数字や絵）の位置を入れ替え、ある目標配置を作るパズルの総称です。代表例は4×4の「15パズル」（1〜15の数字タイルと1つの空き）で、移動は隣接するタイルを空きとスライドさせる操作のみ許されます。単純なルールながら、可解性の古典的な性質や探索アルゴリズムの実験場として歴史的・学術的に重要な題材です。
歴史とサモン・ロイドの神話
15パズルは1870年代後半に米国で大流行しました。流行の際、パズルを広めた人物の一人にサモン（Sam Loyd）がいますが、しばしば「ロイドが発明した」と誤って伝えられます。実際にはロイドは発明者ではなく、パズルを宣伝し「14と15を入れ替えよ（14–15問題）」という挑戦を出して論争を引き起こしたことで有名です。ロイドはその挑戦に賞金を付けましたが、その配置は理論上不可能（不可解）であり、これが誤解や逸話を生みました。
スライドパズルの文化的・数学的取り扱いはその後も続き、20世紀以降は計算機科学の探索アルゴリズムやヒューリスティック評価関数の研究対象として用いられてきました。
数学的性質：可解性とパリティ
スライドパズルには「可解性（ある配置が目標に到達可能か）」を決定する簡潔な判定法があります。代表的な4×4の15パズルの場合、すべての配置は16!通りありますが、そのうち到達可能な配置はちょうど半分、つまり16!/2です。一般には「転倒数（inversion）の偶奇」と「空きマスの行番号」が鍵になります。
- 盤面幅が奇数（例：3×3）なら、タイルの転倒数（読み取り順における i
- 盤面幅が偶数（例：4×4）なら、（転倒数 + 空きマスの行番号（下から数えて））の偶奇が一致することが可解条件。
直感的には、隣接タイルを1回スライドさせる操作はタイルの順序に対して特定のパリティ（偶奇）変化しか生じさせないため、全体としてある不変量が残る、ということです。これにより「14と15だけを入れ替えた配置」など、見た目では簡単そうでも到達不能なケースが存在します。
アルゴリズムと解法：実用的手法と最適解探索
スライドパズルは探索問題の典型です。状態空間は有限ですが爆発的に大きくなるため、効率的な探索と良いヒューリスティックが重要になります。
- A*探索：適切な評価関数（f = g + h）を用いて最短経路を求める代表的手法。ヒューリスティックhが「許容（admissible）」であれば最適解が保証されます。
- IDA*（反復深化A*）：メモリ節約型の深さ優先反復深化法で、A*のメモリ問題を回避します。Richard E. Korfらがスライドパズルで有効性を示しました。
- ヒューリスティックの例：
- マンハッタン距離：各タイルの現在位置と目標位置との縦横距離の合計。単純で許容的（下界）です。
- 線形衝突（linear conflict）：マンハッタン距離に加え、同じ行（または列）にあって互いに行き違いを起こすタイル対を数えて上乗せする手法で、より厳密な下界になります。
- パターンデータベース（Pattern Database, PDB）：部分配置（例えば特定のタイル群）の最短手数を事前にテーブル化し、ヒューリスティックとして合成することで非常に強力な評価が得られます。
- 実運用では、PDB と IDA* の組合せが高次元でも現実的な最適解探索を可能にします。Korf はこうした手法を用いて多くの最短解を効率的に求めました。
計算複雑性
盤面サイズ（n）が固定されている場合、状態が有限のため理論上は多項式時間で判定可能な性質もありますが、最短解を求める問題の難しさは急速に増大します。重要な理論的結果として、パズルのサイズを入力の一部として一般化した場合（n が変化する場合）、最短解を求める問題は計算困難であり、最適解を決める決定問題は NP困難（あるいはNP完全に関連）である、という結果が示されています（研究論文参照）。実務的には、15パズルですら最短解検索は大きな探索空間となるため高度なヒューリスティックやメモリ工夫が必要です。
バリエーションと応用
- Nパズル：一般化された n×n の (n^2−1)-パズル。
- スライディングブロック（例：Klotski、Rush Hour）：複数マスを占めるブロックや異なる移動ルールを持つ変種。
- 画像スライドパズル：写真や絵をシャッフルして元に戻すタイプ。UX上よく使われる。
- 教育・研究用途：探索アルゴリズム、ヒューリスティック設計、パターンデータベース学習、性能評価のベンチマークとして広く使われています。
ゲームデザインと実装のコツ
- ランダム生成の注意：単純にタイルをランダム並べするだけでは不可解（解けない）配置が含まれる可能性があります。安全な生成法は「目標配置から一定手数ランダムに合法移動を繰り返す」方法で、必ず可解なシャッフルが得られます。
- 難度調整：シャッフル回数を増やす、あるいは特定のタイルのみを乱すことで難易度を制御できます。ヒューリスティックな難易度評価（総マンハッタン距離や線形衝突数）を用いるとより客観的に調整できます。
- ユーザー向け機能：解法のヒント表示（部分的な最短手数）、自動ソルバー、履歴の取り消し/やり直し、タイルが動くアニメーションなどがUXを向上させます。
まとめ
スライドパズルは単純な操作ルールから深い数学的性質と計算的難題を生み出す、ゲームデザインとアルゴリズム研究の両面で魅力的な題材です。可解性の判定、強力なヒューリスティック（マンハッタン距離、線形衝突、パターンデータベース）、IDA*などの探索戦略を組み合わせることで、実用的かつ教育的なゲームや研究実験が構築できます。実装では必ず可解な初期配置を作ること、難度評価のために下界ヒューリスティックを利用することが重要です。
参考文献
- 15 puzzle — Wikipedia (英語)
- 15 Puzzle — Britannica
- Sam Loyd — Britannica（ロイドと15パズルに関する解説）
- Iterative deepening A* (IDA*) — Wikipedia (英語)
- Pattern database — Wikipedia (英語)
- R. E. Korf, "Depth-first Iterative-Deepening: An Optimal Admissible Search Algorithm", AAAI 1985 (論文)
- D. Ratner, M. K. Warmuth, "Finding a shortest solution for the N × N − 1 puzzle is NP-hard", Artificial Intelligence (関連研究)
投稿者プロフィール
