GetSetによる
2007年06月05日 14時30分の掲載
昔は体が解法を覚えていたんだがな…部門より。
昔は体が解法を覚えていたんだがな…部門より。
37A 曰く、
マイコミジャーナルによると、 米ノースイースタン大学のコンピュータ科学部の教授と大学院生が、「ルービックキューブは26手以内で揃う」ことを証明したそうです。
これまでは、どんな状態であっても27手以内というのが証明されていましたが、それよりも1手少なくできるとのこと。
実証は、7テラバイトのディスクをRAMの拡張として使用し、秒間1億回のシミュレーションが可能なコンピュータで行ったとのこと。これにより、「ルービックキューブをどのような状態からでも26手以内に揃えられるソリューションを、およそ1秒程度のスピードで見つけ出せる」と豪語しています。
さて、日本の皆さん、クリックしている場合ではありません。これを超える「25手以内」を証明してみませんか？
関連ストーリー
「ルービックキューブ」ブーム再来 81 コメント
この議論は賞味期限が過ぎたので、保存されている。
新たにコメントを書くことはできない。
1).6色のペンキを用意する 2).白を塗る 3)...... (スコア:4, すばらしい洞察)
なぜクリックの話が、と思ったらルービックってハンガリー発なのね.... [wikipedia.org]
Re:1).6色のペンキを用意する 2).白を塗る 3)...... (スコア:2, おもしろおかしい)
#誰もが思いつくけどあえて口にしないネタなのでAC
親コメント
ディスクIOのネックが課題かなぁ (スコア:3, 参考になる)
自宅でこの手の総当り検証をみてやらせたときは、ディスクが遅すぎで困ったよ。
ラプター + デフラグ + なるだけシーケンシャルな読み込み を心がけても遅いものは遅い。
#資金の問題で RAID0は試していない(w
1CPUで50%以下を常にアプリが食べていて、残りはどうみてもディスクIO待ち。
ひたすらガリガリってアクセス音だけが永遠となりつづけた。
データが数十ギガバイト以上になると i-RAM とかも利用できないし。
数十年後には7TBのメモリがつめるようになって、一瞬で問題が解決できるようになるのかねぇ。
Re:ディスクIOのネックが課題かなぁ (スコア:2, 興味深い)
＞ラプター + デフラグ + なるだけシーケンシャルな読み込み を心がけても遅いものは遅い。
＞#資金の問題で RAID0は試していない(w
総当たりをする、という事が目的なんだったら
ディスクを早くするしかないんですが、
単に探索の為に総当たりをしているのだったら
(ルービックキューブもそうだと思いますが)
データ構造や、アルゴリズムの方を改良した方がいいですよね。
RAID0を使ったところで、全読み込みをするというのであれば高々2倍にしかならないのですから。
それよりは、読むデータを1/10に絞り込む方法を考えた方が余程効果的です。
色々頑張ってどうしようも無くなったときは・・・
その時こそハードでごり押しですね。
# でも、最近ごり押し出来ることが多くなったなぁとは思う
親コメント
えーと (スコア:2, おもしろおかしい)
Re:えーと (スコア:3, おもしろおかしい)
妖精哲学の三信
「だらしねぇ」という戒めの心、「歪みねぇ」という賛美の心、「仕方ない」という許容の心
親コメント
Re:えーと (スコア:3, おもしろおかしい)
親コメント
Re:えーと (スコア:2, すばらしい洞察)
１．冷蔵庫を開ける
２．揃ってるルービックキューブを取り出す
３．揃ってないルービックキューブを仕舞う
４．冷蔵庫を閉める
親コメント
Re:えーと (スコア:2, おもしろおかしい)
親コメント
最強の一手 (スコア:1, すばらしい洞察)
と宣言。
一方日本は (スコア:1, おもしろおかしい)
Re:一方日本は (スコア:3, おもしろおかしい)
リセットボタンで自動的に初期状態に戻る機能を追加するのでは
これで家庭に復旧諦めたキューブが埃かぶることもないですしw
#詳しくないので実現できるか不明…どこかの工学屋さんが趣味で挑戦しないかな。
親コメント
Re:一方日本は (スコア:2, 興味深い)
http://www.khi.co.jp/kawasakiworld/ht_flash.html [khi.co.jp]
親コメント
妥当なような気がする (スコア:1)
世界チャンピオンの手順は最適化されているような気がして来た。
# 人間の可能性ってすごい。
Re:妥当なような気がする (スコア:3, 興味深い)
すぐそばにスピードキュービング日本ランキング一桁が居るので聞いて見ました。曰く、
「だいたい50～60手ぐらいですよ」
との事。
公式ルールでは揃った状態から25手崩した状態で競技開始するらしいのですが、
「あんまり少ない手数が証明されちゃうとルール変えなきゃならなくなるかもですね」
とも言ってましたｗ
「何か、忘れてる気がするんだよなあ……」
カートチーム「風来旅団」 [fuurai.org]
親コメント
ところで (スコア:1)
---
24時間以上起きている頭でスゴイ桁の数字見るとくらくらする・・・
リベンジは68手以内 (スコア:2, 興味深い)
解析方法の概略は自分の日記 [fastwave.gr.jp]に少し書きました。
親コメント
質問 (スコア:1)
# 俺には真ん中だけずらすって無理！！
お約束 (スコア:1)
Re:シミュレーションでは証明にならない (スコア:3, 参考になる)
親コメント
Re:シミュレーションでは証明にならない (スコア:2, すばらしい洞察)
親コメント
Re:シミュレーションでは証明にならない (スコア:2, 興味深い)
(回した後に回転面を床につければ同じ状態になる)
回す方向は鏡面とすると、無視して考えられる。
最初の一手目は「完成形から一回回した状態」の一パターンしかないので、
完全に揃ってる状態ではなく、一手目を木構造のrootにできるかもしれない、などと思ったり。
#書いた後に不安になってきた。いいのかな？(笑
親コメント
Re:シミュレーションでは証明にならない (スコア:2, 参考になる)
(というか逆方向を取る時点で枝切りされる)
親コメント
Re:シミュレーションでは証明にならない (スコア:3, 参考になる)
こっちのページ [physorg.com]には論文へのリンクがあります。これから読んでみます。
ちなみに世界選手権でいちばんメジャーな解法である「LBL法」では平均56手くらいです。
自分で解きながら数えたこともありますがおおむね50～60手くらいです。
最小手数を競う競技もあります。
紙と鉛筆だけを使って1時間以内に見つかった解の手数を使います(公式ルール [jrca.cc]内のArticle E参照)。
公式世界記録 [worldcubeassociation.org]では28手、非公式記録 [speedcubing.com]では21手というのが今日現在の記録のようです。
親コメント
Re:シミュレーションでは証明にならない (スコア:3, 参考になる)
そこまでの最大手数、そこからの最大手数の和を計算したそうです。
最後のひと工夫でさらに3手縮めているところがミソのようですがまだ理解できていません。
Wikipediaの記事 [wikipedia.org]では、ルービックキューブの最短手数探索法について、
Thistlethwaiteによる4段階法、Kociembaによる2段階法が解説されています。
CoopermanとKunkleの方法は、同じように表記すれば、
G0=<L,R,F,B,U,D>
G1=<L2,R2,F2,B2,U2,D2>
と部分問題を設定した場合に相当します。
CoopermanとKunkleはcosetの要素全体に対して総当たり的に到達可能手数をさがしています。
このような方法だと、必ずG1を通るような経路しか計算していないので、手数のupper boundしか得られません。「G1を通れば26手で解ける状態」にも、G1を一度も通らないようなより短い手数が存在する可能性が残ります。
高田馬場から東京まで、東西線を必ず使うとして、大手町へ出るとか九段下へ出るとか、全部の場合を調べて遅くとも何分で着く、とはわかった。しかし東西線を使わない場合(JRだけとかタクシーとか)は調べていない、というような感じ。
親コメント
Re:シミュレーションでは証明にならない (スコア:2, 参考になる)
最後のひと工夫 (三手縮める) は Kociemba の Cube Explorer で brute force をかけました、ということでしょう。Section 7.3 のまんまです。
親コメント
Re:シミュレーションでは証明にならない (スコア:2, おもしろおかしい)
親コメント
Re:シミュレーションでは証明にならない (スコア:2, 参考になる)
天気予報は気象モデルを作ってごにょごにょするので、シミュレートしていると言える。
ルービックキューブについてなら、このパズルの本質は各キューブの配置と移動のさせ方のみであり、モデルはそのままルービックキューブ本体であると言える。
実物と同じ振る舞いをするものはエミュレータと呼ばれる。
この場合は「ルービックキューブをエミュレートして解法を探索した」と表現すべきかと。
親コメント
Re:シミュレーションでは証明にならない (スコア:2, 参考になる)
バグの可能性も否定できないので、数学による証明が待たれます。
親コメント
Re:シミュレーションでは証明にならない (スコア:2, 参考になる)
数え上げが数学ではない。という論調が見受けられますが、それは間違いです。
事実が証明できるなら、それは数学です。
エレガントではない、エレファントな解法だ。ってことで好まれないことは事実ですが。
それに、背理法や帰納法だって、最後に待っているのは数え上げでしょ？
かのガウスも、この手の数値実験を好んでいた。といわれています。
親コメント
Re:あながち間違いじゃないな (スコア:2, 参考になる)
ルービックキューブ [wikipedia.org]
しかし、14-15パズル [wikipedia.org]のようにあり得ない配置もあるかもしれないので、単純ではないかも。
親コメント
Re:あながち間違いじゃないな (スコア:2, 興味深い)
あり得ない状態を数えないでこの数字です。
最後に2で割っているのは、面を回すと辺の置換と角の置換が同時に起こることから来る制約です。
このあたりはHerbert Kociembaのページが詳しいです。
http://kociemba.org/cube.htm
左フレームの「The Mathematics behind Cube Explorer」以下を読みましょう。
手とり足とりわかりやすく解説してくれています。
親コメント
最低18手 (スコア:4, 参考になる)
まず、状態数は、角(3面見えている)が8個、辺(2面見えている)が12個のピースがあるので、辺のピースを1つ固定するとすれば、38 x 212 x 8! x 11! = 43 252 003 274 489 856 000 通りあります。
最初の1手は18通りの選択肢 (36じゃないですよ) があり、2手目以降は15通りです (17通りでもないです)。ここから、17手以上必要あることが分かります。あとちょっと工夫すると、17手では不足で18手必要というのが分かるようです。
NHK 受信料はテレビの台数分契約にしてほしい
親コメント
Re:最低18手 (スコア:2, 参考になる)
を証明はできていない，ってんだから18手が要る事は証明されてんでは？
#確か17手で到達可能な全状態数と，ルービックキューブの取り得る全状態数を比較して後者の
#方が大きいから最低でも18手は必要，っていう証明だった気がする．
親コメント
Re:えっ、 (スコア:1, おもしろおかしい)
親コメント
Re:丁度良い絵が (スコア:2, おもしろおかしい)
白２面はありえる状態でした。
なので、このキューブは揃えられる可能性が残っています。
親コメント
Re:シミュレーションでは証明にならない (スコア:1)
「シミュレーションした」と「総当たりした」は，全然違うことだと言いたかったのですが． シミュレーションすることは，証明するための必要条件でも十分条件でもありません．
親コメント
Re:足回し (スコア:1)
片手で完成出来る人で、足の指でジャンケンでチョキができるぐらいに
動かせる人なら、十分揃えられますよ。（時間は掛かりますが。）
> よく廻るように、分解して油をさしたりしていたのですが、今のキューブも
> 昔と同じ作りなんですかね。
基本的な構造は昔と変わりませんが、パーツが取れにくいようになったり、
シールの強度が上がったりと、少しずつ変更はされているようです。
個人的には、90年代に売られていたものが好みですが。
親コメント