パスワードを忘れた？ アカウント作成
Close
22069 story

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

ストーリー by GetSet
上には上がいた 部門より

Fatalwedge 曰く、

昨年6月に「ルービックキューブは26手以内で揃う！」というトピックがありましたが、テクノバーンの記事によると、そこから1年も経たずに「25手で揃う」ことが証明された模様。
ルービックキューブ協会の公式ルールでは、競技開始前のスクランブルを「25手」と定めていますが、いよいよルール改定が必要になってしまうのでしょうか。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

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

  • え？ (スコア:5, すばらしい洞察)

    by Anonymous Coward on 2008年03月28日 12時29分 (#1320902)

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

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

  • 小学生すごい (スコア:5, おもしろおかしい)

    by Anonymous Coward on 2008年03月28日 13時09分 (#1320948)
    「俺さー、ルービックキューブこないだ5面まで出来たんだぜー！もうちょっとだったんだけどなー！」
    「すごーい！」

    • Re:小学生すごい (スコア:2)

      by phenix (31258) on 2008年03月29日 8時52分 (#1321420)
      柄の描いてあるタイプのルービックキューブ(派生品)だと
      色はそろっても、真ん中が変な向きになることはありますね。。。

      # その状態からの戻し方がわからない・・・
      シェア
      親コメント

  • Rokickiの証明の概略 (スコア:3, 参考になる)

    by mad-p (1491) on 2008年03月30日 1時04分 (#1321657)
    元記事からリンクされている論文 [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？ (スコア:1)

    by iwamoto (679) on 2008年03月28日 23時47分 (#1321305) 日記
    >Core2 Quad Q6600（1.6GHz）のパソコンを使って1500時間

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

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

    • Re:なぜ1.6GHz？ (スコア:2, 参考になる)

      by mad-p (1491) on 2008年03月30日 1時09分 (#1321660)
      個人所有のPCでやってるからみたいですね。 ビットマップの部分をMapReduce化してGoogleの計算機を使ったらどんどん上限が下がるかもしれませんね。
      シェア
      親コメント

  • ふと思ったのだが (スコア:0)

    by Anonymous Coward on 2008年03月28日 12時49分 (#1320923)
    ルービックキューブで、全面そろった状態から、何手かけても移行できないパターンと言うのは存在するのだろうか？
    あるいはそんなパターンはないという証明はあるのだろうか？

    • Re:ふと思ったのだが (スコア:3, 参考になる)

      by Vorspiel (2391) on 2008年03月28日 15時10分 (#1321035) ホームページ
      つ Wikipediaでの説明 [wikipedia.org]。

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

      シェア
      親コメント

    • Re:ふと思ったのだが (スコア:1, おもしろおかしい)

      by Anonymous Coward on 2008年03月28日 12時55分 (#1320931)
      たとえば、二面以上の中央部に同じ色が出現することは
      構造上ありえないと思います。
      シェア
      親コメント

    • Re:ふと思ったのだが (スコア:1)

      by NOBAX (21937) on 2008年03月28日 13時09分 (#1320947)
      上手な人に
      赤のピース一個に青いシールを貼って
      やらせてみたら面白そうですね。
      シェア
      親コメント

      • Re:ふと思ったのだが (スコア:5, 興味深い)

        by Fatalwedge (6623) <fatal@fuurai.org> on 2008年03月28日 13時28分 (#1320962) 日記
        タレコミ子です。

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

        • Re:ふと思ったのだが (スコア:2, 参考になる)

          by Fatalwedge (6623) <fatal@fuurai.org> on 2008年03月28日 15時05分 (#1321033) 日記
          追記。
          このトラップを仕掛けるなら上級者ではなく中級者をターゲットにすべきです。
          「ようやく手順書を見なくても揃えられるようになった」あたりがベスト。
          涙目になりながら数分間「あれー？おかしいな、いつもはこんなはずじゃ」となること請け合い。

          ＃ 相手が可哀想だからやるなよ！絶対やるなよ！！
          シェア
          親コメント

          • Re: (スコア:0)

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

    • Re: (スコア:0)

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

        • Re:ふと思ったのだが (スコア:1, 興味深い)

          by Anonymous Coward on 2008年03月28日 13時28分 (#1320961)
          そういうのではなくて、たとえば６面揃った状態で、ある面が
          1 2 3
          4 5 6
          7 8 9
          のように並んでいたとき、
          1 6 3
          4 5 2
          7 8 9
          のように6と2だけ嵌め変えた奴は揃わないはずです。
          またそれを元にシャッフルしたものも揃わないはずです。

          そういう所は１５パズルみたいですね。
          シェア
          親コメント

          • Re: (スコア:0)

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

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

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

              ええ、単なる自慢話ですが何か？
              --
              Youthの半分はバファリンでできています。
              シェア
              親コメント

    • Re: (スコア:0)

      by Anonymous Coward
      ７色以上に塗り分ける
typodupeerror

物事のやり方は一つではない -- Perlな人