15 Puzzle

以前、JavaScriptで15ゲームを作ったときに、noripyさんが [id:noripy:20051219:1135013638] で「どういう配置なら解けるのか」という問題について書かれていました。 私が15ゲームを書いたときは、何かの授業で「15ゲームが解けるのは偶置換のときだけだよ」と言っていたのを思い出して書いたのですが、証明はしてないです。 で、考えてみたのだけどよく分からず。 調べてみると A Modern Treatment of the 15 Puzzle(pdf) っていうのがそれっぽいんだけど、まだ読んでなかったりします。 英語に弱いのはいい加減何とかするべきですな。