置換で見る『14-15パズル』の不思議

 『15パズル』はみなさんご存じのパズルですね。
 500円くらいのオモチャとしても売られている、定番パズルです。
 このパズルに関して有名な問題があります。
 それを数学的な視点で考察してみました。

1.たった2ピース入れ替えただけなのに……

 サム・ロイドは、19世紀から 20世紀にかけて活躍したアメリカのパズル作家です。
 『消える小人(インディアン)』や『子馬のパズル』などパズルの大家として知られ、同時代に活躍したパズル作家ヘンリー・アーネスト・デュードニー(イギリスのパズル作家)とともに双璧をなす人物です。
 『15パズル』はサム・ロイドの代表的なパズルと言えますね。

図 1-1

 15パズルの完成形、もちろん皆さんご存じですね。
 そう。4×4の空間に15個のピースが順番に並んでいる、あの形です。

 今、その 14と15 をちょいと入れ替えてみましょう。
 図1-1 の形です。
 ここで、こんな問題を考えてみる。

この形から15パズルを完成できるかな……?

 このパズル問題は『14-15パズル』と呼ばれています。
 1870年代にサム・ロイドが発表した懸賞問題で、賞金が 1,000ドル(当時)だったおかげか当時は15パズルが大ヒットしたそうです。
 しかし、不思議なことに賞金を獲得した人は誰一人いませんでした。

 ホントに不思議ですね。1人くらい居そうなものですが。
 でも、実は不思議でも何でもなかったんです。
 なぜなら、この問題は不可能だからです。

 ピース2枚入れ替えただけの問題。だが、絶対に完成にたどりつけない。
 それは一体なぜなのか?
 その話をしようと思います。
 数学の視点で15パズルに触れ、『14-15パズル』がなぜ不可能なのかを証明してみます。

2.置換とは何ぞや?

 数学の視点で……とは言ったものの、どう見ればいいんでしょう?
 まず、「15パズルが完成する」をどう捉えればいいのか。

図 2-1

 図2-1 を例にとりましょう。
 ここから完成図を得るとはどういうことか?
 これは、次の 16個を行うことと同じなんです。

  • ピース7 を ピース1 に置き換える。
  • ピース15 を ピース2 に置き換える。
  • 空白スペース を ピース3 に置き換える。
  • ピース4 を ピース4 に置き換える。
     ……
  • ピース10 を ピース15 に置き換える。
  • ピース5 を 空白スペース に置き換える。

 ま、要はピースをつまんで正しい位置に戻しゃぁいいってことさ!
 簡単だね!

 ……そりゃそうだとしか言えんわ😅
 ルールどこ行った😅

 まぁピースつまむ云々は冗談だけど、上述の置き換え行為は15パズルの本質だと言えます。
 上述の16個をすべて達成すればゴールですもんね。「ピースを上下左右にスライドさせる」はルール上の手段に過ぎません。
 そう考えると、「置き換え」という視点で考察するのが良さそうだ。
 じゃぁ、その視点で迫ってみましょう。

 ……と、その前に注意を1つ。
 以降、空白スペースを「16番ピース」と呼ぶことにします。
 ピースと同じ扱いをすることで、先述の置き換え行為は「単なる番号の置き換え」と単純化できます。

 では、本題に入りましょう。
 番号置き換えを論理的に考えるため、数学の「置換」という概念を利用してみます。
 まずはその「置換」のご紹介。
 先述した 16個の置き換え行為、数学では次の式Sで表します。
 このSを 置換 と呼びます。

 この式は「上段の番号を下段の番号にそれぞれ置き換えるよ〜!」ということを表しています。
 7を1に置き換える、15を2に置き換える、etc...
 上記の式はあくまで上下の番号対応を列挙しているだけなので、上段「7 15 16 ……」の並び順に意味はありません。
 並べ替えて次のように書いても意味は同じです。

 この式Sを見ると、4や6などいくつかの番号は変化していません。
 動かない番号を考えてもしかたがないので、それらは除去しちゃいましょう。
 ちょっとスリムになりました😊

 図2-1 の盤面に置換Sを施すと、15パズルは完成します。
 次セクションでは、この置換Sをさらに掘り下げてみましょう。

3.置換は回って分解される

 前セクションでは、置換を紹介しました。
 当セクションからはその置換の性質に迫ってみましょう。

 まず、置換には大きな特徴があります。
 置換Sの番号 2, 8, 10, 15 を見てみましょう。

 あれ?
 なんか……グルッと一周してない?
 2は8に変わり、8は10に、10は15に。そして、15は2に変わる。
 あら〜、置換が一回りしとるわ。

 そうなんです。
 4つの番号 2, 8, 10, 15 はワンセットでローテーションしてるんですね。
 実は、置換の内部にはローテーションをなすミニ置換が存在するんです。
 これを 巡回置換 と呼びます。
 また、この巡回置換は番号が4種類あるので、長さ4の巡回置換 と言います。

 置換Sには他にも巡回置換が存在しています。
 (1, 13, 7) と (3, 11, 5, 16) の2つ。
 巡回置換は全部で3つあるわけですね。

 巡回置換 (2, 8, 10, 15) はそれ自身で置換が完結していて、他の巡回置換に干渉しません。
 (1, 13, 7) も (3, 11, 5, 16) も同様です。
 だから、3つとも独立した置換と捉えることができる。
 言い換えると、置換Sは3つの巡回置換に分解することができるんです。

 巡回置換はわざわざ2行で書く必要はありません。
 「右隣の番号に置換する」と解釈すればOKですもんね(右端の番号は左端の番号に置換すると解釈)。
 式を簡略化しちゃいましょう!

 ちなみに。
 前セクション 図2-1 の盤面に対して巡回置換は何をもたらすんでしょう?

図 3-1

 例えば、巡回置換 (1, 13, 7) は盤面にどう作用するのか?
 これは、次の3つを行うことと同じです。

  • ピース1 を ピース13 に置き換える。
  • ピース13 を ピース7 に置き換える。
  • ピース7 を ピース1 に置き換える。

 つまり、図3-1 のようにピースを移動させるということです。
 おぉ、盤面でもローテーションしとる!
 盤面でも「巡回」するんですね。

 他の巡回置換 (2, 8, 10, 15), (3, 11, 5, 16) も同じです。
 ヒマな時にでも試してみてください。

 さて、置換は巡回置換に分解できたわけですが、実は巡回置換も分解できます。
 そして分解後のミニミニ置換が『14-15パズル』の証明に必要なものです。
 次セクションでは、そのミニミニ置換の話をしましょう。

4.置換よ、もっと細かくな〜れ

 ところで。
 いきなりですが、最も小さい巡回置換は何でしょう?

 最小の巡回置換は「番号2つの巡回置換」です。長さ2の巡回置換。
 例えば「番号1を2に置き換え、番号2を1に置き換える」ですね。
 これを 互換 と呼びます。

 互換は巡回置換の一種です。
 だから、巡回置換を (2, 8, 10, 15) と書いたように互換も (1, 2) と書くことができます。

 さて、この互換ですが、実は巡回置換との間に関係があるんです。
 それは次の定理です。

図 4-1

 巡回置換 (2, 8, 10, 15) で具体的にやってみましょう。
 A=(2, 8, 10, 15) としておきます。
 4つの番号 2, 8, 10, 15 に次の手順を順番に施してみます。

  1. 番号2と8を交換する。
  2. 番号2と10を交換する。
  3. 番号2と15を交換する。

 結果は 図4-1 の通り。
 なんと、Aを直接施したのと同じ結果になっとる!
 巡回置換Aは3個の互換で代用できるんですね。
 式で書くと A=(2, 15)(2, 10)(2, 8) となります。

 こうして、巡回置換Aは3個の互換で表現できました。
 残りの巡回置換も同様です。
 巡回置換B=(1, 13, 7) は互換2個 (1, 13), (1, 7) で代用できます。
 そして、B=(1, 7)(1, 13) と表現できます。
 巡回置換C=(3, 11, 5, 16) も互換3個で C=(3, 16)(3, 5)(3, 11) です。

 巡回置換A, B, Cの互換表現を見ると明らかですが、次セクションで使うのでこれも述べておきます。

 巡回置換は互換だけで表現できることがわかりました。
 そうなると、ひとつ大きな事実が判明する。
 置換S自身も互換だけで表現できるようになるんです!

 置換Sは互換8個で表現できました。
 図2-1 の盤面から置換Sで完成できるはずだけど、この互換8個で本当に完成するんだろうか?
 ちょいと試しにやってみましょう。

図 4-2

 次の手順を順番に施してみます。

  1. ピース3 と ピース11 を交換する。
  2. ピース3 と ピース5 を交換する。
  3. ピース3 と 空きスペース を交換する。
  4. ピース2 と ピース8 を交換する。
  5. ピース2 と ピース10 を交換する。
  6. ピース2 と ピース15 を交換する。
  7. ピース1 と ピース13 を交換する。
  8. ピース1 と ピース7 を交換する。

 結果は 図4-2 の通り。
 ちゃんと 15パズルが完成するんですね。

 置換は巡回置換に分解でき、巡回置換は互換に分解できる。
 というわけで、すべての置換は互換の組み合わせで表現できるようになりました。
 この後は互換を中心に話が進み、最終的に『14-15パズル』の不可能性も証明できるようになっていくわけです。

 ところが!
 ここで残念な話をしなければなりません……😞
 互換表現に関して困ったことが1つ生まれてしまう。
 それは次セクションにて。

5.奇置換と偶置換

図 5-1

 残念な話をぶっちゃけます。
 実は……、

互換による表現は1通りではありません。

 例えば、図5-1 のように互換5つを施してみる。
 すると……これも同じ結果になっちゃうんです。

 巡回置換A=(2, 8, 10, 15) は互換5個で代用することも可能であり、そのため、A=(2, 15)(10, 15)(8, 10)(2, 10)(8, 15) とも表現できてしまう。
 互換表現は一意ではなかったんですね。

 前セクションで示した式はほんの一例に過ぎなかった。
 互換の個数すら8個と決まったわけではなかった。
 確実にわかったのは「単に置換Sは互換で表せる」ということだけだった。
 前セクションで長々と話した割には、成果は大したことなかったわけです。

 悲しいなぁ😞

 しかし。
 そんな悲しみの中にも一筋の光明があった。
 実は、互換の個数について面白い法則があるんです。

巡回置換A=(2, 8, 10, 15) は必ず奇数個の互換で表現される。

 巡回置換Aは必ずしも互換3個だとは限らないが、どのような表現をしても互換は必ず奇数個になる。
 これが成り立つというのです。
 そういえば前セクションでは3個、図5-1 では5個だった。
 両方とも奇数個だったけど、これは偶然ではなかったということか。

 巡回置換を互換で表した時、互換の個数は表現によってさまざまです。
 しかし、互換が奇数個であるか偶数個であるかは必ず決まるんです。
 証明はこのページに示してあります。
 そして、前セクションで「長さnの巡回置換は (n−1) 個の互換で表現できる」と述べました。
 これを基にして次の2つが成り立つんです。

 巡回置換 (2, 8, 10, 15) は必ず奇数個の互換で表現される。
 巡回置換 (1, 13, 7) は必ず偶数個の互換で表現される。
 巡回置換 (3, 11, 5, 16) は必ず奇数個の互換で表現される。

 ここまでわかると、互換の個数について何か見えてきそうだ。
 あらためて置換Sを見てみましょうか。

 置換Sは必ず偶数個の互換で表現される。
 これが判明したのです!

 互換表現について大事な定理を紹介します。
 次が成り立ちます。

 では、最後の定義をしましょう。
 ある置換Tが互換で表現されたとする。
 もし互換の個数が奇数だった時、Tを 奇置換 と呼びます。
 もし互換の個数が偶数だった時、Tを 偶置換 と呼びます。
 すべての置換は、奇置換/偶置換 のどちらかです。
 奇置換でも偶置換でもある置換は1つも存在しません。
 ちなみに、置換Sは偶置換です。

 ……ここまで長い道のりでした。
 次はいよいよ『14-15パズル』の不可能性を証明します!

6.いよいよ不可能を証明するよ

 奇置換・偶置換の定義も済ませ、準備は整いました。
 さぁ、いよいよ証明します!

図 6-1

 『14-15パズル』とは、15パズルのルールに従って 図6-1 から完成図を作るという問題でした。
 これが不可能だということを背理法で証明していきます。
 引き続き、空きスペースは 16番ピースだと解釈することにします。

 では、『14-15パズル』は可能だと仮定しましょう。
 そして、図6-1 から完成へと導ける置換をPとしておきます。
 果たしてPは奇置換なのか偶置換なのか? これを調べましょう。

 まず、Pは簡単にわかります。
 P=(14, 15) です。
 ピース 14と15 を交換すれば完成できますもんね。
 Pは互換1個の置換だから、こうなります。

  • 置換Pは奇置換である。

 あら、もう奇置換だとわかっちゃったよ😅
 早ぇな😅
 でも、もしこれで「Pは偶置換でもある」なんて判明した日にゃぁ……なんてね。
 さてどうだろうか。

 次は視点を変えて、ルールに沿って話をしましょう。
 15パズルでは「ピースを空きスペースにスライドする」という操作をしますよね。
 これは、見方を変えると「空きスペースも上下左右にスライドする」と言えます。
 なぜなら、ピースと空きスペースが入れ替わるからです。ピースとは逆方向に空きスペースがスライドするということです。
 ということは、「1手進むたびに 16番ピースは上下左右に1マス動く」とも言えるわけですね。

図 6-2

 ここで、4×4の盤面を市松模様にしてみましょう。
 そして、16番ピースを右下隅に置く(図6-2)。
 ルールに従って 図6-1 から15パズルが完成する場合、この16番ピースは盤面を上下左右にカクカク移動して再び右下隅に戻ってきます。
 この時、16番ピースは何回動くことになるんでしょう?
 それを考えてみます。

 現在、16番ピースは白マスの上にある。
 上下左右どの方向でもいいので、盤面の外に出ないようにタテヨコに1マスずつ動かしてみる。
 まず1手目。
 黒マスに移動した。
 2手目。
 今度は白マスに移動した。
 3手目。
 黒マスに移動した。
 4手目。
 白マスに移動した。
 ……もう法則は見えたかもしれませんね。

 そうです。
 奇数回移動したら 16番ピースは黒マスの上にある。そして、偶数回移動したら白マスの上にある。
 これが成り立つんですね。
 ということは、図6-1 からの完成時に16番ピースの動いた回数もわかる。
 そう。偶数回動いたことになるのです。

 16番ピースが1マス動くということは、16番に隣接しているn番ピースと位置交換をするということです(nは番号1~15のどれか)。
 つまり、互換 (n, 16) を施すのと同じ。
 16番ピースが偶数回動いて完成するのだから、置換Pはこういう表現もできますね。

 よって、こうなるんです。

 ……あっ!
 マズいことが起きてもぅた……。

 そう。
 Pは奇置換でもあり偶置換でもある、ということになってしまった😵
 矛盾が起きてしまったのです。

 というわけで、遡って「『14-15パズル』は可能だ」という仮定は間違いだと結論づけなければならない。
 『14-15パズル』は不可能だ、ということになるのです。

更新履歴