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

Filed in 未分類

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

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

#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; }

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


Related Posts
Click to view/hide

Warning: sprintf() [function.sprintf]: Too few arguments in /home/users/2/lolipop.jp-dp07042166/web/wordpress/wp-includes/widgets.php on line 1042
Oenology Post Formats
Click to view/hide

Warning: sprintf() [function.sprintf]: Too few arguments in /home/users/2/lolipop.jp-dp07042166/web/wordpress/wp-includes/widgets.php on line 1042
Posts Calendar
Click to view/hide
2013年6月
« 4月   10月 »
 1
2345678
9101112131415
16171819202122
23242526272829
30  

Warning: sprintf() [function.sprintf]: Too few arguments in /home/users/2/lolipop.jp-dp07042166/web/wordpress/wp-includes/widgets.php on line 1042
アーカイブ
Click to view/hide

Warning: sprintf() [function.sprintf]: Too few arguments in /home/users/2/lolipop.jp-dp07042166/web/wordpress/wp-includes/widgets.php on line 1042
最近の投稿
Click to view/hide