スライドパズル（15パズル・15ゲーム）
スライドパズル（15パズル）
スライドパズル（15パズル）の遊び方
・箱の中には1～15の番号の書かれた15枚のチップが入っています。
・空欄の上下左右にあるチップをクリック（タッチ）すると、そのチップは空欄へとスライドされます。
・この15枚のチップを左上から順に1、2、3、…、15と並ぶようにできればクリアです。
・以下の基本形（完成形）を目指してください。
・リセットを押すとシャッフルされ、新たなゲームが始まります。
完成する15パズルと完成しない15パズル
スライドパズルの1～15をランダムに配置した場合、頑張れば完成するものと、頑張っても完成しないものはちょうど半々になります。
たとえば上で遊べる15パズルは何度リセットを押しても毎回必ず完成するものが表示されるようになっています。
一方で、以下の図1のような15パズルはどんなに頑張っても完成することはありません。
ではどういう配置だと完成して、どういう配置だと絶対に完成しないのでしょうか。
実は15パズルでは、15個の小チップのうちの２つ（離れていてもかまわない）を基本形（完成形）から偶数回交換したものであれば必ず完成し、奇数回交換したものであれば絶対に完成しません。（※交換する２つはその都度自由に選べます。）
ここではその数学的な理論を紹介します。
まず、わかりやすいように場所に番号を付けます。
「場所1」と書いたら基本形（完成形）の1の場所。「場所2」と書いたら基本形の2の場所とし、……以下同様に定めて、「場所16」と書いた場合は基本形の空白の場所を意味することとします。（※この「場所〇〇」という表現はこのページで何度も出てきます。）
次に、４×４のマスに16枚の小チップがあると考えます。15枚の番号が書かれた小チップと、1枚の番号の書かれていない白い小チップが存在するものとします。
これによって、「番号の書かれた小チップを空いてる場所にスライドさせること（15パズルの1回の操作）」は、「番号の書かれた小チップと白い小チップを交換すること」と考えられます。
以下では、この「小チップ同士の交換」のことを「互換」と表現します。
たとえば、図2からゲームを開始するとき、開始直後に9の付いた小チップを下に動かすことは、場所12上の小チップと場所16上の小チップの互換を行ったことになります。この操作のことを互換( 12 16 )と表記します。
次に8の付いた小チップを右に動かすことは、場所11上の小チップと場所12上の小チップの互換を行ったことになります。それら2つの操作を合わせると、場所16上の小チップを場所11に、場所11上の小チップを場所12に、場所12上の小チップを場所16に移すことになり、それは互換( 12 16 )と互換 ( 11 12 )の合成
を行ったことと一致します。なお数学の記法として、合成に関しては右の( 12 16 )を行ってから左の( 11 12 )を行うように、右から行います。
ゲームの開始時から終了時まで、毎回の操作で空白は上下左右に1コマずつ動きますが、空白が上に動いたのべ回数を\(a\)、下に動いたのべ回数を\(b\)、左に動いたのべ回数を\(c\)、右に動いたのべ回数を\(d\)とすると、空白は終了時には開始時と同じ場所16に戻って来ることから、
が成り立つことになります。したがって、操作回数の合計は
となります。
上式右辺は偶数であることに注目すると、各回の操作に対応する場所どうしの互換は、ゲームの開始から終了までちょうど偶数個になります。以上から、15パズルの場所の集合を
とすると、開始時から終了時を見た\(S\)上の置換（文字の置き換え）は偶置換（偶数回の互換となる置換）に限ります。すなわち、完成するパズルでは、開始時から終了時を見た\(S\)上の置換は偶置換でなければなりません。もちろん現段階では、その逆（偶置換であれば完成するかどうか）に関しては何も分かっていません。
なお偶置換が奇置換（奇数回の互換となる置換）になったり、奇置換が偶置換になったりすることはありません。（拙著『群論入門』『置換群から学ぶ組合せ構造』に平易な証明を掲載）
例1
図2から（基本形の）図1を見た\(S\)上の置換\(f\)は
です。（上段の各数字は真下の数字に移すとみなします。）
実際、4の場所にある5の付いた小チップは5の場所に移し、5の場所にある7の付いた小チップは7の場所に移し、7の場所にある10の付いた小チップは10の場所に移し、…、以下同様。
\(f\)が偶置換であるか奇置換であるかを調べるために、\(f\)と同じ作用をするように線を引いて、その交点の個数が偶数であるか奇数であるかを調べてみましょう。図3のように、上段の各数字から真下の数字に、合計16本の線を引きます。なお同一の交点では、3本以上の線が交わらないようにします。
図3において交点の個数は12個なので、\(f\)は偶置換となります。ここで、交点は互換を意味することに注意します。
例2
次の図4から図1を見た\(S\)上の置換\(g\)は
です。例1と同様にして、\(g\)と同じ作用をするあみだくじを作るとして、その横線の本数を調べてみましょう（図5参照）。なお同一の交点では、3本以上の線が交わらないようにします。
図5において交点の個数は21個なので、\(g\)は奇置換です。それゆえ、図4は完成しないパズルです。
15パズルでは、15個の小チップのうちの２つ（離れていてもかまわない）を基本形（完成形）から（その都度2つ選んで）偶数回交換したものであれば必ず完成し、奇数回交換したものであれば絶対に完成しません。
そのことを「定理」として書くと、以下のようになります。
15パズルにおいて、開始時から終了時を見た\(S\)上の置換\(f\)が偶置換であることは、パズルが完成するための必要十分条件である。
ではこの定理を証明していきましょう。
定理には「必要十分条件」と書かれていますが、すでに上で「\(f\)が偶置換であることの必要性」は説明しました。
そのため、定理を証明するためには、「\(f\)が偶置換ならばパズルは完成すること」、すなわち「十分性」を示せばよいのです。
まず、基本形を上の図6に変形することは容易であるから、
という置換は（ゲームの移動として）実現可能です。なお、( 11 15 12 ) は場所11（基本形で11の場所）上の小チップを場所15へ、場所15上の小チップを場所12へ、場所12上の小チップを場所11へ移す置換のことです。
以下、置換が「実現可能」というときには、そのように右下が空白の状態から右下が空白の状態を見た場合での移動についてとします。そして、今後示していきたいことは、16を16に移す\(S\)上の偶置換はすべて「実現可能」になることです。それがいえれば、定理の十分性も示せたことになります。
それを示すためには、ここから2通りの方法があります。一つは置換群という世界の性質を使う方法で、もう一つは置換群の性質を使わない素朴な方法です。前者は拙著「置換群から学ぶ組合せ構造」（日本評論社）に載せてあります。後者は拙著「群論入門」（講談社ブルーバックス）に載せてあります。以下、後者の概略を述べましょう。
まず、次の補題を用意します。なお、「長さ3の巡回置換」とは、前出の ( 11 15 12 ) のように３つの場所を回る置換のことです。
補題
\(n\geq3\)のとき、\(\Omega=\left\{1,2,3,\cdots,n\right\}\)上の任意の偶置換は長さ3の巡回置換の合成として表せる。
補題の証明
任意の2つの互換の合成は長さ3の巡回置換の合成として表せることを示せばよいのです。そして、2つの互換の合成に注目すると、次の3つの型のどれかになります。
（ア） \(（ \alpha \beta ) ∘ ( \alpha \beta ) \) （\(\alpha、\beta\)は異なる\(\Omega\)の元)
（イ） \(（ \alpha \beta ) ∘ ( \beta \gamma ) \) （\(\alpha、\beta、\gamma\)は互いに異なる\(\Omega\)の元)
（ウ） \(（ \alpha \beta ) ∘ ( \gamma \delta ) \) （\(\alpha、\beta、\gamma、\delta\)は互いに異なる\(\Omega\)の元)
（ア）の型の置換は（すべての文字を動かさない）恒等置換\(e\)であり、\(e\)は
というように、2つの長さ3の巡回置換の合成として表せます。
（イ）の型の置換はそれ自身
というように、1つの長さ3の巡回置換になります。
（ウ）の型の置換は
というように、2つの長さ3の巡回置換の合成として表せます。
――（補題の証明終り）――
定理の証明に戻ると、集合
上のすべての偶置換は「実現可能」になることを示せばよいのです。そのためには補題を利用して、\(T\)の相異なる任意の3つの元\(a、b、c\)に対し、長さ3の巡回置換
は「実現可能」であることを示せばよいのです。
以下、少し直観的に述べます（厳格で丁寧な証明は拙著『群論入門（講談社ブルーバックス）』を参照）。いくつかの操作を重ねて\(a\)の場所上の小チップを11の場所、\(b\)の場所上の小チップを15の場所、\(c\)の場所上の小チップを12の場所、それぞれに動かす移動\(\phi\)があります。この\(\phi\)の移動を行って、続けて図16で示した ( 11 15 12 )に相当する移動を行います。さらに続けて、移動\(\phi\)の作業を完全に逆にした移動\(\phi^{-1}\)を行います。
この3つの移動によって、長さ3の巡回置換\( (a b c ) \)は「実現可能」であることが示されたのです。
――（定理の証明の概略終り）――