【パズル】ルー ビック・キューブはどんな状態からでも26手以下で揃えられる〜スパコンで解明[07/08/20]

スーパー・コンピューターを使った数時間のナンバークランチングによって、Rubik's cube
（ルービック・キューブ）の最終的な解が見えてきました

今回の研究では、「Rubik's cube」を26未満の移動によって各面がそろった状態に戻す事が
可能だ、という事が証明されています。

スーパー・コンピューターは、これまでに求められていた最も良い解決策よりも1手少ない
移動によって、それが可能だという証拠を得るために、 63時間という時間を必用としました。

今回の研究を計画した2人のコンピュータ科学者達は、より多くの研究を行うことによって、
必用とされる移動回数はより少なくなるかもしれない、と考えています。

キューブの解法

Northeastern Universityの大学院生であるDaniel・KunkleとGene・Cooperman が、それを証明
するためには、いくつかのスマートな思考が必用とされました。なぜなら、「Rubik's cube」では
存在しうる状態の数が「430億の10億倍」という厖大な数になるからです。それはスーパー・コン
ピューターを使用したとしても、非常に長い時間を必用とする作業に成るのです。

彼等はそれを順次試してゆく代わりに、彼らの計算にツーステップのテクニックを使用しました。

まず初めに、彼らは1万5000の「half-solved solutions（半分解決している解決策）」の1つに
到着するように、スーパー・コンピューターをプログラムしました。彼らはそこから更に少数の
移動を行うことによって、その1万 5000の立方体の全てが完全に解決出来る事を利用したの
です。

そこで得られた結果は、それぞれの面がどんな状態になっているかに関わらず、あらゆる
「Rubik's cube」は最大で29手の移動によって完全に解決される、またそのほとんどが26手
もしくはより少ない数で完成されるかもしれない、という事を示していました。

次の段階で、研究者達は26以上の移動を必要とした少数の「問題」のある構成に焦点を合
わせたのです。

「問題」のある構成を持っていたケースはごく少数だったので、研究者達はそれらのキューブを
完全に解決する最も良い方法を捜し求める為に、スーパー・コンピュータを使用することができました。

そして、スーパー・コンピューターは、それらの特別なケースのすべてが 26未満の移動に
よって完全に解決可能だ、という事を明らかにしたのです。

今回の研究は、どんな面の状態を持つ「Rubik's cube」であってもそれを元の状態に戻せる、
移動の最小の数である「God's Number（神様の数字）」の解明を、また一歩進めるものなのです。

神様は「Rubik's cube」を解決するために、最も少ない移動数を必要とするだろう、という事に
よってその数字は「God's Number」と命名されています。理論の研究は、その数が「20の並び
の前半」にあるだろう、という事を示しています。

DunkleさんとCoopermanさんは、オンタリオ州のウォータールーで開催された International
Symposium on Symbolic and Algebraic Computationで、その発見を発表しています。

（ニュースソース）BBC NEWSの和訳サイト
http://www.mypress.jp/v2_writers/beep/story/?story_id=1645026

BBC NEWS
http://news.bbc.co.uk/2/hi/technology/6949149.stm

関連スレ（こちらからお借りしました、感謝です。さらに情報提供者の某板補佐さんにも感謝です）
【科学】「ルービック・キューブはいかなる状態からでも26手以下で揃えられる」…スーパーコンピューターが解き明かす
http://news22.2ch.net/test/read.cgi/newsplus/1187534092/

２ゲット
>>3にはエラの張った右翼が家に押しかけてくる。

3ゲットなら
2の予想は>>4に適用される。

はっきり言って安倍晋三は気持ち悪い

今までの結果が26だったら、以下と未満は大きな違いを生むと思うのだが。
どうでしょうか？
この場合整数以外にあり得ないのだから「以下」が訳としては正しそうな
気がするんですが？どうでしょうか？
本文の未満の方が間違ってるのでは？
>Rubik's cube can be returned to its original state in no more than 26 moves.
26より多くはならないだから、26が最大数ってことと思うのですが？

家にはRainbow Cubeがある。

どうやっても5面までしか揃えられない(*^_^*)

>>5
私、それと関連スレの記者さんもそう思っているのですが、本文に手を加えるのは
躊躇してしまうので、スレタイだけでも「以下」にしてみました。
後に修正がなされるかもしれませんが、それまでは>>5さんのように読み替えて
いただければいいかと思います。

【科学】「ルービック・キューブはいかなる状態からでも26手以下で揃えられる」…スーパーコンピューターが解き明かす
http://news22.2ch.net/test/read.cgi/newsplus/1187534092/
どろろ丸φ ★：2007/08/19(日) 23:34:52

俺が今暗算してみたら25手以下でいけることが判明した

まぁコレならチェスの世界チャンピオンも負ける筈だ！
何れは将棋でも負けるんだろう？！

>>10 アンディ・リビイ乙

なんで２６なんだ？

これはびっくり

>>12
思考トラックが３つ以上あるのか？

>>13
3x3x3-1

４列なら

4X4X4X4-1 で２５５手ね

解が分かると実際やるは違うからね。

アンディ・リビイなら暗算だけじゃなくて検算に計算尺も使ったろうよｗ

>>1
なんで「必用」なのかなあ、普通に必要って変換されるでしょうに。

ところで超ひも理論では、２６次元という数式も成立する可能性があるらしい。
２６つながりで何か意味を見出せないかな。

俺なんて４８手のうち、まだ一つも試したことないんだぜ

これって
「26手以内でルービックキューブは揃う!! 米研究者が証明」
http://journal.mycom.co.jp/news/2007/06/05/004/index.html
と同じ話でしょ？

>>7
5面しか揃えることはできないだろう。

俺は是非五面しか揃ってないやつをうpしてほしな〜。>>7

>>18 が真実だなｗ

自分は、解に向かっているかどうかを感じ取ることが出来ない。

いつまでも間違った手＋２６手＝∞　（ＴΛＴ）

欽ちゃん、ルービックキューブも得意だったんだよなあ、確か。

ルービックキューブの面を揃えるのがやけに上手い人がときどきいる。

風俗勤務女＝　魔界 ◆RC3h9.WHho　＝　東芝産業システム社

最終状態はキレイとはいえない。もっと芸術的にキレイな絵柄を目的とすべきだ。

ルービックきゅーぶの達人は何手位で揃えてるの？

ルービックマジックで酔った俺はこの研究結果には賛同しかねる。

ルービックキューブの面がそろった状態から
全ての組み合わせを26手以下で作り出せるっていうことか

>>32
１手。

>>34
２^２６通り？？

（18）＾26　通りでしょう？

スーパーと名のつくコンピュータ使ってやってることはルービックキューブかよ

おめでてーな

>>32
だいたい４０台かな

スネークキューブならｵﾚにまかせろ！

全通り計算して照明するとか寺ﾊﾞｶｽ

数学で美しく証明できないのかな？

俺もルービックキューブが全面揃えられると思っていた頃がありました




都市伝説乙

>>21は評価されるべき

>>44
現在では、82手もあるようです。しかも、厳密に分けると300手くらいだそうですね。

昔、２０数年前に、学習院大学のどなたか女性の学生の方が、群論を使って
任意の初期状態から全部揃った状態へ確実に導くことの出来る方法を与える
ことに成功しておられました。確か、数理科学か数学セミナーか、そんな
雑誌で読んだ記憶があります。栗田さんとおっしゃったかな？

劇団ひとり

>>46
20数年前のI/O誌に乗っていたやつかな？

スパコンみたいな力技じゃなくて
証明で簡単に解けそうな気がするんだが…

まぁどっちも証明されたことには違いないからどうでもいいわけだが

四色問題の二の舞いだな。

>>7

四次元的な天才だな、おまえ。

１手の定義がわからん。

90ﾟ回転を１手と数えるならば180ﾟ回転は２手なのか？

これはすごいな

こういう力業で解答出すのは気に入らん
もっとエレガントに出来ないもんかな

>>54
「解き伏せてやったぜえぇぇ！！」っていう壮大な感じは好きだな。

まあ、数学者はエレガントな方法を好むかもしれないが、
数学者のような世間知らずのニートの引きこもりの感情欠如のあるいみ廃人以外には、
コンピュータ使ってでも解明した方が偉いって事になる件。

>>56
とりあえずお前が何にも分かってないことだけは分かった

俺のＰＣでシュミレーションしたら２４手なんだけどなー
変だな

おれはどんな女が相手でも3手が限界

うそーーん
一度も全部そろえたことないよー

自分も、解無し、というルービックキューブがあるはずだと信じている。

買った時は全面揃っていたんだけどね。

ルービックキューブのソルバだw

http://jp.youtube.com/watch?v=htnL1KTpaY8

すげえ
まさに26手で完成？

「Rubik's cube」を26未満の移動によって各面がそろった状態に戻す事が
可能だ、という事が証明しなさい。

これが何の役に立つのかわからない俺ｶﾜｲｿｽ

一晩で４８手は無理

>>62 Legoだ！

昨日テレビでルービックキューブのチャンピオンが言ってたよ。
全パターン暗記しているって。

>>61
バラした？

何かの計算まちがえだろ
そんなわけない

>65
3次元化された暗号がどうのこうのって研究があるらしい。

それはともかく、映画キューブシリーズ良さが良くわからない。
すごく怖かったけどね…

>>7はもっと評価されるべき

2001年宇宙の旅は素晴らしい映像映画だった。

>>73
キューブリックと答えて欲しいんだろう〜。ん〜。
何恥ずかしそうにしてんだよ。
素直に欲しいって言えよ。
そのすました口で言ってみろよ。
欲しいですって。
ん〜。

スパコンの解析がただの総当たりだと思っている奴が意外と多いな

一面揃えたところで飽きる俺ｶﾜｲｿｽ

これ揃ったキューブから何手で他のパターンと被るか見てった方が早くね？

プロルービックなら63時間も要しない
よってスパコンは馬鹿

ルービック・キューブが流行ったとき、
６面そろえられるやつは勉強ができない法則というのはあった。

　＞１はスパコンをおもちゃと勘違いしてる

>>79
その逆だった

>>80
夢のない奴だ

>>80
PS2のことだよ

中心のブロックって、どうやっても表にでてこないよね？

1980年、魔法のパズルに逢ったようだった。
このニュース味気ないというか、
スパコンってなんか夢砕くね。

こんなことで給料が貰えるなんてうらやます

>>54
> こういう力業で解答出すのは気に入らん
> もっとエレガントに出来ないもんかな

多分だが、

・いかなるルーピックキューブ状態へも、揃った状態から最長でも26手で作れる

という事を証明したのだろう。これは「いかなる状態からでも、26手で揃えることが可能」と同値。
ただし、実際に逆変換するのは難しいだろうなぁ。
ていうか「どうすれば26手で戻せるかを探すルーチン」はかなり難しい。

簡単だよ

>>54
> こういう力業で解答出すのは気に入らん
> もっとエレガントに出来ないもんかな

エレファントに解いた。

将棋は未だに必勝法が発見されていないばかりか、人間のトッププロに歯が立たない
分岐の数は全部で１０の２２０乗通りとか聞いたが

１グーゴル以上あるのかよ・・・
どうあがいても解析しきれないな

>>87
東京ガス、よろしく。

>>89
エレファントなら一発でばらばらに出来るからな

ルービックキューブってそろえるための法則や定石ってあるの？
たとえばこのコマと裏側のコマをほかのコマに影響させずに入れ替える。とか。
俺もチャレンジしたことがあるけど、何をしていいのかが分からない。

>>94
みんな定石覚えて6面そろえるんだよ

マイナスドライバでキューブをバラバラにしてから、組み立てていたオレが登場

解明と証明では違うからな。
原理が解明されたが、絶対に間違いないと証明されないことは沢山ある。

いやはや、すばらしい研究だな。
この研究結果のもたらす社会貢献度はスゴイ！

これからもスパコンでいろんな研究して人類に貢献して欲しい。

26手ってｗ
セロは1手だぞｗ

>>94
やり方を覚えれば誰でも全面揃えられるよ。
ｗｅｂで調べたらやり方が書いてあったので、その通りにやったらホントに揃ったので驚いた。

正直スパコンの限界を感じる

>>21
あと数年で魔法使い

29手かかりそうに見えて、２６手で済む証明にスパコンが必要な配置って、どんなのか興味ある。

俺もどんな状態からでも26手以上で揃える自信あるよ

360度回転させるのは一手としてカウントしていいのかな？

>>87
いや>>54は
「8×8のチェス板の、一本の対角線上の2マスを取り除いた62マスを
1×2のドミノ板で覆うことはできない」
という問題のエレガントな解答みたいなのを求めてるんだろう。



解答例
62マスを白黒で市松模様に塗り分けると、白黒それぞれ30マスと32マスに
なるので、白黒1マスづつからなるドミノ板で覆うことはできない。

>>105 されないでしょ。
けどまじで180度は一手でしょ。

でな、中段を回すのは一手？なんでしょうね。


　□□□
　□□□←　
　□□□

ならば>>37がいう26手の回し方全組み合わせは
　　　(27)^26
になるよな。この中に4325京種類の状態が含まれる
という事だな。

六面の色がそろった状態って、各ブロックの配置も常に同じなの？
それとも何通りかあるの？

>>108
各頂点のブロックの色の組み合わせは変えられない。
だから一通り。

>>109
各面中央のキューブの回転があるんじゃない？
キューブの各面に／を入れると、難易度が上がるって聞いたことがある。

動かすごとに、全ての色が語ごろっと変わる。解けるかな？

ごめん。「語ごろっと」→「ごろっと」

>>1
26手未満か以下かはっきりしろ！

六面揃えられない俺にしたら些末な問題だ。

各6面の中央のコマはどんなに回しても入れ替わる事はない

>>115
そういう意味じゃなくて

パターン１
　　　　　　　↑色１
　□□□
　□▲□　　→色２
　□□□
　　　　　　　↓色３

パターン２
　　　　　　　↑色１
　□□□
　□▼□　　→色２
　□□□
　　　　　　　↓色３


見たいな組み合わせってありえないのか？って意味だと思うぞ。

直感的にはなさそうに思うが。

>>116
縦に180°回転させ、横に180°回転すれば、そのようにはなる。
ただし「各ブロックの色の配置」は変化しない。
そしてそのような「逆位置」にしたときに6面揃えられるのかはわからない。

つまり、人間のルービックキューブのタイム争いは”器用さ選手権”ってことか

「スパコンでやるほどのことかよ」と彼らは語るのであった

>>117
ｽﾏﾝ、言葉が足りなかったが、俺の言いたい話ってのは、
※「６面揃った状態で、こういう逆位置状態はありえるか」って話。

15パズルで、通常状態と14-15入れ替えた状態は互いに通常の手段で移行できないのと
同じ様な感覚で、※はありえないとなんとなく思う。

1層ずつ揃えていくやり方を知ってれば
>>116は出来るってのが直感的に理解できるよ。
最初の1面の最初の角をどこにするかで決まる。
試しにルービックキューブ買ってやってみれ。白面の真ん中に絵が付いてるから
向きがわかりやすい。

>>120
>最初の1面の最初の角をどこにするかで決まる。

あ、なるほどそういうことか。理解した。サンクス。

>>7をギャグだと思ってる奴がいるが
５面揃って最後の一面が揃わないという状態はありうる
すごく、悔しいんだよ

>>122
ちゃんと確認してみ
6面そろってるから

残りの１面に何が集まっているのかを知りたい。

>116 あるよ

俺の友人が3時間でプロフェッサーキューブを完成させたのには驚いた。

マスコミはヒットしている商品とか最新の事件とか旬な話題しか追わない。
「ニュース＝新しいものの集まり」だから。
時が過ぎれば、「そういえばそんなおもちゃもあったな」となってしまう。

だがネットは異なる。
ある事件・現象に関して興味を持つ奴が集まって、白熱した議論が延々と繰り広げられている。
ネットがなければ近年のルービックキューブ・ブームなど起こりえなかったであろう。
1980年には「ルービックキューブが流行りました」と懐かしそうにメディアが伝えても効果は小さい。

>>116
は感覚的にはありそうな気がする。
>>7
これは・・・ある。

>>7

裏面が露出すると、そうなるよな。

子供の頃、買ってもらった
しかしわしが触る前に母によってぐちゃぐちゃにされてしまい結局元に戻せなかった

あんなでも26手で直せたのか…

>>127
×ヒットしている商品とか最新の事件とか
○ヒットさせたい商品とか局にとって都合の良い事件とか

3x3が26手以下か。


NxNの場合、の手数をNで表すことは可能なのだろうか。

2x2の最小手数は解明されているんだろうか。

2n＝26
もう一個式くれ。

昔友達がルービックキューブを持ってた。貸して欲しいといって貸して貰った
のだが、何日どころか１月たっても上手くそろえることが出来なかった。
いつまでも借りてるのもなんだと思って、とうとう諦めて返しにいったら、
出来ないだろうといわれた。降参だどうやればいいのか、やって見せて欲しい
といったら、これは不可能なんだよ、部品を組替えてあるんだからと言われた
とき、思わず。。。。

自首する？w

1: ばらす
2-9(8手): 下の段を組みなおす
10-13(4手): 中央の段を組みなおす
14-21(8手): 上の段を組みなおす
計21手

そんなことよりキューブの構造が不思議なんだがな

>>135
それが妻との出会いでした

Ｎの３乗−１かな？

もしくは
Ｎの３乗−（Ｎ−２）の３乗

初めて手にした日から20年以上たってもいまだに6面揃わない

俺は8色目がうまくいかない

1手.立方体の一面にペンキを塗る
2手.同上
3手.同上
4手.同上
5手.同上
6手.同上　完成

5面なら揃うんだが・・・

26手以下で揃える方法を全部覚えとけば世界チャンプじゃん
簡単簡単

なんて無駄な研究ｗ

>>144がツッコミを待っている件

>>96
あれ？俺がいる

テンビリオンは?

>135
出来ないなんてありえない。だまされたんだよ

>>145
そう思っていた時期が俺にもありました。
http://jp.youtube.com/watch?v=HDG6ZTYartI

２６手って馬鹿か
俺は２手で揃えられる

>>7
5面のみ揃った6面体って…存在するの？ｗ

>>153
どうやらマヌケは見つかったようだな・・・・・

>>151　何回まわしてんだよﾔﾚﾔﾚ
26手でﾋﾞｼｯと揃えろよ！

>>153
>>7だけに突っ込むなんて…憐れな>>144

最長の２６手かかるのが何種類あるのか詳細希望

こういうのってさ、凡人が取り組んでるから答が出ないけど、
世界トップクラスの数学者が本気出したらすぐ解けちゃったりするわけ？

数学者が本気出してすぐ解ける程度ならスパコンを使わなくとも解けるって。

>>153
前５面そろったという人がいた
見てみたら一面９個のうち５個が同じ色だった

No1から全て読ましていただきました。
面白いお話の中に、時々マジなものがあるようで楽しかったです。
実は自分は、今思えば無謀ながら、最短手数をもとめることを目刺し、
それはできなかったものの、それなりの解読プログラムを搭載した、
誰でもが画面で操作できるルービックキューブを先ごろ
公開した者です。今日、「最短手数、解、ルービック」をキーに検索し
ここにたどり着きました。ごちゃごちゃになってもすぐResetもできます。
一度試してください。
java　applet　仕様です。また少し大きなデーターを持っていますので
ロード時に時間がかかるかもしれませんが宜しくお願いします。
http://www.geocities.jp/tsuyoshik1942/rubikcube2.html

さっき日テレでやってたけどアレがそうなのかな

26 って 13 * 2 なんだけど、それと関係あるのかな。

なんとうか、力業すぎるだろｗｗ

俺がガキだったころ、絶対に揃えられなくて
どうしようもなくなったときに親父に渡すと
とっかに持ってって戻ってくると全部揃ってたんだよ
どうやってんのか不思議だった
ある日どうしても知りたくて聞いたんだ
そしたら>>96だった

>>165
普通に解法は存在するのに。

age

こういうプログラムを書いた奴らにキューブを渡してじゃあ解けるか
というと、必ずしもそうでないというのが実状ではないかと思う。

この研究が次に何につながるってんだろう。
一見してクズ研究と思っちまうが
擁護できる人いたら解説プリーズ。

この研究者、あっさり記録破られて涙目ｗｗ

>>168
このプログラムを組むより、既に解法のあるキューブを解く方が遥かに易しいよ。

最近久しぶりにキューブやってみたらちゃんと6面揃えることが出来たよ。
最初に覚えてから27年も経っているのに出来るなんてガキの頃の
記憶って凄いなと感心したよ。

ルービックキューブやりたくなってきた