8パズルとは、いわゆるスライドパズルだ。15パズルが一般的だ。
これを題材にして、Egisonでツリーのプログラミングに挑戦してみた。
公式のデモでも、ツリーを扱っている。
8パズルの有効パターンは何通りあるかを計算しようと思う。
方法1
ツリーのルートを、揃ったパターンとする。
それを、下に向かって成長させていく。追加するのは一手動かしたパターンだ。
同じ要素の所はとめる。
ツリーの成長が止まったら、全パターン網羅完了だ。
まずは3パズルで計算して、その後8パズルを計算した。
3パズルの全パターンは12だった。
……
6時間実行しても終わらなかった。
bugが発覚した。直せなかった。
（bugのせいで計算が終わらないのかは分からないけれど）
19/09/08追記
bug直しました！詳しくはこちらへ。
方法2
8パズルの全パターンは、9!=362880より小さい。それは分かる。
9!から、8パズルのルールで辿り着ける物をフィルタリングすれば良いのではないか。
以下の方法を使ってみよう。
参考記事：
定理：s に対応する状態からはじめたとき，
8パズルが完成できる ⟺ s を t にする置換のパリティ（偶奇）と「空き」の最短距離の偶奇が等しい。
置換のパリティを求めるには、
置換で1から順番にそろえていけば良いそうだ。
最初Egisonでやっていたけれど、計算が終わらないのでHaskellにした。
出来たプログラムはこちら。（ツリー使わなかったよ……）
8パズルの有効なパターンは、181440ということが分かった。
9!/2なのは偶然ではないのだろう。
おまけ
群論の言葉で言うと、以下になりそうだ。
スライドパズル群は、集合
permutations [1..9]を、二つの軌道に二等分する。
一つは[1, 2, 3, 4, 5, 6, 7, 8, 9]を元に持つ軌道。
もう一つは[1, 2, 3, 4, 5, 6, 8, 7, 9]を元に持つ軌道。
.
.
