スライドパズルの数学

バイオハザード４、PCバージョンをやってて、アシュリー

（参考動画）



を操作するシーンで3*3のスライドパズルがあった。
こんなの
http://curahome.net/puzzle/slidepuzzle/3x3/

小さい頃にディズニーランドのお土産とかで遊んだことあるけど、これの数学使って何かわからないの？とか思ってシコシコノートにカキカキしてたけど、イマイチ（このとき料金未払いでネット止まってたorz)。


すぐ思いつくのは、例えば簡単のために2*2にして、4マスだから、4を空白として(2,4,3,1)と数を並べて、４と左右は交換OK、上下の交換4±2（一般にn*nならn^2±n）もOK。それ以外はダメ。交換は普通に行列で表現できる。ココまではいい。

で、スタート時のベクトルをxs、完成時のベクトルをx0、１回の操作の行列をTiとすると、
Tを何回かかけて完成させるわけだから。

Tn・・・・T2T1 x_s=x_0

・・・で、どーする？
操作の行列のdetは-1。くらいしか手がかりが思いつかなくてGive Up！

で、ネット復活。

高校生への数学講義の一例 : 15パズルの非可解性について　和歌山大学教育学部教育実践総合センター紀要
http://tinyurl.com/y8e7zx9

なるほろ、と思った。交代式みたいなの持ってくるのね・・・と。あと、空白の場所の情報(i+j)。


1.任意の要素の交換で転置数（2つの数の組み合わせを順番に全て書き出して(a,b)でa>bとなるもの）の偶奇は必ず変化する。偶数→奇数　奇数→偶数

2.意味のある操作は全て要素の交換で表せる

3.位置情報を加えた転置数+i+j（名前忘れたｗ）を考えると、上下左右の移動で偶奇は必ず変化する

4.1と3より、結局1回の操作で偶奇は変化しない

初期状態、例えば(1234)は転置数0で偶数。よって、可能な配置である必要条件は転置数が偶数であること。つまり、奇数だったら解けない。
とあって、実は必要十分なんだけど、その証明は参考文献みてください～♪で終わってた。
3*3だっったら9!÷２が可能な配置の数。
置換群から学ぶ組み合わせなんちゃら、理科大の時、離散数学担当してた吉沢なんちゃら先生の本だったけど借りてみよーかなっと。

新規、既存のアイディアを元に記号とか用語とかその場で定義して使いこなす数学の人ってすげーなぁ、と思った。


っていうのをmixi日記に書いたけど場違いだと思った。