１．たった２ピース入れ替えただけなのに……
サム・ロイドは、19世紀から 20世紀にかけて活躍したアメリカのパズル作家です。
『消える小人（インディアン）』や『子馬のパズル』などパズルの大家として知られ、同時代に活躍したパズル作家ヘンリー・アーネスト・デュードニー（イギリスのパズル作家）とともに双璧をなす人物です。
『15パズル』はサム・ロイドの代表的なパズルと言えますね。
15パズルの完成形、もちろん皆さんご存じですね。
そう。４×４の空間に15個のピースが順番に並んでいる、あの形です。
今、その 14と15 をちょいと入れ替えてみましょう。
図1-1 の形です。
ここで、こんな問題を考えてみる。
この形から15パズルを完成できるかな……？
このパズル問題は『14-15パズル』と呼ばれています。
1870年代にサム・ロイドが発表した懸賞問題で、賞金が 1,000ドル（当時）だったおかげか当時は15パズルが大ヒットしたそうです。
しかし、不思議なことに賞金を獲得した人は誰一人いませんでした。
ホントに不思議ですね。１人くらい居そうなものですが。
でも、実は不思議でも何でもなかったんです。
なぜなら、この問題は不可能だからです。
ピース２枚入れ替えただけの問題。だが、絶対に完成にたどりつけない。
それは一体なぜなのか？
その話をしようと思います。
数学の視点で15パズルに触れ、『14-15パズル』がなぜ不可能なのかを証明してみます。
２．置換とは何ぞや？
数学の視点で……とは言ったものの、どう見ればいいんでしょう？
まず、「15パズルが完成する」をどう捉えればいいのか。
図2-1 を例にとりましょう。
ここから完成図を得るとはどういうことか？
これは、次の 16個を行うことと同じなんです。
- ピース７ を ピース１ に置き換える。
- ピース15 を ピース２ に置き換える。
- 空白スペース を ピース３ に置き換える。
- ピース４ を ピース４ に置き換える。
…… - ピース10 を ピース15 に置き換える。
- ピース５ を 空白スペース に置き換える。
ま、要はピースをつまんで正しい位置に戻しゃぁいいってことさ！
簡単だね！
……そりゃそうだとしか言えんわ😅
ルールどこ行った😅
まぁピースつまむ云々は冗談だけど、上述の置き換え行為は15パズルの本質だと言えます。
上述の16個をすべて達成すればゴールですもんね。「ピースを上下左右にスライドさせる」はルール上の手段に過ぎません。
そう考えると、「置き換え」という視点で考察するのが良さそうだ。
じゃぁ、その視点で迫ってみましょう。
……と、その前に注意を１つ。
以降、空白スペースを「16番ピース」と呼ぶことにします。
ピースと同じ扱いをすることで、先述の置き換え行為は「単なる番号の置き換え」と単純化できます。
では、本題に入りましょう。
番号置き換えを論理的に考えるため、数学の「置換」という概念を利用してみます。
まずはその「置換」のご紹介。
先述した 16個の置き換え行為、数学では次の式Ｓで表します。
このＳを 置換 と呼びます。
この式は「上段の番号を下段の番号にそれぞれ置き換えるよ〜！」ということを表しています。
７を１に置き換える、15を２に置き換える、etc...
上記の式はあくまで上下の番号対応を列挙しているだけなので、上段「7 15 16 ……」の並び順に意味はありません。
並べ替えて次のように書いても意味は同じです。
この式Ｓを見ると、４や６などいくつかの番号は変化していません。
動かない番号を考えてもしかたがないので、それらは除去しちゃいましょう。
ちょっとスリムになりました😊
図2-1 の盤面に置換Ｓを施すと、15パズルは完成します。
次セクションでは、この置換Ｓをさらに掘り下げてみましょう。
３．置換は回って分解される
前セクションでは、置換を紹介しました。
当セクションからはその置換の性質に迫ってみましょう。
まず、置換には大きな特徴があります。
置換Ｓの番号 2, 8, 10, 15 を見てみましょう。
あれ？
なんか……グルッと一周してない？
２は８に変わり、８は10に、10は15に。そして、15は２に変わる。
あら〜、置換が一回りしとるわ。
そうなんです。
４つの番号 2, 8, 10, 15 はワンセットでローテーションしてるんですね。
実は、置換の内部にはローテーションをなすミニ置換が存在するんです。
これを 巡回置換 と呼びます。
また、この巡回置換は番号が４種類あるので、長さ４の巡回置換 と言います。
置換Ｓには他にも巡回置換が存在しています。
(1, 13, 7) と (3, 11, 5, 16) の２つ。
巡回置換は全部で３つあるわけですね。
巡回置換 (2, 8, 10, 15) はそれ自身で置換が完結していて、他の巡回置換に干渉しません。
(1, 13, 7) も (3, 11, 5, 16) も同様です。
だから、３つとも独立した置換と捉えることができる。
言い換えると、置換Ｓは３つの巡回置換に分解することができるんです。
巡回置換はわざわざ２行で書く必要はありません。
「右隣の番号に置換する」と解釈すればＯＫですもんね（右端の番号は左端の番号に置換すると解釈）。
式を簡略化しちゃいましょう！
ちなみに。
前セクション 図2-1 の盤面に対して巡回置換は何をもたらすんでしょう？
例えば、巡回置換 (1, 13, 7) は盤面にどう作用するのか？
これは、次の３つを行うことと同じです。
- ピース１ を ピース13 に置き換える。
- ピース13 を ピース７ に置き換える。
- ピース７ を ピース１ に置き換える。
つまり、図3-1 のようにピースを移動させるということです。
おぉ、盤面でもローテーションしとる！
盤面でも「巡回」するんですね。
他の巡回置換 (2, 8, 10, 15), (3, 11, 5, 16) も同じです。
ヒマな時にでも試してみてください。
さて、置換は巡回置換に分解できたわけですが、実は巡回置換も分解できます。
そして分解後のミニミニ置換が『14-15パズル』の証明に必要なものです。
次セクションでは、そのミニミニ置換の話をしましょう。
４．置換よ、もっと細かくな〜れ
ところで。
いきなりですが、最も小さい巡回置換は何でしょう？
最小の巡回置換は「番号２つの巡回置換」です。長さ２の巡回置換。
例えば「番号１を２に置き換え、番号２を１に置き換える」ですね。
これを 互換 と呼びます。
互換は巡回置換の一種です。
だから、巡回置換を (2, 8, 10, 15) と書いたように互換も (1, 2) と書くことができます。
さて、この互換ですが、実は巡回置換との間に関係があるんです。
それは次の定理です。
- すべての巡回置換は互換の組み合わせで表現できる。
巡回置換 (2, 8, 10, 15) で具体的にやってみましょう。
Ａ＝(2, 8, 10, 15) としておきます。
４つの番号 2, 8, 10, 15 に次の手順を順番に施してみます。
- 番号２と８を交換する。
- 番号２と10を交換する。
- 番号２と15を交換する。
結果は 図4-1 の通り。
なんと、Ａを直接施したのと同じ結果になっとる！
巡回置換Ａは３個の互換で代用できるんですね。
式で書くと Ａ＝(2, 15)(2, 10)(2, 8) となります。
こうして、巡回置換Ａは３個の互換で表現できました。
残りの巡回置換も同様です。
巡回置換Ｂ＝(1, 13, 7) は互換２個 (1, 13), (1, 7) で代用できます。
そして、Ｂ＝(1, 7)(1, 13) と表現できます。
巡回置換Ｃ＝(3, 11, 5, 16) も互換３個で Ｃ＝(3, 16)(3, 5)(3, 11) です。
巡回置換Ａ, Ｂ, Ｃの互換表現を見ると明らかですが、次セクションで使うのでこれも述べておきます。
- 長さｎの巡回置換は (n−1) 個の互換で表現できる。
巡回置換は互換だけで表現できることがわかりました。
そうなると、ひとつ大きな事実が判明する。
置換Ｓ自身も互換だけで表現できるようになるんです！
置換Ｓは互換８個で表現できました。
図2-1 の盤面から置換Ｓで完成できるはずだけど、この互換８個で本当に完成するんだろうか？
ちょいと試しにやってみましょう。
次の手順を順番に施してみます。
- ピース３ と ピース11 を交換する。
- ピース３ と ピース５ を交換する。
- ピース３ と 空きスペース を交換する。
- ピース２ と ピース８ を交換する。
- ピース２ と ピース10 を交換する。
- ピース２ と ピース15 を交換する。
- ピース１ と ピース13 を交換する。
- ピース１ と ピース７ を交換する。
結果は 図4-2 の通り。
ちゃんと 15パズルが完成するんですね。
置換は巡回置換に分解でき、巡回置換は互換に分解できる。
というわけで、すべての置換は互換の組み合わせで表現できるようになりました。
この後は互換を中心に話が進み、最終的に『14-15パズル』の不可能性も証明できるようになっていくわけです。
ところが！
ここで残念な話をしなければなりません……😞
互換表現に関して困ったことが１つ生まれてしまう。
それは次セクションにて。
５．奇置換と偶置換
残念な話をぶっちゃけます。
実は……、
互換による表現は１通りではありません。
例えば、図5-1 のように互換５つを施してみる。
すると……これも同じ結果になっちゃうんです。
巡回置換Ａ＝(2, 8, 10, 15) は互換５個で代用することも可能であり、そのため、Ａ＝(2, 15)(10, 15)(8, 10)(2, 10)(8, 15) とも表現できてしまう。
互換表現は一意ではなかったんですね。
前セクションで示した式はほんの一例に過ぎなかった。
互換の個数すら８個と決まったわけではなかった。
確実にわかったのは「単に置換Ｓは互換で表せる」ということだけだった。
前セクションで長々と話した割には、成果は大したことなかったわけです。
悲しいなぁ😞
しかし。
そんな悲しみの中にも一筋の光明があった。
実は、互換の個数について面白い法則があるんです。
巡回置換Ａ＝(2, 8, 10, 15) は必ず奇数個の互換で表現される。
巡回置換Ａは必ずしも互換３個だとは限らないが、どのような表現をしても互換は必ず奇数個になる。
これが成り立つというのです。
そういえば前セクションでは３個、図5-1 では５個だった。
両方とも奇数個だったけど、これは偶然ではなかったということか。
巡回置換を互換で表した時、互換の個数は表現によってさまざまです。
しかし、互換が奇数個であるか偶数個であるかは必ず決まるんです。
証明はこのページに示してあります。
そして、前セクションで「長さｎの巡回置換は (n−1) 個の互換で表現できる」と述べました。
これを基にして次の２つが成り立つんです。
- 長さ奇数の巡回置換は、必ず偶数個の互換で表現される。
- 長さ偶数の巡回置換は、必ず奇数個の互換で表現される。
巡回置換 (2, 8, 10, 15) は必ず奇数個の互換で表現される。
巡回置換 (1, 13, 7) は必ず偶数個の互換で表現される。
巡回置換 (3, 11, 5, 16) は必ず奇数個の互換で表現される。
ここまでわかると、互換の個数について何か見えてきそうだ。
あらためて置換Ｓを見てみましょうか。
置換Ｓは必ず偶数個の互換で表現される。
これが判明したのです！
互換表現について大事な定理を紹介します。
次が成り立ちます。
- すべての置換は互換で表現できるが、その表し方は一意ではない。
しかし、互換の個数が奇数であるか偶数であるかは必ず決まる。
では、最後の定義をしましょう。
ある置換Ｔが互換で表現されたとする。
もし互換の個数が奇数だった時、Ｔを 奇置換 と呼びます。
もし互換の個数が偶数だった時、Ｔを 偶置換 と呼びます。
すべての置換は、奇置換/偶置換 のどちらかです。
奇置換でも偶置換でもある置換は１つも存在しません。
ちなみに、置換Ｓは偶置換です。
……ここまで長い道のりでした。
次はいよいよ『14-15パズル』の不可能性を証明します！
６．いよいよ不可能を証明するよ
奇置換・偶置換の定義も済ませ、準備は整いました。
さぁ、いよいよ証明します！
『14-15パズル』とは、15パズルのルールに従って 図6-1 から完成図を作るという問題でした。
これが不可能だということを背理法で証明していきます。
引き続き、空きスペースは 16番ピースだと解釈することにします。
では、『14-15パズル』は可能だと仮定しましょう。
そして、図6-1 から完成へと導ける置換をＰとしておきます。
果たしてＰは奇置換なのか偶置換なのか？ これを調べましょう。
まず、Ｐは簡単にわかります。
Ｐ＝(14, 15) です。
ピース 14と15 を交換すれば完成できますもんね。
Ｐは互換１個の置換だから、こうなります。
- 置換Ｐは奇置換である。
あら、もう奇置換だとわかっちゃったよ😅
早ぇな😅
でも、もしこれで「Ｐは偶置換でもある」なんて判明した日にゃぁ……なんてね。
さてどうだろうか。
次は視点を変えて、ルールに沿って話をしましょう。
15パズルでは「ピースを空きスペースにスライドする」という操作をしますよね。
これは、見方を変えると「空きスペースも上下左右にスライドする」と言えます。
なぜなら、ピースと空きスペースが入れ替わるからです。ピースとは逆方向に空きスペースがスライドするということです。
ということは、「１手進むたびに 16番ピースは上下左右に１マス動く」とも言えるわけですね。
ここで、４×４の盤面を市松模様にしてみましょう。
そして、16番ピースを右下隅に置く（図6-2）。
ルールに従って 図6-1 から15パズルが完成する場合、この16番ピースは盤面を上下左右にカクカク移動して再び右下隅に戻ってきます。
この時、16番ピースは何回動くことになるんでしょう？
それを考えてみます。
現在、16番ピースは白マスの上にある。
上下左右どの方向でもいいので、盤面の外に出ないようにタテヨコに１マスずつ動かしてみる。
まず１手目。
黒マスに移動した。
２手目。
今度は白マスに移動した。
３手目。
黒マスに移動した。
４手目。
白マスに移動した。
……もう法則は見えたかもしれませんね。
そうです。
奇数回移動したら 16番ピースは黒マスの上にある。そして、偶数回移動したら白マスの上にある。
これが成り立つんですね。
ということは、図6-1 からの完成時に16番ピースの動いた回数もわかる。
そう。偶数回動いたことになるのです。
16番ピースが１マス動くということは、16番に隣接しているｎ番ピースと位置交換をするということです（ｎは番号１～15のどれか）。
つまり、互換 (ｎ, 16) を施すのと同じ。
16番ピースが偶数回動いて完成するのだから、置換Ｐはこういう表現もできますね。
よって、こうなるんです。
- 置換Ｐは偶置換である。
……あっ！
マズいことが起きてもぅた……。
そう。
Ｐは奇置換でもあり偶置換でもある、ということになってしまった😵
矛盾が起きてしまったのです。
というわけで、遡って「『14-15パズル』は可能だ」という仮定は間違いだと結論づけなければならない。
『14-15パズル』は不可能だ、ということになるのです。
更新履歴
- 2022. 4. 8.
- 新規公開。
- 2022. 4.10.
- セクション３を加筆。
巡回置換とピースの関係を説明。 - セクション４を加筆。
互換により15パズルが完成することを説明。
- セクション３を加筆。