はじめに少し記号と用語を導入する。
a,b,cをb,c,aと並び替えるような置換を3次の巡回置換といって(a b c)と表す。
またaとbを入れ替えるような互換を(a b)と表す。（互換は2次の巡回置換でもある）
また3次の巡回置換は偶置換になっている。実際(a b c)=(b c)(a b)となっているからである。
参考図
さて、偶置換によって並び替えた、n× nの15パズル（正確にはn^2-1パズルというべきか）を考える。
そして、まず1列目と1行目にあたる部分（つまり正方形の左の辺と上の辺）の部分を全部埋める。
これは辺の長さが3以上あればあるパターンによって可能である。これについては後で説明する。
すると1行目と1列目を除いた部分のn-1 × n-1の正方形部分で考えればよい。参考図
そしてこれを繰り返すことで2× 2 の正方形部分の問題に帰着される。
そして空マスを正方形の右下の角（つまり空マスの初期位置）に戻すと、
これはやはりはじめの偶置換の配置から、さらに偶置換を行ったものである。
つまり偶置換と偶置換の合成は偶置換（互換が偶数個のものと偶数個のものを合わせても偶数個）であり、
さらに、他の部分は、元の位置に戻っているので2× 2の部分に制限して考えても偶置換の配置となっている。
空マスは右下の角と決まっているので、残り3マスの位置関係を考えればよい。
3マスの並び替えの数は高校数学とかでもやったと思うけど3!、つまり6通り。
そのうち偶置換の配置は3通りとなる。
・id（恒等置換。つまり、もうすでにパズルが完成してしまっている場合）
・(1 2 3),(1 3 2)
idの場合はパズルが完成してしまっているのでOK 。
実はこの3マスは空マスを移動させることで配置を循環させることが出来る。
つまり(1 2 3),(1 3 2)の場合も出来ることになる。
これにより偶置換がスライド置換であることが示される。
（おまけ）ちなみに上の3マスの並び替えで奇置換の場合は(1 2),(2 3),(3 1)の3つである。
さて残った"辺の長さが3以上の時の、正方形の左辺と上辺を敷き詰める方法"を説明しよう。
まず上の辺を考え、左から敷き詰めていくとする。
敷き詰めたものを動かさないようにすると、最後の1マスが埋められない場合があることに気づくだろう。
つまり最後の2マスは同時に敷き詰めるを考えないといけない。参考図
ここからは図を使わないと説明がしにくいので紙に書いてみた。文章にしたほうが厳密に言えるかもしれないが
長くなって読みにくい上に、こちらとしても書くのがしんどい。
参考図
参考図
上の参考図で書き忘れたことだが、、
ABと並べたあと空マスがABの下にある場合も考えられるが、これも簡単に上の場合に帰着できる。
参考図
このように正方形の辺の長さが3マス以上の場合、正方形の上の辺は敷き詰めることができる。
左の辺も同様にして敷き詰めることができる。
