ルービックキューブ は 25手で完成可能、米研究者が新解法の証明に成功

ルービックキューブは「どんな状態」にあったとしても必ず25手で完成させることが可能ということが米研究者の論文により24日、明らかとなった。

20061127_260645.jpg


これまでの研究では「どんな状態」の場合のルービックキューブの完成には2007年に米ノースイースタン大学のジーン・コッパーマン博士らが発表した26手が最短の解法だった。今回、明らかとなった解法は従来発表されていた最短の解法を1手、短縮することに成功したことになる。この「数学的証明」に成功したのは米スタンフォード大学で数学の研究助手を務めるトマス・ロキッキさん。

ロキッキさんはルービックキューブの動きを個別な「手」としてではなく「動きの組み合わせ」と考えることで、200億通り存在するルービックキューブの空間遷移の状態を20億通りまでに集約。

その上で、その20億通りの組み合わせをインテルのCore2 Quad Q6600のパソコンを使って1500時間をかけて解析を行うことで、ルービックキューブはどんな状態にあったとしても必ず25手で完成させることが可能という新解法を見つけることに成功した。

引用元:technobahn


3 :名無しのひみつ:2008/03/29(土) 11:43:15 ID:SHjo6s7Y
> インテルのCore2 Quad Q6600のパソコンを使って1500時間をかけて解析
この時間を全て勉強時間に当てたら、弁護士や公認会計士受かりそうだな。

10 :名無しのひみつ:2008/03/29(土) 11:46:20 ID:Ms1MYx2K
>>3
それは無理、極まれに2000時間で受かる秀才がいるけど。


26 :名無しのひみつ:2008/03/29(土) 12:04:43 ID:SN2Z1MwT
>>3
PCが別室で、黙々と計算していたんだけどね。



4 :名無しのひみつ:2008/03/29(土) 11:43:48 ID:cFZUoh2g
人類の役に立つのか?


8 :名無しのひみつ:2008/03/29(土) 11:45:04 ID:i1qCKf9G
24手では不可能ってことを証明したのか?

9 :名無しのひみつ:2008/03/29(土) 11:45:48 ID:GvoKj5tX
>>8
それ大事だよな。



12 :名無しのひみつ:2008/03/29(土) 11:47:29 ID:PpJDbqxA
完成した状態からどんな状態へも25手で行けるということか。


13 :名無しのひみつ:2008/03/29(土) 11:47:55 ID:9CY9JkPd
これフィールズ賞もらえる?


17 :名無しのひみつ:2008/03/29(土) 11:57:39 ID:FCVKAqJ1
パソコン普通すぎて笑った、クロック落としてるのは何で?

18 :名無しのひみつ:2008/03/29(土) 11:58:40 ID:dlu4a6lD
>>17
昔に買ったからだろ、数年前はそれくらいだったからな。



19 :名無しのひみつ:2008/03/29(土) 11:59:48 ID:qixtZhFn
25手での完成にいたる道筋を組み立てる方法を作らなきゃ意味ないな。


20 :名無しのひみつ:2008/03/29(土) 12:01:08 ID:0ZUc/XC9
完成から1手ずらした状態からでも ちょうど25手で崩してまた完成まで行けるってこと?
全ての状態から25手「以下」でできるってこと?

23 :名無しのひみつ:2008/03/29(土) 12:03:08 ID:i5ISw4US
>>20
後者



22 :名無しのひみつ:2008/03/29(土) 12:02:40 ID:kWKOLHRt
大学のコンピュータセンター使わせて貰えなかったのかよ。


24 :名無しのひみつ:2008/03/29(土) 12:03:10 ID:R3EaFEh4
ルービックキューブの全パターンの求め方ってどうやんの?
数学詳しい人教えて。


27 :名無しのひみつ:2008/03/29(土) 12:05:33 ID:Poo7ucxJ
理論家としては優秀かもしれないが・・・
3GHzのPCを、10台並列で動かせば3日で終わるじゃないか。

30 :名無しのひみつ:2008/03/29(土) 12:09:24 ID:KRsjZjwg
>>27
こんなのは趣味の研究じゃないの?
昔のPCが研究室の隅にころがってたから、ちょいとプログラムを書いて走らせてみたって程度の。


33 :名無しのひみつ:2008/03/29(土) 12:19:50 ID:t6GptrUY
>>27
budgetって分かる?


35 :名無しのひみつ:2008/03/29(土) 12:25:53 ID:ziZ5GJls
>>27
こんな研究に最新PC10台も使ってたら、それこそ3流だと思うが?


52 :名無しのひみつ:2008/03/29(土) 13:41:56 ID:AVNplrEr
>>27
そもそも、並列化できる処理なのか?



28 :名無しのひみつ:2008/03/29(土) 12:08:31 ID:ABF3XHHv
ここまで色々遊べるんだから、玩具としては大したもんだと思う。


29 :名無しのひみつ:2008/03/29(土) 12:08:56 ID:wor93JLo
俺のPS3貸してやったのにな・・・


34 :名無しのひみつ:2008/03/29(土) 12:23:00 ID:tqj/jiEJ
25手?一瞬で完成させられる人がいなかったっけ?


38 :名無しのひみつ:2008/03/29(土) 12:33:11 ID:6qK6s/FA
あれって、1回ばらしてからもう一度組み立てれば1手だよ。


39 :名無しのひみつ:2008/03/29(土) 12:34:46 ID:XV4wPru9
数学オタクって、半端じゃないとこが呆れるよな。
究極の粘着性質なんだろうね、友達にはなりたくねえな・・・


47 :名無しのひみつ:2008/03/29(土) 13:07:37 ID:nYP22OXz
>>39
粘着の対象はお前じゃなくて数学だから安心しろ。



41 :名無しのひみつ:2008/03/29(土) 12:37:55 ID:38zB5Tyt
25年以上たったが、俺はできない。

49 :名無しのひみつ:2008/03/29(土) 13:27:37 ID:+R7CeOua
>>41
お前は俺か。



42 :名無しのひみつ:2008/03/29(土) 12:42:54 ID:QdkQUTP1
これ超高速でやってる人ってほとんど超能力者だよな・・・
何故かキューブ見てないし。


43 :名無しのひみつ:2008/03/29(土) 12:48:18 ID:5bDxClLj
そのうち同じ計算をAMDが、短時間でやってみせる予感。
関連記事
スポンサーサイト



コメント

これはすげえw

 中の人
( -ω-)y~~ RSSを改善しました。

行間を空けて、ニュースとネタに分ける事に。
#ネタのRSSは準備中、ニュースの下に続けて設置予定。

名無し隊員さん
次々改善されるなここ。

パソコンで計算しても1500時間もかかるのか
よくやったな。
あんな小さい箱にこんなにも詰まっているなんて

名無し隊員さん
グラフ理論の分野になるんかね? つか200億もあったんだ

名無し隊員さん
RSSに(*゚∀゚)ゞカガクニュース隊を入れてみてはどうだろうか

 
こういう、ゲームに関しての無駄な分析って好きだな。
6×6オセロは既に全手調査済みで、後手が勝てるんだっけか。

中の人、色々改善感謝。
俺がルービックキューブを完成させるまでここ見続けるぞ。
まずは…家の中から探すところから始めねば。

 中の人
米5
> RSSに(*゚∀゚)ゞカガクニュース隊を入れてみては

詳しくお願いします。

名無し隊員さん
※7
RSSの仕組み知らないんで申し訳ないが、他のサイトでは自分のところ更新したら自分のサイトの項目もRSSで更新されてたりするやつです。

中の人
米8
なるほど。

名無し隊員さん
1500時間もかかるのかぁ・・
すごいな~

 
ここのサイトは日々いろいろ変わっていくな。
それも良い方に。

名無し隊員さん
中の人って人が素直だからじゃね

名無し隊員さん
この論文を読みたいのだが、どこの雑誌に掲載されたか教えて!

名無しさん
そう考えると人間て凄いねー

人体の神秘やー

名無し隊員さん
*13
http://arxiv.org/abs/0803.3435

ここだニョロ

名無し隊員さん
人間が1分くらいで解けるものをコンピュータは1500時間かかるといえるのかな。

名無し隊員さん
コンピューターにやらしてるってのが詰まらん。
机の上で紙とペンで証明してくれよ。美しくないわ。

名無し隊員さん
全手検索で解法が正しい事を証明したってだけでは。

名無し隊員さん
コンピュータっていうと、これは四色問題方式なんだろうか。人間の証明ってできんのかな。

名無し隊員さん
*16
人間が1分もかからずに解くのは手数制限が無いとき

VIPPERな名無しさん
一度も完成したことのない俺にどう25手動かしたら出来るのか教えてくれw

名無し隊員さん
あれ・・・最近23手でできるってのを見たんだけどw

名無し隊員さん
俺の脳みそcpuだと平均100手くらい

名無し隊員さん
落ちで笑ったw
スーパーπに次ぐ新たな基本ベンチになったら笑えるなw

God's Number is 20

名無し隊員さん
キューブを任意の状態から完成させるために必要十分な手数(God's Number)は20手であると決定したようです.
・1995年に「どう頑張っても解くのに最低20手かかる」初期状態が発見された
・2010年7月に「全ての初期状態は20手かければ必ず解ける」ことが示された
・よって20が必要十分な手数
とのこと
リンク先の著者グループのサイトにはGod's Numberの上限・下限の推移や過去の論文への参照が載っています
非公開コメント

トラックバック