ルービックキューブを揃えるためのプログラムを探しています!!

Question

ルービックキューブを２３手以内で揃えられることが証明されたそうです。

そこで、実際に“どのような状態からは何手で揃う”というのを教えてくれるプログラム（ソフト）はないかと探しているのですが、見つけることができません。
どなたか良いサイトをご存知の方は、教えて下さい。

また、これは何を用いて考えられているのでしょうか？
群論というものですか？？

Ishiwara · Accepted Answer

＃２,４です。
ご参考になるか分かりませんが、私の解法を簡単にご紹介しておきます。

先日、テレビで名人クラスの演技を見ましたが、私の方法より４～５倍以上も速く、手順もまったく異なっていました。思うに、手順を短くしようとすれば、それだけパターンの暗記項目が増えるようです。私の方法は、暗記項目が比較的少なく、完成以来３０年のブランクがありましたが、今でもスラスラと難なくできます。

第１段階：頂点コマ（８個）の完成。これは＃５さんが挙げた２×２×２のものと、まったく同じことです。実物が市販されていますから、手にとって研究されるといいでしょう。見かけよりは、手こずりますが。

第２段階：互いに反対側にある２面の完成。まず２つの面心コマを合わせてしまえば、残りは８個の辺心コマです。この段階が最も簡単です。

第３段階：上記２面に挿まれたリング状の８個のコマの完成。ここは８種ほどのパターン分けが必要になります。ここで６色を３色とみなします。反対側にある色を「同色」とみなすと、パターンの種類が激減します。とにかく「見なし同色」のまま完成してしまうと、最後の修正は、極めて簡単です。（手数が多少長くなってもよければ、パターン分けをしない方法もあります。）

完成時に「数芸パズル」という雑誌に掲載してもらいましたが、これは学問的に高度な雑誌でした（現在は廃刊）。これに対して、私の論文は「できた！」という報告にすぎず、数学的な裏付けが希薄なためか、読者から何の反応もありませんでした。今でも、数芸パズル誌についてのWEBページは多数ありますが、私の報告に関する言及は１件もありません。

ご成功を祈ります。

kabaokaba · Answer

とりあえず論文を読んでみればどうです？
読んでどういう仕組みか自分で分からなければ先には進めません．

No.2さんのご意見が極めて妥当だと思います．
状態とその遷移規則の表現が一番厄介でしょうね．
9マスの「丸バツゲーム」とか，将棋や詰め碁
数独とかの解法プログラムと本質的な機構は同じかも
＃膨大な状態空間から適宜枝仮りをするという意味．

普通のルービックキューブだと困難なので
2*2*2の小さなもので考えるのも手でしょう．

少しだけ数学ちっくに考察．

2*2*2だと一個の状態を表すのには
表面積の分，24個のパラメータが「最大」で必要．
この時点で「可能な状態の個数」は最大 24! 個
つまり，24個のものの並べ替え．数学でいうところの
24次置換群 S_{24}．

しかしこれは大きすぎ．実際には24!個もパターンはなく
一個のパターンに付き24個の重複がある
（同じパターンを回したりすることで同じものを
24回数えてしまっていることを意味する）
有限群論の「正六面体群」に相当．これをDと書くことで
考えるパターンは剰余群S_{24}/D（位数23!）まで抑えられます．

さらに，2*2*2の場合，「角」しかなく，角のパーツは
角にしか移動できないので，その分の束縛もあるので
更にパターンはへる．

こうしてできあがった群には生成元があるはず．
この生成元を一手による状態遷移に対応させるようにとれるはず．
生成元の集合をGenとする．

揃った状態をスタートの状態 e として，
eに対するGenの元の作用の結果が
「揃った状態」から一手で移る状態になる．

そう考えると，ルービックキューブの「状態」とは
eからGenの元の作用で遷移したものとみなせ，
ルービックキューブが解けるとは
「Genによる作用が推移的である」ことを意味する．
おそらくこれはものすごく難しいというわけではない気がする．
しかし，群論の知識はそれなりに必要だと思う．

さらに，状態遷移のグラフに表せば
そのグラフの位相幾何的な性質が何かを表現してることも
想像がつく

と，まあ・・・まじめに計算するとかなりつらそうなというか
余暇ではできなさそうなので
これにて・・・

Ishiwara · Answer

＃２です。
最短手数の証明などに使ったアルゴリズムは、おそらく解の実行プログラムには役に立たないでしょう。純数学的なアプローチは、将棋で言えば、初手から「香」が１つ上がる手も吟味するようなもので、実線の指針としては使えないでしょう。ただし、もし完成して、とんでもなく速いコンピューターができれば、それこそ絶対に勝てるプログラムとなります。

もしルービックキューブを実践的に解くプログラムを作りたければ、まず試行錯誤で「必ず完成する手順」を見出し、そのアルゴリズムをプログラムに展開するのが、最も賢明だと思います。もちろん、アッと驚くアルゴリズムが発見されて、容易にプログラムに乗ってしまう、という可能性が絶対にないとは断言できません。例えば「ニム」などというゲームは、その類のものです。

私の解法は、標準で100手ぐらい（所要時間で２分ぐらい）です。このくらいなら「凝り性」の方は、開発可能ではないでしょうか。手順開発よりも、状態や操作の記述のほうが、ずっとたいへんのように思われます。

kabaokaba · Answer

>ルービックキューブを２３手以内で揃えられることが証明されたそうです。

この結果を出した
Tomas Rokickiさん（dvipsの作者として著名）の当該論文は
http://arxiv.org/abs/0803.3435
でPDFを入手できます．

以下，入手して数分眺めた印象のみです
精読してませんので，いい加減な感想です．

中身ですが・・・ざーーっと眺めた限り
数学というよりもやっぱり情報工学っぽい感じですね．
つまり，「数学的なエレガントさ」ではなく
「こんな風に総当りすれば解けるはず」という
アルゴリズムを作って
コンピュータにがしがし計算させる感じ．
ぱっと見て使われてそうな数学は
「グラフ理論」のように見えますが，
これはアルゴリズムでは普通にでてくるものですね．
あと20手未満にはできないだろうということも書いてます．

このアルゴリズムを実装しても多分「普通の感覚で」思うところの
「解いてくれるプログラム」にはならない気がします．
そういうプログラムを実装するのは
また別の困難がありそうです．

Ishiwara · Answer

自分で解法を編み出した者の一人です。方法は、私の頭の中に「非数学的な」記述法で入っていて、説明はとてもたいへんです。具体的なプログラムを作ろうとしたことがありますが、「状態」と「着手」の記述がとてもややこしくて、放り出したままです。

今回のご質問で、考えられることは、次のとおりです。

(1) 多分、英語の文献以外にはないでしょう。キーワードとしては、math recreations と思います。ざっと、数万件はあるようです。

(2) 最短手数に関する研究からは、具体的な着手法はまったく得られないでしょう。具体的な着手を調べて行って最短手数に到達する、というものではないからです。最短手数の研究は、抽象的な数式が並んでいるだけで、私たちが読んでも、一言半句も理解できないでしょう。

(3) ２６手というのは「天文学的」に大きな集合であり、枝分かれ手順の全貌は「記憶」できないだけでんなく「記録」もできないと想像されます。

参考URL：http://www.newscientist.com/blog/technology/2007/08/rubiks-cube-solvable-in-26-moves-or.html

ymmasayan · Answer

↓には２５手と書いてあります。

群論みたいですね。
位相幾何学という話も聞いたことが有るような。

参考URL：http://ja.wikipedia.org/wiki/%E3%83%AB%E3%83%BC%E3%83%93%E3%83%83%E3%82%AF%E3%82%AD%E3%83%A5%E3%83%BC%E3%83%96

ルービックキューブを揃えるためのプログラムを探しています!!

＃２,４です。

とりあえず論文を読んでみればどうです？

＃２です。

>ルービックキューブを２３手以内で揃えられることが証明されたそうです。

自分で解法を編み出した者の一人です。

↓には２５手と書いてあります。

この回答への補足

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング