ペナントパズルをRubyで解く
箱入り娘とほぼ同類のスライドパズルとして、ペナントパズルというものがあるらしいとWikipediaで知った。
左上の2x2のピースを右下にまで持ってくるというもので、箱入り娘の解法のために作ったRubyスクリプトの初期条件とゴール判定の位置だけを変えてやってみた。
それなりに難しいものなのかと思ったら、一瞬で解答にたどり着いた。解答がすぐに表示されるというのは想定外の動作だったのでバグかと思った。妙にうれしい。
深さ優先では354手、幅優先では1分ほどかかって5万ほど状態を調べたのちに、41手の解法を発見できた。あれ？ Wikipediaによるとペナントパズルの最短手順は59手と書いてある（追記：ゴールの位置を間違えてた。ゴールは右下じゃなくて左下。後でやり直してみる）。
ともあれ、深さ優先の解法を見ると、あまりにも頭が悪い感じ。意味のない動きでゴチャゴチャ動かしいる様子が見て取れる。一方、幅優先のほうは結構ゴールに向かって一直線に進む感じで、なぜか「知性」を感じる。
幅優先で出てきた解答は以下。
initial state: 0 0 1 1 0 0 2 2 5 6 . . 7 8 3 3 7 8 4 4 found a solution: 8 7 1 1 8 7 2 2 3 3 . . 4 4 0 0 6 5 0 0 process: 0 0 1 1 0 0 2 2 5 6 . . 7 8 3 3 7 8 4 4 ------- 0 0 1 1 0 0 2 2 5 . 6 . 7 8 3 3 7 8 4 4 ------- 0 0 1 1 0 0 2 2 . 5 6 . 7 8 3 3 7 8 4 4 ------- 0 0 1 1 0 0 2 2 . 5 . 6 7 8 3 3 7 8 4 4 ------- 0 0 1 1 0 0 2 2 . . 5 6 7 8 3 3 7 8 4 4 ------- . . 1 1 0 0 2 2 0 0 5 6 7 8 3 3 7 8 4 4 ------- . 1 1 . 0 0 2 2 0 0 5 6 7 8 3 3 7 8 4 4 ------- 1 1 . . 0 0 2 2 0 0 5 6 7 8 3 3 7 8 4 4 ------- 1 1 2 2 0 0 . . 0 0 5 6 7 8 3 3 7 8 4 4 ------- 1 1 2 2 0 0 5 . 0 0 . 6 7 8 3 3 7 8 4 4 ------- 1 1 2 2 0 0 . 5 0 0 . 6 7 8 3 3 7 8 4 4 ------- 1 1 2 2 . 0 0 5 . 0 0 6 7 8 3 3 7 8 4 4 ------- 1 1 2 2 . 0 0 5 7 0 0 6 7 8 3 3 . 8 4 4 ------- 1 1 2 2 7 0 0 5 7 0 0 6 . 8 3 3 . 8 4 4 ------- 1 1 2 2 7 0 0 5 7 0 0 6 8 . 3 3 8 . 4 4 ------- 1 1 2 2 7 0 0 5 7 0 0 6 8 3 3 . 8 . 4 4 ------- 1 1 2 2 7 0 0 5 7 0 0 6 8 3 3 . 8 4 4 . ------- 1 1 2 2 7 0 0 5 7 0 0 . 8 3 3 6 8 4 4 . ------- 1 1 2 2 7 0 0 . 7 0 0 5 8 3 3 6 8 4 4 . ------- 1 1 2 2 7 0 0 . 7 0 0 5 8 3 3 . 8 4 4 6 ------- 1 1 2 2 7 0 0 . 7 0 0 . 8 3 3 5 8 4 4 6 ------- 1 1 2 2 7 . 0 0 7 . 0 0 8 3 3 5 8 4 4 6 ------- 1 1 2 2 . 7 0 0 . 7 0 0 8 3 3 5 8 4 4 6 ------- 1 1 2 2 . 7 0 0 8 7 0 0 8 3 3 5 . 4 4 6 ------- 1 1 2 2 . 7 0 0 8 7 0 0 8 3 3 5 4 4 . 6 ------- 1 1 2 2 . 7 0 0 8 7 0 0 8 3 3 5 4 4 6 . ------- 1 1 2 2 . 7 0 0 8 7 0 0 8 3 3 . 4 4 6 5 ------- 1 1 2 2 8 7 0 0 8 7 0 0 . 3 3 . 4 4 6 5 ------- 1 1 2 2 8 7 0 0 8 7 0 0 3 3 . . 4 4 6 5 ------- 1 1 2 2 8 7 . . 8 7 0 0 3 3 0 0 4 4 6 5 ------- 1 1 . . 8 7 2 2 8 7 0 0 3 3 0 0 4 4 6 5 ------- . 1 1 . 8 7 2 2 8 7 0 0 3 3 0 0 4 4 6 5 ------- . . 1 1 8 7 2 2 8 7 0 0 3 3 0 0 4 4 6 5 ------- . 7 1 1 8 7 2 2 8 . 0 0 3 3 0 0 4 4 6 5 ------- 8 7 1 1 8 7 2 2 . . 0 0 3 3 0 0 4 4 6 5 ------- 8 7 1 1 8 7 2 2 3 3 0 0 . . 0 0 4 4 6 5 ------- 8 7 1 1 8 7 2 2 3 3 0 0 4 4 0 0 . . 6 5 ------- 8 7 1 1 8 7 2 2 3 3 0 0 4 4 0 0 . 6 . 5 ------- 8 7 1 1 8 7 2 2 3 3 0 0 4 4 0 0 . 6 5 . ------- 8 7 1 1 8 7 2 2 3 3 0 0 4 4 0 0 6 . 5 . ------- 8 7 1 1 8 7 2 2 3 3 0 0 4 4 0 0 6 5 . . ------- 8 7 1 1 8 7 2 2 3 3 . . 4 4 0 0 6 5 0 0 -------
