ルービックキューブは25手以内で揃う！ 32
ストーリー by GetSet
上には上がいた 部門より
上には上がいた 部門より
Fatalwedge 曰く、
昨年6月に「ルービックキューブは26手以内で揃う！」というトピックがありましたが、テクノバーンの記事によると、そこから1年も経たずに「25手で揃う」ことが証明された模様。
ルービックキューブ協会の公式ルールでは、競技開始前のスクランブルを「25手」と定めていますが、いよいよルール改定が必要になってしまうのでしょうか。
Fatalwedge 曰く、
昨年6月に「ルービックキューブは26手以内で揃う！」というトピックがありましたが、テクノバーンの記事によると、そこから1年も経たずに「25手で揃う」ことが証明された模様。
ルービックキューブ協会の公式ルールでは、競技開始前のスクランブルを「25手」と定めていますが、いよいよルール改定が必要になってしまうのでしょうか。
ソースを見ろ -- ある4桁UID
え？ (スコア:5, すばらしい洞察)
「あらゆる状態から25手で6面完成できる」、つまり逆に考えると「6面から25手の手順で全パターンへ移行できる」ことが証明されたんだから、スクランブルは25手でokということなんでないの？
Re:え？ (スコア:1, おもしろおかしい)
Re:え？ (スコア:5, おもしろおかしい)
Re: (スコア:0)
Re:え？ (スコア:1)
小学生すごい (スコア:5, おもしろおかしい)
「すごーい！」
Re:小学生すごい (スコア:2)
色はそろっても、真ん中が変な向きになることはありますね。。。
# その状態からの戻し方がわからない・・・
Re: (スコア:0)
Re: (スコア:0)
Re: (スコア:0)
Re: (スコア:0)
Rokickiの証明の概略 (スコア:3, 参考になる)
Rokickiは139Mのcosetのうち約4000をグラフの構造から戦略的に選び、それぞれ19ないし20手以内で解けることを確認しました。これによって全coset(の全要素)が最大25手で到達可能なことを示したそうです。coset内の探索は「少なくとも○○手以内では解ける」というところでやめてしまうことで時間短縮しています。
以前に話題になったKunkleの方法は [srad.jp]、碁盤の目状の街で東西に何ブロック、南北に何ブロック、合計○○ブロックで到達可能とした上で、対角一番遠い地点までのななめの近道がないかさがす方法に例えることができます。Rokickiの方法は、首都圏の私鉄・地下鉄のようなネットワークにおいて、主要な乗り換え駅に待ち時間○○分以内の支店を配置することによって、どの駅からでも△△分以内にどこかの店舗でサービスを受けられる、という感じの戦略です。
この方法は、cosetの最大手数が短縮されることによってケーリーグラフ上のクリティカルパスが変わっていくので、それに応じて別のcosetを選んで解くことを繰り返せば、全体の上限をさらに短縮することができます(支店を追加して最大の待ち時間を短縮できる)。現在24手という上限をめざして計算を続行中だそうです。
なぜ1.6GHz？ (スコア:1)
2.4GHzで駆動すればもっと早く解けたのでは？
ってのが一番の疑問点だったりして…
#それとも最近のQ6600って1.6GHzなの？
Re:なぜ1.6GHz？ (スコア:2, 参考になる)
ふと思ったのだが (スコア:0)
あるいはそんなパターンはないという証明はあるのだろうか？
Re:ふと思ったのだが (スコア:3, 参考になる)
単純化して言うと、「全ピースをばらして適当に組み立てなおした場合に、そこから6面揃った状態にできる確率は1/12」。
Re:ふと思ったのだが (スコア:1, おもしろおかしい)
構造上ありえないと思います。
Re:ふと思ったのだが (スコア:1)
赤のピース一個に青いシールを貼って
やらせてみたら面白そうですね。
Re:ふと思ったのだが (スコア:5, 興味深い)
日本ランカーの某氏に対して実際に、別コメントにもある“角のピースをひねった状態”を渡したら10～15手ぐらい回したあと一瞬手を止め「ニヤッ」と笑って何事も無かったかのように“戻され”ました。
彼らを舐めちゃ駄目です。
Re:ふと思ったのだが (スコア:2, 参考になる)
このトラップを仕掛けるなら上級者ではなく中級者をターゲットにすべきです。
「ようやく手順書を見なくても揃えられるようになった」あたりがベスト。
涙目になりながら数分間「あれー？おかしいな、いつもはこんなはずじゃ」となること請け合い。
＃ 相手が可哀想だからやるなよ！絶対やるなよ！！
Re: (スコア:0)
＃っていうか、ピースの入れ替え後、スクランブルする以前の状態までになら、普通に直すことができると思う。
Re: (スコア:0)
ばらさないと作れないはずです。
Re:ふと思ったのだが (スコア:1)
Re:ふと思ったのだが (スコア:1, 興味深い)
1 2 3
4 5 6
7 8 9
のように並んでいたとき、
1 6 3
4 5 2
7 8 9
のように6と2だけ嵌め変えた奴は揃わないはずです。
またそれを元にシャッフルしたものも揃わないはずです。
そういう所は１５パズルみたいですね。
Re: (スコア:0)
赤 赤 赤 → 赤 赤 赤
赤 赤 赤 → 赤 赤 赤
赤 赤 赤 → 赤 青 赤
青 青 青 → 青 赤 青
青 青 青 → 青 青 青
青 青 青 → 青 青 青
Re:ふと思ったのだが (スコア:1)
それが実は完成（既に入れ替えられていたのでしょう。ピースはだいぶ緩んでましたから）だったと知ったのは２２のときに友人が持っていたルービックキューブを自力で完成させて、まもなく状態遷移を観察してからのこと。
ちなみに２カ所反転しているケースは復元できるはずです。
ええ、単なる自慢話ですが何か？
Youthの半分はバファリンでできています。
Re: (スコア:0)
Re:ふと思ったのだが (スコア:1)
Re:ふと思ったのだが (スコア:1)
４色で隣り合う各ピースが別の色になるようにする。
# ほとんどのピースが１点で4つづつ接しているので、もしかしたら３色でもOKか？