まず、１５パズルの現在の盤面を考えて、これを扱いやすい形に書き直すことを考えます（これを数学用語で表現と言います）。
一般に、１５パズルの盤面は、空マスがどの位置にあっても構いません。しかしこれでは扱いにくいので、ここんところをまずうまく書き直したいと思います。それには、空マスを常に同じ位置に置いてやればいいわけです。具体的には、空マスをいつも１５パズル完成図の時のように右下に持ってくるように考えます。
| ||||||||||||||||||||||||||||||||||||||||||||||||
| 図1.5 空白移動の取り決め |
|---|
空マスを右下に持っていったら、今度はこの１５個の数字を１列に並べることを考えます。と言っても本当に１列に並べ替える必要はなく、転倒数を数えた時と同じように、左上から始まって、その行の一番右まで行って、次の行に移ってまた右に移って、と言う要領で左上から右下までの数字を順序付けて考える、と言うことです。勿論、本当に１列に並べ替えて書き記した方が直感的で分かりやすいですね。
ここで、一つ二つ言葉を定義します。
今並べ替えたこの１５個の数字の集まりを、その時の１５パズルの盤面に対する『状態』または『現状態』と言います。
例えば図1.1 の盤面に対応する『状態』は、［４，13，８，14，３，12，６，９，５，２，11，１，７，15，10］と書き表されます。
またその時の転倒数を数えた時、それが奇数だったら、その状態は『奇置換』、偶数だったらその状態は『偶置換』と言います。
更に、１５パズルの完成図に対応する状態（１〜15が、その順番に並んでいる状態ですね）を『基本状態』と呼ぶことにしましょう（注：基本状態の転倒数は０、よって基本状態は偶置換です）。
すると、“具体的なパズル完成判定方法！”で述べた、１５パズルの大事な性質は、次のように言いかえることが出来ます：
定理１ １５パズルは、現状態が偶置換なら基本状態にすることが出来る。現状態が奇置換なら基本状態にすることが出来ない。
そして、これからこれを証明しようと言うわけです。
でも、まだまだ準備が必要です。まず、もう一つ、大事な考え方を導入しなければなりません。
先程『偶置換』『奇置換』と言う言葉を導入しましたが、そもそも『置換』というのは、数学用語で「文字の列を並べ替えること」という意味です。
つまり今考えているのは、“１”〜“15”の、１５個の『文字』なのです。そして１５パズルというのを、この１５個の文字の並べ替えパズルだと考えているわけです。
ここで『二文字置換』『三文字置換』という言葉を定義します。と言っても、これは簡単です。１５個の文字のうちの、どれか二つ（普通は記号で“ａとｂ”のように書きます）を入れ替える「並べ替え」を『二文字置換』といいます。また１５個のうちの３つの文字（ａとｂとｃ）を、その順番に（即ち、ａをｂに、ｂをｃに、ｃをａに）置き換える「並べ替え」を『三文字置換』と言います。
同様に『ｍ文字置換』と言うものを定義できます（ｍが３以上の時は、『ｍ文字巡回置換』という方が実は正しいです、また『二文字置換』は普通は『互換』と言います）。
今は説明のために「全部で１５文字」と言うことにしていますが、勿論何文字でも（一般に ｎ文字 とよく書きます）同じことが言えます。
例を挙げると、ｎ＝３として、［１，３，２］は（［１，２，３］の）『二文字置換』（記号 (23) であらわします）、［２，３，１］は（［１，２，３］の）『三文字置換』（記号 (123) であらわします）です。
ではここで、宿題です(笑)
次の事柄を示してみてください：
「二文字置換（互換）は奇置換、三文字置換は偶置換である。」
ヒントは、二文字置換の場合は具体的に「転倒数」がどう変るかと言うことを計算してみてください。また三文字置換は、実は「２つの二文字置換の合成」だと考えることが出来ます（ちょっと難しいかな(^^;）。でもその事実さえ意味が分かれば、奇置換の奇置換で偶置換になる、というわけです。
では続いて、次の補題を考えます：
補題１ 現状態が偶置換(resp. 奇置換)ならば、そこから何手か進めた１５パズルの盤面に対応する状態も偶置換(resp. 奇置換)である。
証明：１５パズルでは、一手進むごとに空マスの位置が一つずつずれる。今、空マスの位置を座標で(x,y)とあらわすとする。一つの状態に対応する、空白が右下に位置されている盤面においては、即ち空マスの位置は(x,y)=(4,4)となる。特に x+y = 4+4 は偶数である。そしてすぐに分かるように、そこから空マスの位置が一つずれる毎に、x+y は偶数と奇数が交互に現れる。そして巡りめぐって、空マスがまた右下に来た時、今までの話からそれは偶数手目であることが分かる（分かりますよね）。
ところで、「空マス」を“第１６の文字”と見て、空マスの移動を「１６個の文字の置換」に見立ててみる。すると、空マスの一回の移動は「空マスと、そこに隣り合っている数字との『二文字置換』である」と言うことが出来る。そして空マスが元の右下の位置に戻った時、今見たように偶数回の移動があったことになるのだから、この時の置換は「偶数回の『二文字置換』」だと言い表すことが出来る。
よって、現状態が偶置換(resp. 奇置換)ならば、そこから何手か進めた状態は、偶置換(resp. 奇置換)＋（偶数回の奇置換）＝偶置換(resp. 奇置換) である。 □
どうですか？ 見事でしょう(^^)
ところで、これは何を意味しているのか、と言うと。実は、［定理１］の二つの主張のうちの、後者。「現状態が奇置換なら基本状態にすることが出来ない。」をこれで示してしまったことになるのです。
こう考えてください。現状態がある奇置換の状態だったとしたら、そこから何手か進めた状態は、この補題２から必ず『奇置換』の状態にならなければならないのです。ところが先程注意したように、基本状態は『偶置換』なのです。マル。
では、後半は定理１の前者の主張を示してみたいと思います。
To be continued...