8パズルのパターン数は8!ぐらいですよーとかごまかしてましたが、ちゃんと解ける形だけ数えるとどうなのかなと思って列挙してみました。
はいこれ列挙に使ったコード。
[code:cpp]
Initializer listで初期化したいのになんかエラー出るから諦めたのはご愛嬌として。
#include
#include
#include
bool is_pazzleout(const std::vector
{
int sum = 0;
for (int i = 0; i < seq.size(); ++i) {
int f = i + 1;
std::set
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
{
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
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]
やってることは順列作って順列表示して順列の巡回置換の長さ-1の総和が奇数だったら印つけるだけです。
これで列挙してみると印のつかなかった行が26939行ありました。$8!$が40320なので$\frac{1}{3}$ぐらいが解けないんですね。
ちょっとすっきりしました。
わんくま勉強会東京#78の資料
わんくま勉強会東京#78の資料