15パズルで30分費やしてもどうしても終わらない — どんな手を指しても最終的に2枚のタイルが入れ替わった状態に戻ってしまう — という経験をしたことがあれば、そのパズルが数学的に解けない可能性があります。すべての15パズルの配置のちょうど半分が解けません。粗末なアプリはうっかりそのような盤面を生成することがあります。
この記事は実践的な確認方法です。完全な数学的証明は偶奇性定理にあります。この記事ではシンプルに説明します。
30秒でできる確認
タイルを読み順に並べます — 各行を左から右、上から下 — 空きマスを除いて。
すべてのタイルのペアについて、大きい数字が小さい数字より前に現れる回数を数えます。その数が転倒数です。
次に、空きマスが何行目にあるかを下から数えます（最下段が1、その上が2、次が3、最上段が4）。
転倒数と下からの空きマスの行数を足します。結果が奇数なら解けます。偶数なら解けません。
以上です。これが確認方法のすべてです。
実際の例
盤面がこのようになっているとします：
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 _
読み順：1、2、3、4、5、6、7、8、9、10、11、12、13、15、14。
転倒数を数えます。大きい数字が小さい数字より前にあるペアを探します。確認すると：15が14より前にあり、これが唯一の転倒です。転倒数 = 1。
空きマスは最下段 → 下から1行目。
合計：1 + 1 = 2。偶数。 この盤面は解けません。
これは実際のところ、サム・ロイドが1880年に提示した賞金問題のパズルです。彼はこれを解いた人に1000ドルを約束しました。パズルは解けない状態だったため、彼は賞金を払わずに済みました。
別の例
盤面がこのようになっているとします：
5 1 3 4
2 6 7 8
9 10 11 12
13 14 15 _
読み順：5、1、3、4、2、6、7、8、9、10、11、12、13、14、15。
転倒数を数えます：
- 5が1より前 → 1回（5 > 1かつ5が先）
- 5が3より前 → 1回
- 5が4より前 → 1回
- 5が2より前 → 1回
- 3が2より前 → 1回
- 4が2より前 → 1回
合計転倒数：6。
空きマスは最下段 → 1行目。
合計：6 + 1 = 7。奇数。 この盤面は解けます。
なぜこれが機能するか（簡単に）
合法なスライドはタイルを水平方向（転倒数の変化なし、空きマスの行の変化なし）か垂直方向（転倒数が奇数変化し、空きマスの行が1変化）に動かします。
いずれの場合も、転倒数＋空きマスの行の合計は最初と同じ偶奇のまま変わりません。つまりこの合計は不変量です。合法な手が変えられない性質です。
ゴール状態（1‑2‑3‑...‑15で空きマスが右下）は転倒数0、空きマスが下から1行目です。合計：1、奇数。したがって解ける任意のパズルは奇数の合計を持ちます。偶数の合計を持つパズルはゴールに到達できません。
すべてのケースを含む完全な証明は偶奇性定理のページを参照してください。
8パズル（3×3）の場合
3×3の確認はより簡単です：
- 読み順で転倒数を数えます。
- 偶数なら解けます。
- 奇数なら解けません。
3×3では空きマスの行を追跡する必要はありません。パズルの対称性によって行の依存性が消えるためです。
（5×5は3×3と同じルール。6×6は4×4と同じルール。ルールは「Nが偶数のとき空きマスの行が重要」です。）
アプリが解けないパズルを生成する場合の対処法
これは起きてはならないことです。きちんと書かれたアプリは次の2つの方法のどちらかで回避します：
ゴールから逆向きに歩いて生成する。 ゴール状態から始め、ランダムな有効手を適用し、その結果の状態を開始位置として使います。この方法で生成されたすべての位置は、構造上解けることが保証されます。
ランダム生成してから偶奇チェックする。 タイルを均等にランダムシャッフルし、偶奇チェックを計算し、偶数なら任意の2枚を入れ替えて修正します。結果の位置は解けることが保証されます。
アプリで解けないパズルが出たら、そのアプリはバグっています。バグを報告してアプリを変えましょう。Slide Puzzleはゴールから逆向きに歩く生成方法を使っており、解けない開始位置を生成することはできません。
物理的なパズルが解けないと思ったら
2つのことをしてください：
- チェックを実行する。転倒数＋空きマスの行。偶数なら、物理的なピースが誤って組み立てられています。タイルを1枚外して隣のタイルと入れ替えれば解けます。
- 入れ替えた後でもパズルが解けないなら — 原因はパズルではなく戦略です。
偶奇チェックは約30秒で完了します。行き詰まったボードにさらに1時間費やす前に実行する価値は十分にあります。