15パズルは何故解けないのか？ - やねうらおブログ(移転しました)15パズルは誰でも知ってるだろう。プログラミングの練習がてらに誰もが一度は作ったことがあるかも知れない。しかし、右図の15パズルは解けない。 この問題は超古典であって、高木先生の「数学小景」にも載っている有名なものである。私は、これは誰でも知ってるものだとばかり思っていたが、先日うちのプログラマにあるゲームのための15パズルを実装してもらったとき、ゼンゼンわかってなかったので驚いた。 何故解けないのか、簡単に説明しておく。以下のスライドを参考にどぞ。 http://www.misojiro.t.u-tokyo.ac.jp/~tomomi/text/14-15.pdf あと、線形代数の教科書をお持ちなら行列式の定義のあたりを見て欲しい。「偶置換」と「奇置換」の説明が出てくる。 (スライドの要約) 15パズルのゴールを(1 2……14 15)とおく。右図の(1 2……15 14)はゴールを奇置
