わんくま勉強会東京82でごまかした8パズルのパターン数を調べてみた

　8パズルのパターン数は8!ぐらいですよーとかごまかしてましたが、ちゃんと解ける形だけ数えるとどうなのかなと思って列挙してみました。

　はいこれ列挙に使ったコード。

[code:cpp]
#include
#include
#include
bool is_pazzleout(const std::vector& seq)
{
int sum = 0;
for (int i = 0; i < seq.size(); ++i) { int f = i + 1; std::set cyclic;
cyclic.insert(f);
for (int j = i; f != seq[j]; j = seq[j] - 1) {
//std::cout << "f: " << i << ", seq[" << j << "]: " << seq[j] << std::endl; cyclic.insert(seq[j]); ++i; } sum += cyclic.size() - 1; } return sum % 2; } void print(const std::vector& seq)
{
std::cout << "( "; std::for_each(seq.begin(), seq.end(), [](int x) { std::cout << x << " "; }); std::cout << ")"; if (is_pazzleout(seq)) std::cout << "*"; std::cout << std::endl; } int main() { std::vector complete;
for (int i = 1; i <= 8; ++i) { complete.push_back(i); } do { print(complete); } while (std::next_permutation(complete.begin(), complete.end())); return 0; } [/code]

　Initializer listで初期化したいのになんかエラー出るから諦めたのはご愛嬌として。
　やってることは順列作って順列表示して順列の巡回置換の長さ-1の総和が奇数だったら印つけるだけです。
　これで列挙してみると印のつかなかった行が26939行ありました。$8!$が40320なので$\frac{1}{3}$ぐらいが解けないんですね。
　ちょっとすっきりしました。