ルービックキューブは25手以内で揃う！

Fatalwedge 曰く、

昨年6月に「ルービックキューブは26手以内で揃う！」というトピックがありましたが、そこから1年も経たずに25手が証明された模様。

ルービックキューブ協会の公式ルールでは競技開始前のスクランブルを25手と定めていますが、いよいよルール改定が必要になってしまうのでしょうか。

え？

[Anonymous Coward]

ルービックキューブ協会の公式ルールでは、競技開始前のスクランブルを「25手」と定めていますが、いよいよルール改定が必要になってしまうのでしょうか。

「あらゆる状態から25手で6面完成できる」、つまり逆に考えると「6面から25手の手順で全パターンへ移行できる」ことが証明されたんだから、スクランブルは25手でokということなんでないの？

Re:え？

[Anonymous Coward]

協会すごい！

Re:え？

[virtual (15806)]

つーか、競技に限って言えば「競技開始前のスクランブルを「25手」」としているのなら、25手以内で揃うのは当たり前ですよね。

Re:

[Anonymous Coward]

まあスクランブル前の状態が全面揃った状態なら確かにそうですね。

Re:え？

[virtual (15806)]

ん？公式ルールにはそう書いてありますよ。

小学生すごい

[Anonymous Coward]

「俺さー、ルービックキューブこないだ5面まで出来たんだぜー！もうちょっとだったんだけどなー！」
「すごーい！」

Re:小学生すごい

[phenix (31258)]

柄の描いてあるタイプのルービックキューブ(派生品)だと
色はそろっても、真ん中が変な向きになることはありますね。。。

# その状態からの戻し方がわからない・・・

Re:

[Anonymous Coward]

ツクダの純正キューブの説明書には「５面」て書いてありましたよ。

Re:

[Anonymous Coward]

表紙裏が１面なんですね

Re:

[Anonymous Coward]

ただの野暮です

Re:

[Anonymous Coward]

ごめん

Rokickiの証明の概略

[mad-p (1491)]

元記事からリンクされている論文 [arxiv.org]を読みました。今回の証明概略はこんな感じ:

• ルービックキューブ群Gとその部分群H=<U,D,R2,L2,F2,B2>を考え、Hとcoset空間G＼Hの性質を調べるのはこれまでと同じアプローチ。Hの要素は20G個あり、直交するようにcosetが2.2G個ある。20G×2.2G=約43Eでキューブの取り得る全状態数になる。
• 従来の解法(Reidの方法) [wikipedia.org]は、Hが最大18手で到達可能、coset空間が最大12手で到達可能なので、18+12手以内でキューブの全状態が到達可能とするもの。
• Rokickiの方法は、すべてのcosetにつき、coset内の全要素がある手数(例えば25手)以下で解けると証明することによって、全キューブ状態が25手以下で解けると示すもの。cosetは2.2G個あるが、対象性を考えると139M個だけ考えればよい。
• cosetを頂点とするケーリーグラフを作成。あるcosetが20手以内で解けるなら、グラフ上で隣にあるcosetは21手以内で解けることを利用すれば、全数を解かなくてもよい。
• あるcosetの必要手数上限を得るために、1要素を1ビットに対応させた20Gビットのビットマップを使って、breadth-firstサーチを実行(集合の各要素を解くのでなく全体を一気に解くのでset solverと称している)。上限付近は具体的なキューブをKociembaの解法で解いてみることによって、時間のかかるBFサーチを省力化。

Rokickiは139Mのcosetのうち約4000をグラフの構造から戦略的に選び、それぞれ19ないし20手以内で解けることを確認しました。これによって全coset(の全要素)が最大25手で到達可能なことを示したそうです。coset内の探索は「少なくとも○○手以内では解ける」というところでやめてしまうことで時間短縮しています。

以前に話題になったKunkleの方法は [srad.jp]、碁盤の目状の街で東西に何ブロック、南北に何ブロック、合計○○ブロックで到達可能とした上で、対角一番遠い地点までのななめの近道がないかさがす方法に例えることができます。Rokickiの方法は、首都圏の私鉄・地下鉄のようなネットワークにおいて、主要な乗り換え駅に待ち時間○○分以内の支店を配置することによって、どの駅からでも△△分以内にどこかの店舗でサービスを受けられる、という感じの戦略です。

この方法は、cosetの最大手数が短縮されることによってケーリーグラフ上のクリティカルパスが変わっていくので、それに応じて別のcosetを選んで解くことを繰り返せば、全体の上限をさらに短縮することができます(支店を追加して最大の待ち時間を短縮できる)。現在24手という上限をめざして計算を続行中だそうです。

なぜ1.6GHz？

[iwamoto (679)]

>Core2 Quad Q6600（1.6GHz）のパソコンを使って1500時間

2.4GHzで駆動すればもっと早く解けたのでは？
ってのが一番の疑問点だったりして…

#それとも最近のQ6600って1.6GHzなの？

Re:なぜ1.6GHz？

[mad-p (1491)]

個人所有のPCでやってるからみたいですね。 ビットマップの部分をMapReduce化してGoogleの計算機を使ったらどんどん上限が下がるかもしれませんね。

ふと思ったのだが

[Anonymous Coward]

ルービックキューブで、全面そろった状態から、何手かけても移行できないパターンと言うのは存在するのだろうか？
あるいはそんなパターンはないという証明はあるのだろうか？

Re:ふと思ったのだが

[Vorspiel (2391)]

つ Wikipediaでの説明 [wikipedia.org]。

単純化して言うと、「全ピースをばらして適当に組み立てなおした場合に、そこから6面揃った状態にできる確率は1/12」。

Re:ふと思ったのだが

[Anonymous Coward]

たとえば、二面以上の中央部に同じ色が出現することは
構造上ありえないと思います。

Re:ふと思ったのだが

[NOBAX (21937)]

上手な人に
赤のピース一個に青いシールを貼って
やらせてみたら面白そうですね。

Re:ふと思ったのだが

[Fatalwedge (6623)]

タレコミ子です。

上手な人に不可能な形を渡すイタズラ

これ、残念ながら数秒でばれます。
日本ランカーの某氏に対して実際に、別コメントにもある“角のピースをひねった状態”を渡したら10～15手ぐらい回したあと一瞬手を止め「ニヤッ」と笑って何事も無かったかのように“戻され”ました。
彼らを舐めちゃ駄目です。

Re:ふと思ったのだが

[Fatalwedge (6623)]

追記。
このトラップを仕掛けるなら上級者ではなく中級者をターゲットにすべきです。
「ようやく手順書を見なくても揃えられるようになった」あたりがベスト。
涙目になりながら数分間「あれー？おかしいな、いつもはこんなはずじゃ」となること請け合い。

＃ 相手が可哀想だからやるなよ！絶対やるなよ！！

Re:

[Anonymous Coward]

手順書見ないでできるようになった人は、手順書ではあり得ないパターンになっていることにすぐ気づきますよ。
＃っていうか、ピースの入れ替え後、スクランブルする以前の状態までになら、普通に直すことができると思う。

Re:

[Anonymous Coward]

辺中央の1ピースだけ色が入れ替わっている状態。
ばらさないと作れないはずです。

Re:ふと思ったのだが

[tarosuke (2403)]

こういうの？ [gate01.com]

Re:ふと思ったのだが

[Anonymous Coward]

そういうのではなくて、たとえば６面揃った状態で、ある面が
1 2 3
4 5 6
7 8 9
のように並んでいたとき、
1 6 3
4 5 2
7 8 9
のように6と2だけ嵌め変えた奴は揃わないはずです。
またそれを元にシャッフルしたものも揃わないはずです。

そういう所は１５パズルみたいですね。

Re:

[Anonymous Coward]

隣り合った二面の中央ピースを反転させるだけでもOK

赤 赤 赤　→　赤 赤 赤
赤 赤 赤　→　赤 赤 赤
赤 赤 赤　→　赤 青 赤
青 青 青　→　青 赤 青
青 青 青　→　青 青 青
青 青 青　→　青 青 青

Re:ふと思ったのだが

[Youth (28154)]

小学生の頃６つ年上の従兄弟のルービックキューブに関心を示していじくり回してたら結局お下がりとして貰ったことがあったのですが、後日まさにその状態まで辿り着いて限界を感じてぶん投げました。
それが実は完成（既に入れ替えられていたのでしょう。ピースはだいぶ緩んでましたから）だったと知ったのは２２のときに友人が持っていたルービックキューブを自力で完成させて、まもなく状態遷移を観察してからのこと。

ちなみに２カ所反転しているケースは復元できるはずです。

ええ、単なる自慢話ですが何か？

--
Youthの半分はバファリンでできています。

Re:

[Anonymous Coward]

７色以上に塗り分ける

Re:ふと思ったのだが

[y.katz (6948)]

中央に向きのある絵を描くと難易度上昇？

Re:ふと思ったのだが

[USH (8040)]

７色以上に塗り分ける

４色で隣り合う各ピースが別の色になるようにする。

# ほとんどのピースが１点で4つづつ接しているので、もしかしたら３色でもOKか？