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

質問

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

そこで、実際に“どのような状態からは何手で揃う”というのを教えてくれるプログラム（ソフト）はないかと探しているのですが、見つけることができません。
どなたか良いサイトをご存知の方は、教えて下さい。

また、これは何を用いて考えられているのでしょうか？
群論というものですか？？

回答No.6

Ishiwara · ベストアンサー

＃２,４です。
ご参考になるか分かりませんが、私の解法を簡単にご紹介しておきます。

先日、テレビで名人クラスの演技を見ましたが、私の方法より４～５倍以上も速く、手順もまったく異なっていました。思うに、手順を短くしようとすれば、それだけパターンの暗記項目が増えるようです。私の方法は、暗記項目が比較的少なく、完成以来３０年のブランクがありましたが、今でもスラスラと難なくできます。

第１段階：頂点コマ（８個）の完成。これは＃５さんが挙げた２×２×２のものと、まったく同じことです。実物が市販されていますから、手にとって研究されるといいでしょう。見かけよりは、手こずりますが。

第２段階：互いに反対側にある２面の完成。まず２つの面心コマを合わせてしまえば、残りは８個の辺心コマです。この段階が最も簡単です。

第３段階：上記２面に挿まれたリング状の８個のコマの完成。ここは８種ほどのパターン分けが必要になります。ここで６色を３色とみなします。反対側にある色を「同色」とみなすと、パターンの種類が激減します。とにかく「見なし同色」のまま完成してしまうと、最後の修正は、極めて簡単です。（手数が多少長くなってもよければ、パターン分けをしない方法もあります。）

完成時に「数芸パズル」という雑誌に掲載してもらいましたが、これは学問的に高度な雑誌でした（現在は廃刊）。これに対して、私の論文は「できた！」という報告にすぎず、数学的な裏付けが希薄なためか、読者から何の反応もありませんでした。今でも、数芸パズル誌についてのWEBページは多数ありますが、私の報告に関する言及は１件もありません。

ご成功を祈ります。

お礼

お礼が遅くなり申し訳ありません。

３度の回答、本当にありがとうございます。
とても参考になります。

手順を短くすることを第一に考えるのか、覚えるパターンを少なくすることに重点をおくのか、その点についても考えているところでした。

Ishiwaraさんの方法は、私がこれまで調べたものとはまた違っていて、本当にたくさんの解法があるのだと改めて感じました。

自分のプログラムが組めるように、頑張って学習を続けたいと思います。

回答No.5

kabaokaba

とりあえず論文を読んでみればどうです？
読んでどういう仕組みか自分で分からなければ先には進めません．

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による作用が推移的である」ことを意味する．
おそらくこれはものすごく難しいというわけではない気がする．
しかし，群論の知識はそれなりに必要だと思う．

さらに，状態遷移のグラフに表せば
そのグラフの位相幾何的な性質が何かを表現してることも
想像がつく

と，まあ・・・まじめに計算するとかなりつらそうなというか
余暇ではできなさそうなので
これにて・・・

お礼

お礼が遅くなり申し訳ありません。

回答ありがとうございます。

数学的な解法を考察するために、群論の学習も行っています。
また、プログラム上でルービックキューブの状態をどのように表すのか、
あり得ない状態を含まないために何を考えなければならないのか、
課題も多いですがプログラムを実現できるよう頑張りたいと思います。

回答No.4

Ishiwara

＃２です。
最短手数の証明などに使ったアルゴリズムは、おそらく解の実行プログラムには役に立たないでしょう。純数学的なアプローチは、将棋で言えば、初手から「香」が１つ上がる手も吟味するようなもので、実線の指針としては使えないでしょう。ただし、もし完成して、とんでもなく速いコンピューターができれば、それこそ絶対に勝てるプログラムとなります。

もしルービックキューブを実践的に解くプログラムを作りたければ、まず試行錯誤で「必ず完成する手順」を見出し、そのアルゴリズムをプログラムに展開するのが、最も賢明だと思います。もちろん、アッと驚くアルゴリズムが発見されて、容易にプログラムに乗ってしまう、という可能性が絶対にないとは断言できません。例えば「ニム」などというゲームは、その類のものです。

私の解法は、標準で100手ぐらい（所要時間で２分ぐらい）です。このくらいなら「凝り性」の方は、開発可能ではないでしょうか。手順開発よりも、状態や操作の記述のほうが、ずっとたいへんのように思われます。

お礼

２度も回答をいただきまして、本当にありがとうございます。

Ishiwaraさんがおっしゃるように、自分で「必ず完成する手順」を見出してプログラムにするという方法でやってみようと思います。

＞手順開発よりも、状態や操作の記述のほうが、ずっとたいへんのように思われます。
これは私も感じていたのですが、頑張って取り組みたいと思います。

回答No.3

kabaokaba

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

この結果を出した
Tomas Rokickiさん（dvipsの作者として著名）の当該論文は
http://arxiv.org/abs/0803.3435
でPDFを入手できます．

以下，入手して数分眺めた印象のみです
精読してませんので，いい加減な感想です．

中身ですが・・・ざーーっと眺めた限り
数学というよりもやっぱり情報工学っぽい感じですね．
つまり，「数学的なエレガントさ」ではなく
「こんな風に総当りすれば解けるはず」という
アルゴリズムを作って
コンピュータにがしがし計算させる感じ．
ぱっと見て使われてそうな数学は
「グラフ理論」のように見えますが，
これはアルゴリズムでは普通にでてくるものですね．
あと20手未満にはできないだろうということも書いてます．

このアルゴリズムを実装しても多分「普通の感覚で」思うところの
「解いてくれるプログラム」にはならない気がします．
そういうプログラムを実装するのは
また別の困難がありそうです．

お礼

回答ありがとうございます。

「コンピュータにがしがし計算させる感じ」ということは、4325京以上の配置が考えられるルービックキューブの計算を、一般的に使われているコンピュータで計算することはやはり難しいのでしょうか？

私は「解いてくれるプログラム」をつくりたいと考えているのですが、そのためには何を学習したり調べたりすればよいのでしょうか？

アドバイスがあればよろしくお願いします。

回答No.2

Ishiwara

自分で解法を編み出した者の一人です。方法は、私の頭の中に「非数学的な」記述法で入っていて、説明はとてもたいへんです。具体的なプログラムを作ろうとしたことがありますが、「状態」と「着手」の記述がとてもややこしくて、放り出したままです。

今回のご質問で、考えられることは、次のとおりです。

(1) 多分、英語の文献以外にはないでしょう。キーワードとしては、math recreations と思います。ざっと、数万件はあるようです。

(2) 最短手数に関する研究からは、具体的な着手法はまったく得られないでしょう。具体的な着手を調べて行って最短手数に到達する、というものではないからです。最短手数の研究は、抽象的な数式が並んでいるだけで、私たちが読んでも、一言半句も理解できないでしょう。

(3) ２６手というのは「天文学的」に大きな集合であり、枝分かれ手順の全貌は「記憶」できないだけでんなく「記録」もできないと想像されます。

参考URL：

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

お礼

回答ありがとうございました。

最短手数で揃えられることが証明されたということで、私は具体的にその数値を出すことができるのだと考えていましたが、それは間違いだったのですね………

私もルービックキューブを解くためのプログラムをつくりたいと考えているのですが、「最短で」ということを考えなければ、群論を学ぶことで解くことができるのでしょうか？また、他に方法がありましたら教えて下さい。

回答No.1

ymmasayan

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

群論みたいですね。
位相幾何学という話も聞いたことが有るような。

参考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

お礼

回答ありがとうございます!!

位相幾何学というのは聞いたことがないので、調べてみたいと思います。

補足

質問に補足をさせていただきたいと思います。

実際に“どのような状態からは何手で揃う”というのを２３手以内で教えてくれるプログラム（ソフト）を探しています。

よろしくお願いします。