1880年、アメリカのパズル制作者サム・ロイドは、特定の15パズルを解いた人に1000ドルの賞金を宣言した。標準的な1〜15の並びで14と15が入れ替わった配置だ。パズルブームがすでにアメリカとヨーロッパを席巻していた中、ロイドの賞金は火に油を注いだ。何千人もが挑戦した。誰も勝てなかった。
誰も勝てなかった理由がある。ロイドの盤面は数学的に解けないことが証明されており、その証明は1ページに収まるほど簡単だ。この記事はその1ページだ。
主張
4×4の盤面に15枚のタイルと空きマスを配置する方法は全部で16!/2 ≈ 10兆4,610億通りある（偶奇性ルールにより全16!の半分）。そのうち標準ゴールに解ける配置はちょうど半分だ。残り半分は解けない。ロイドの「14と15が入れ替わった」配置は解けない半分に属する。
これは一般化できる。あらゆるN×Nスライドパズルで、全配置の半分が解けない。3×3の8パズルでは全362,880通りのうち解ける盤面は9!/2 = 181,440通り；24パズル、35パズルなども同じルールに従う。
転倒数
証明には1つの定義が必要だ。タイルを読み取り順に並べる。左から右へ第1行、次に第2行、第3行、第4行の順で読み、空きマスは無視する。15個の数列が得られる。
転倒とは、数列中でaがbより前に来るが a > b であるような組(a, b)のことだ。数列全体でそのような組を全部数えた数が転倒数だ。
例：ゴール状態の1,2,3,…,15は転倒数がゼロ。ロイドの「14と15が入れ替わった」配置は数列が1,2,3,…,13,15,14となり、転倒は(15,14)の1組だけだ。
重要な補題：スライドがパリティを制御された方法で変える
合法的な手を行うと転倒数はどう変わるか？
-
水平スライド（タイルが1マス左右に移動）：移動したタイルは読み取り順数列での位置が1つずれる。数列中の他のすべてのタイルとの相対順序は変わらない。水平移動は行内での位置変化も行またぎもないからだ。転倒数は変わらない。
-
垂直スライド（タイルが1マス上下に移動）：移動したタイルは読み取り順数列中で3つの他のタイルを跳び越す。離れる行または入る行にある3枚のタイルだ。それぞれが「後」から「前」または逆に変わり、各タイルが転倒数に+1または-1を加える。3つの±1の合計は常に奇数だ。したがって転倒数は奇数だけ変わる。
まとめると：水平スライドは転倒数の偶奇性（偶数か奇数か）を保つ。垂直スライドはそれを反転させる。
垂直スライドでは空きマスの行も反転する
空きマスの行を上から数えて追跡する。水平スライドは空きマスを同じ行に留める。垂直スライドは1行上または下に移動するので、空きマスの行の偶奇性が変わる（偶数行↔奇数行）。
これで、同時に変化する2つのものが得られた：
- 転倒数の偶奇性が反転 ⟺ 垂直スライド
- 空きマスの行の偶奇性が反転 ⟺ 垂直スライド
したがって、その和はすべての合法的なスライドで不変だ。保存量が見つかった。
パリティ定理
不変量を次のように定義する：
P = (転倒数) + (空きマスの行番号、下から数えて1始まり)
これが保存量だ。すべての合法的なスライドで P は偶数だけ変わるため、その偶奇性（偶数か奇数か）は変わらない。
ゴール状態は転倒数がゼロで、空きマスは下から1行目にある。なので P = 1（奇数）。P が偶数の盤面はゴールから到達不可能で、逆にゴールもそのような盤面からは到達不可能だ。
これで15パズルの解ける判定が得られる：
- 空きマスを無視してタイルを行順に読む。
- 転倒数を数える。
- 空きマスの行を下から数える（1、2、3、または4）。
- 合計する。和が奇数なら解ける。偶数なら解けない。
ロイドの「14と15が入れ替わった」配置は転倒数が1、空きマスが下から1行目で、合計2（偶数）。解けない。
他のサイズでの見方
N×Nのパリティルールは、Nが偶数か奇数かによって異なる。一般的な記述：
- N奇数（3×3、5×5、…）：転倒数が偶数なら解ける。空きマスの行は関係ない。対称性により空きマスの行の偶奇性は転倒数の偶奇性によって決まるためだ。
- N偶数（4×4、6×6、…）：(転倒数) + (下からの空きマスの行番号) が奇数なら解ける。
3×3では判定は「転倒数が偶数か？」だけだ。4×4版より簡単で、1分で覚えられる。
便利な帰結
全配置のちょうど半分が解けるので、パリティ判定をした後のランダムシャッフルは、解こうとした後のランダムシャッフルより速い。解ける出発状態を保証する必要があるアプリは：
- パリティテストで事前スクリーニングし、失敗したら再シャッフルする。
- ゴールから後ろに歩く方法で生成する。ランダムな合法的スライドを適用することで、構成上の解ける保証が得られる。ほとんどのアプリがこの方法を採用しており、私たちのアプリも同様だ。
どう試しても解けないスライドパズルに出会ったら、それはアプリの生成が悪かったのだ。あなたのせいでも、宇宙のせいでもない。
サム・ロイドの余談
ロイドの1000ドルの賞金は、パズル史上で最もよく記録された実践的なジョークの1つだ。解けないことを独立に証明した数学者はWilliam JohnsonとWilliam Story（1879年、American Journal of Mathematics）、またはロイド自身だという説もあるが、誰の話を信じるかによる。ロイドは自分が発明していないものをいくつも発明したと主張したことで有名な自己宣伝の達人だ。15パズル自体は1874年にNoyes Chapmanが発明しており、ロイドの賞金より6年前だ。
ロイドが実際に貢献したのは賞金と宣伝、そして解けない変形問題だった。宣伝した内容ではないが、有用な貢献ではあった。