ルービックキューブコミュの最短手数とか最適解とか…

スピードキューブ～ＬＢＬなどが今回のブームの核となっているようですが、そういった方法論とは別に昔っからずっと気になってることがあります。

解法の中である状態から最も手数を少なく解いていく方法について言及しているようなもの（論文など）ってありますか？もしくは何手以内で全ての組み合わせを網羅できますって証明されてるんでしょうか…。
どこかでそういったものの予測のようなのを読み齧った気がしたのですが良く理解できずスルーしてた気がするのですが勘違いだったのでしょうか。

プログラムによって解いて行くにしてもそのアルゴリズムとして全ての組み合わせをつぶして行くんじゃあまりにもベタだし…でも、最悪それでも最大何手で全てを網羅って数えた記録ってあるんでしょうか？

崩した逆順が恐らくは最適解に最も近いものですが、それをある状態から求める方法があれば感激的だと思いませんか。最終的にはなんらかＰＣに頼らざるを得ないかもしれませんがね。

当方いわゆる数学の専門ではないですが、高校～大学教養程度なら今でも理解はできると思います。それは群論で…見たいなことを提案いただいたこともあるんですがちょっとそれはわかんないです。ってかその群論で語りきれてることならば勉強してみたいです。

何かご存知の方いらっしゃいますか？

コメント(15)

最初
全て
最新の40件

[2] mixiユーザー 07月29日 14:48

ソースは覚えてないですが、
どんな状態からでも完成までの最短手順は20～22手くらいになると言うのを見た記憶があります。
そのためか、3x3x3の公式スクランブルでは25回回すことで「十分にバラバラ」になるとされているようです。

[3] mixiユーザー 07月29日 14:56

Cube Explorerと言うソフトが、ほぼ最短に近い手順を見つけてくれるようです。
F2L/OLL/PLLなどの新たな手順を模索するときにも使用されるようです。
　
人間では公式に最短手順を競う競技もあって
http://www.speedcubing.com/rankings/ranking2005_fm.html
2005年の世界記録は28手です。
ただ、これは最短手順を見つけるのに数時間をかけるようですが。
それでもすさまじいです。

[4] mixiユーザー 08月01日 04:09

キューブ群の直径(半径?)はまだ証明されてなかったよなー、と思って検索したら、Wikipediaが引っかかりました。
http://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube

「20手(superflip)以上、29手以下とまではわかっている。じゃあ26なのか27なのかと言うと、わからない」ということのようです。Jaap Scherphuisさんのページにも解説があります。
http://www.geocities.com/jaapsch/puzzles/cayley.htm

最適解を求める方法は、現在two-phase algorithmというのが主流で、Cube ExplorerやACubeに実装されています。Cube Explorerは検索しても本家サイトが見つかりにくいので、URL貼っときますね。
http://www.kociemba.homepage.t-online.de/cube.htm

Cube Explorerといえども、基本的にはすべての組合せをつぶしていく方式です。「望みがないことがわかったら早めに次の組合せに移る」「3つの方向から同時に攻める」という工夫によって、99%程度の組合せの探索を省略しつつ「これが最小手順だ!」という解にたどりつけるようになっています。詳しくは上のKociembaさんのページの左フレームにあるリンクから解説を読んでください。手とり足とり詳しく教えてくれるので、高校程度の数学がわかれば理解できると思います。

[5] mixiユーザー 08月01日 04:30

Cube Explorerは最近のPCで動かせば、たいがい1秒くらいで解を見つけます。「最適じゃないかもしんないけど、1秒でさがした範囲でこんなの見つかったよー」という解ですね。本当に最適な解を求めるには最新のPCでも2分くらいかかるようです。あと「99%程度」より「99%以上」の方が表現として適切なような気がしてきました。

[6] mixiユーザー 08月02日 04:24

＞NatcHさん
順方向にしか回してないのを見ると設計上の制約でしょうが恐らく最適解ではなさそうですね。画像処理の時間がかかっているんでしょうか？
映像としては興味深いです。でもロボットと歌うのならばやはり人間のように持ち替えて解いて行くのを見たいですね。

＞こだまさん
よく言われるセンターキューブの向きを除いた組み合わせが
8!・3~8・12!・2~12/3/2/2=43252003274489856000　えと、約4300京？
コレに対して１手目の種類が６面正逆で１２通り。２手目以降は１手目の逆を除く１１通り…って単純じゃないですがザックリと１０通りとすると２０手目でこの数字を超え、直行する８通りだけだとしても２２手目で超えます。
この近辺か少なくともこれ以上だとはわかりますが、途中に同じ組み合わせがどの程度出てくるのかちょっとよくわかりませんね。その辺がどう解かれているのか居ないのかが興味があるんです。

このリストって同じものからの解なんですかね。だとしたら２８手と３２手、他のもそうですが数手しか違わないのに同じ結果に至るって言うのが興味深いです。

[7] mixiユーザー 08月02日 04:38

＞mad-pさん
ああ、このアタリの解説が多分求めてるものに一番近いんだと思います。…英語はあまり得意でないのですががんばって読み解いて見ます。ありがとうございました。
でも予測はおおよそされているが結果はまだ出ていないって事なんでしょうか？ザックリと２０手以上だろうとは上でも書いてわかりますが、２９手以下ってどういう判断からできるんでしょうかね。

ところでキューブ群の直径ってナンですか？
ちょっとシロウトの推測ですが空間に１手置きに配置して組み合わせを埋めてくみたいなもんでしょうか？ルービックキューブだと６次元空間とかになるのかなぁ。わかんないですけど。

数学を専門にやってる方がまだって事は敷居が結構高いですね。２ｘ２ｘ２とかなら高々３００万通りくらいだから考えたらいけそうな気がしてるんですが…。

[8] mixiユーザー 08月03日 01:17

superflipという形は最小手数でも20手かかるのはわかっています。最小手数が21手になるようなキューブ状態はまだ発見されていません。29手というのは、どんな状態からでも最悪でも29手で解けることが保証できる解法があることからわかったものです。

「キューブ群の直径」って書くと数学に詳しい人におこられてしまうので、「ケーリーグラフのdiameter」と言い直しておきますね。Jaapさんのページに絵入りで解説されています。Jaapさんはキューブ状態の対称性からsuperflipが一番遠い状態だろうと予想していますが、実際に誰かが全状態について最小手数を検算してみない限り、21手必要となるものが「存在しない」ことは言えないのです。

以上はWikipediaなどからの受け売りです。

2x2x2は完全に解かれていますよ。ある2x2x2のソルバーは、全状態に対応した最適解の表を持っています。どこのやつだっけかなあ。

[11] mixiユーザー 08月18日 00:26

>ほりあてくん
それは、さては2x2x2用の手順を3x3x3用のCube Explorerにかけたんじゃありませんか? それか、最後まで探索させていないかでしょうね。

2x2x2の全解データは、さがしておきます。Jaap氏のとこから行くんだったかなあ?

>野田さん
14手まで1～2時間というと、ACubeと同じくらいですか? two-phase algorithmを手順発掘用に作ったものがACubeです。ACubeは無視するキューブの情報を知ってから座標変換表や枝刈り表を作ります。
http://software.rubikscube.info/JACube/

[12] mixiユーザー 08月18日 00:28

7/27付でこんな記事が出てました。3x3x3の対称性のある状態をすべて探索した結果、21FaceTurn必要なものはなかったそうです。
http://cubezzz.homelinux.org/drupal/?q=node/view/63

[13] mixiユーザー 08月18日 00:47

Jaapさんの2x2x2ソルバーありました。
http://www.geocities.com/jaapsch/puzzles/javascript/cube2j.htm
起動時に枝刈り表を作って、実行時に探索するGod's Algorithmだそうです。全解をあらかじめ知っているものではありません。

……どこで見たっけ??

[14] mixiユーザー 08月18日 00:56

Jaapさんの紹介文に残っていました:
for Windows, simply has a 20Mb database with all the solutions.

しかし残念ながらリンク切れです。Internet Archiveにもありませんねえ。
http://web.archive.org/web/20050214073815/http://tocomak.com/

見つけたときにセーブしておけばよかった……。

[15] mixiユーザー 10月30日 10:18

Cube Explorerがバージョンアップして、手順発掘に使えるようになりました。URLも変わっています。
http://kociemba.org/cube.htm

OLLやCOLLのような実用的な穴あき問題なら、Cube Explorerの方がJACubeよりも速そうです。

ログインすると、みんなのコメントがもっと見れるよ