自作パズルゲームの可解性についての考察(1)

昔(たぶん2年前になるのかな?)に部活の新入生歓迎会にPythonの勉強がてらパズルゲームをつくりました。作ったのはいいんですが、どんな場合でも解けるか否かってのが自明ではなく、気持ち悪いのでときどき思い出して解けることの証明に取り組んでいます。結論としてはどうやらn>2のときは解けないらしいということなのですが。それ自体は苦手な組み合わせ理論を使ってパターン数計算してってので出しました。ただ、苦手であるがゆえにあっているか自信ない、エレガントじゃないのでもっときれいな証明がないかとかはひねくりまわしています。

　まずパズルのルールを(元のパズルと違い若干数学的表現になりますが)示しておきます。たとえばn=3のときランダムに正方形に配置された1～9までの数字を以下のような整列した形に直すことを目的とします。
1 2 3
4 5 6
7 8 9
直すために許されている操作は
3 1 2
4 5 6
7 8 9
あるいは
1 2 9
4 5 3
7 8 6
のように一番上の行を横にスライドして回す?かそれを縦にするかの2つの操作です。これを基本操作と呼び、この組み合わせでパズルを解いていきます。
今までの方針としてはパズルの操作を置換とみなして、それを行列で表しそれによって基本行列が構成できないことを示そうというもの。たとえばn=2のとき以下のようなパズルを考えます。
$\begin{pmatrix}a_{1,1} & a_{1,2} \\a_{2,1} & a_{2,2}\end{pmatrix}$
このとき
$\begin{pmatrix}a_{1,1} \\ a_{1,2} \\ a_{2,1} \\ a_{2,2}\end{pmatrix}$
みたいに位置を列ベクトルで表せば、基本操作はそれぞれ
$\begin{pmatrix}0 & 1 & 0 & 0 \\1 & 0 & 0 &0 \\0 & 0 & 1 & 0 \\0 & 0 & 0 &1 \end{pmatrix}$
$\begin{pmatrix}1 & 0 & 0 & 0 \\0 & 0 & 0 &1 \\0 & 0 & 1 & 0 \\0 & 1 & 0 &0 \end{pmatrix}$
とか表せるのでこれをがんばってごにょごにょ。
しかし見てわかるようにn=2でも4次行列となってしまい一般のnに対して調べるのは大変そうです...実際の情報量はそんなに多くないとはいえ、実験して性質を調べるってのでもPCの力を借りないとちょっと...
ところが今日大きな進展がありました。今日ふと置換群を行列として表現できるんだから線形性があるはず...ってことを思いつき。もしかしたらもっと線形代数を表に出してくれば解けるんじゃないかと解けるための指標を探し始めました。何気なくn=2,3の基本操作行列の行列式をとってみると-1と1になりました。これの原因は...行列式の交代性ですね。一般にnが奇数のとき行列式が1になるようです。これは置換と帰納法を使えば割合簡単に示せました。(実は計算してみるまで∀nに対して正となるとか勘違いしたのですが...)1か-1になるとは偶置換と奇置換の雰囲気がしますね。昔これをつかって証明を試みていた時期がありましたが、平面での置換に適応する方法が思いつかず、正確には使いこなせずあきらめていたのに思いがけないところで復活の予感。
さて
$det(AB)=det(A)det(B)$
という行列式関係式より
$n=2m+1(m\in\mathbb{N})$
のとき基本操作の積の行列式は常に正になることがわかります。また、とりうる置換の中には行列式が負となるものが存在するので結局
$n=2m+1(m\in\mathbb{N})$
のときパズルは解けない。

ということが示せます。やっと半分証明が完成しました。といってもまだ証明することは無限個残っているわけですが...解けないのはnが奇数のときだけに限られるのでしょうか?それとも3以上のすべての自然数についてとけないのでしょうか？まだわからなくなってきました。この方針でいいのならnが偶数のときは解けたほうがエレガントですね。偶数のとき解けないのだとしたらきっとさらにきれいな法則によって支配されているのでしょう。これからもこのことについて考えていくつもりなのでまたかくことがあるかと。最終的には解けるための条件、あるいは全パターンの分類とかしてみたいです。

　また、今回の証明の過程で偶置換と奇置換の性質が行列式の性質に還元できそうだという発見もありました。これについてはもう少し考察してみようと思います。結局線形代数というより行列式の理論でしたが、結果オーライということでｗ