ルービックキューブの解法プログラム

質問

私の出身校の後輩が、ハンガリーで行われたルービックキューブの大会で世界一になりました。（縦横奥行き３列の部門）

新聞によると、このタイプのルービックキューブの色の組み合わせパターンの数は、京（兆の次）のオーダーになるそうです。

ふと思ったんですけど、色のパターンを入力したら、自動的に解法（どうひねくりまわせば色がそろうか）を教えてくれるアルゴリズムというか、コンピュータプログラムは作れるんでしょうか。（もちろん有限時間内の最短の道のりで。）

答：作れるにきまってるじゃないか。人間が解けるんだから。ですか？

「知の森」を復活させねばなあ。

回答No.8

goyow

I/O 1981年3月号に横澤信夫さんが「ルービック・キューブ解法プログラム」という記事を掲載されています。BASIC での解法で、最適化されたものではないという断り書きがあります。
　参考文献に、

参考文献
1)神谷真吾：“ルービック・キューブの解き方”I/O,
　　'80年10月号
2)数学セミナー，’80年11月号
3)Ｎ－ＢＡＳＩＣプログラム教本

が載ってます。

回答No.7

stomachman

なるほど。
　ルービックキューブ（もしくはハンガリアンキューブ）は、操作が数学で言う群になるんで、群論の教材としても使われました。3x3x3のキューブを回して作れる可能な色の配置の数は (3^8)(2^12)(8!)(11!)通りです。

　以下、3x3x3の話にします。手に持ったキューブの各面をFront, Back, Left, Right, Up, Downと名付け、それぞれの面を（面に向かって）時計回りに90°回転する操作をF, B, L, R, U, Dと表します。また反時計回りは ' を付けて表します。キューブを上面、中間層、底面に分けて考えます。そして、中間層を右に90°回す（上から見て半時計回りに回す）操作をεと書きます。（最初にアルゴリズムを[論文として証明付きで]構成したのはアン・スコットって人ですけれども、この記法はシングマスターさんが考えたもの。）

簡単な操作の組み合わせだけで色を揃えるには、以下の手順だけで可能です。
(１) 底面の辺のキューブを正しい位置にする。（簡単ですんで省略）
(２) 底面の角のキューブを正しい位置にする。これは、
F'U'F, RUR', F'UF, RUUR'
のどれかの手を使えばできます。
(3) 中間層の辺にあるキューブを正しい位置にする。
URU'R'U'F'UF, U'F'UFURU'R'
を使うことによって、底面を全く変化させずに可能です。
(4)上面の辺にあるキューブを正しい位置にする。ただし向きが狂っていても気にしない。
UFRUR'R'U'F'
を用いることで、中間層、底面を変化させずにできます。
(5) 上面の角にあるキューブを正しい位置にする。ただし向きが狂っていても気にしない。
FDFFDDFFD'F'
で隣接した角にあるキューブを交換することができます。
(6) 上面の辺と角にあるキューブの向きを直す。
(F'RDR')^2, (RF'R'F)^2, (εR)^4
を使うと他の部分が乱れません。( ^n はn回繰り返すという意味。）

　もちろん、各段階で色の並び方を見て、どの操作を適用すべきかを判定する必要があります。それはここでは省略しますが、簡単にプログラミングできることはお察し戴けるでしょう。かつてフリーソフトも見かけたことがあります。という訳で、ご質問への答はYES。

　しかし競技をやる方々にしてみれば、こんなのは初歩も初歩、「バイエル」みたいなもんだろうと思います。彼らはこんな冗長な手順の代わりに、一連の操作から成る特殊な「フレーズ」をいっぱい憶えていて、特定の部分を変化させずに別の部分を素早く動かすために利用するようです。　
　もちろん、「何回操作したか」ではなく「何秒で操作したか」を測るのですから、数学的な最短手順とはまた違った話です。ほとんど自動的に手が動くまでに練習し、さらにキューブが物理的に滑らかに回るように手入れをして、F1マシンのように磨き上げていると聞きます。

　もっと別の、より数学らしい方法も証明されています。その方法では、キューブの配色の状態を、ある計算式で「点数」に変換する。そして、可能な操作(F, B, L, R, U, Dおよびその逆回転)のうちから「それをしたら点数が小さくなるようなもの」を一つ選んで実行する。すると、（ただ一つの状態を除いて）どの状態でも常に「点数をより小さくできる操作」が存在する。（点数を小さくできるような操作が存在しない唯一の状態というのは、もちろん、全ての面の色が揃っている状態のことです。）

　「ある（条件分岐を含む）手順が、どんな状態から始めても最悪何手で各面を揃えることができるか」を考えると、「最悪何手掛かるか」の手数が最小であるような手順を求める、という問題が考えられます。そのためにはまず、「どんな手順を使おうとも最低x手掛かるような状態」とはどんなものか、そしてxの最大値は幾らか、を考える必要があるでしょう。（ANo.6のリンクは「xが25であることを（スパコンで？)証明した」というハナシですね。）
　「任意の状態に対して、最小の手数で各面を揃えるための手順を作り出す」ことができるアルゴリズムを求む、となるとまた別の問題です。もちろん、そういうアルゴリズムは実際に構成できます（総当たりで調べるだけです）が、そのための計算量をどこまで小さくできるか、が本当の問題です。
　他にもいろんな問題が考えられますんで、嘗ての流行時には数学の分野として「キューブ学」なるものを提唱する方まで居たようです。そろそろ復活してもいいんじゃないかなあ。

回答No.6

noname#108554

2chの科学板でそんな話題をみかけました。
残念ながら、アルゴリズムについてはあまり詳しく載せてませんが、
文章の印象だと、ありそうですね。
つまり、「アルゴリズムの存在証明」だけでなく、
すでに具体的にアルゴリズムが構成されていそうです。

参考URL：

http://news21.2ch.net/test/read.cgi/scienceplus/1187539363/l50

お礼

回答ありがとうございます。ご紹介のＵＲＬを見ました。

ルービックキューブがどんな状態（パターン）であっても、26手以内で
色合わせができるということが証明されたようですね。

「スーパー・コンピューターで63時間かかった」という意味は、
26手より多く手が必要なパターンが存在しないのを確かめるのに
それだけの時間がかかった、ということでしょうか。（？）

だとすると「ルービックキューブの解法プログラム」なるものは
お仕着せで人間がコンピュータに与えるしかなく、コンピュータが
解法を教えてくれるわけではない、ということですよね。

回答No.5

Ishiwara

私は、自分で開発した方法で、１００動作前後でできます。自分用のメモは書いてありますが、プログラム作りは断念しました。理屈上は可能ですが、断念の最大理由は、状態・動作と画面表示とのインターフェースの設計が、とても面倒だからです。
コンピューターでやるときは「特定の２つのコマの交換法」を繰り返しせば、プログラムの記述自体は短くなるはずです。しかし実技上の動作数は、とても大きくなります。
もちろん、私の方法は、最短動作数ではありません。理論的な最短動作数は「最大の場合で３０手前後」だという記事を、昔読んだことがあります。

お礼

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

ハンガリーでチャンピオンになった後輩は、新聞報道では、
500種類の解法パターンを暗記していたそうです。

> 「特定の２つのコマの交換法」を繰り返しせば、
> プログラムの記述自体は短くなるはずです。
> しかし実技上の動作数は、とても大きくなります。

プログラムとしてはわかりやすいけど、方法は愚直だということですね。
プログラムとしてもスマートでわかりやすく、手数も最短というのは、
無理なことなのでしょうね。きっと。

回答No.4

unchikusai

#2です。
#3の動画見ました。感動モンですな。
PC-8001の解法プログラムですが、動画を見てちと思い出しました。
PC-8001のプログラムは動画のような３Ｄではなく、１面３×３に区切ったサイコロの展開図のような表示だったと思います。
今手元にありませんが、実家に帰ったときに確認してみます。

お礼

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

> １面３×３に区切ったサイコロの展開図のような表示だったと思います。

ルービックキューブを回転させてとき「コマ」がどう移動するかの
方程式？（変換式？）は、簡単に作れるでしょうけど、６面の色を
きれいにそろえるプログラムは、どうすれば作れるのか、私には見当が
つきません。膨大な解法パターンのデータベースを参照するようなプログラム
じゃ、しょうがないですよね。（チェスや将棋のプログラムはこれに近い？）

回答No.3

looker1986

ありました。関連リンクに1000×1000×1000を解いている動画があります。20×20×20で４時間かかっているので恐ろしく長い時間を掛けているみたいですね。

参考URL：

http://www.youtube.com/watch?v=CruqZhN_5D8&mode=related&search=

お礼

回答ありがとうございます。
時間はコンピュータの性能によりますよね。
スーパーコンピュータなら、1000分の1秒もかからないのかもしれません。
私も質問を出してから気がついたのですが、ポイントは「最短の道のり」を教えてくれるプログラムを作れるのかどうか、じゃないでしょうか。
（数学カテゴリの質問としては。）
トライアンド・エラーで、そろったかどうか途中で確かめながら、試行錯誤するようなプログラムじゃ、しょうがないですよね。（人間と同じ。）

回答No.2

unchikusai

古い話ですが、ルービック・キューブが大流行していた1980年頃、工学社から出ていたパソコン雑誌「I/O」（アイ・オー）にPC-8001用の「ルービック・キューブ解法プログラム」が掲載されていたと思います。
　自分はPC-8001を持っていなかったので、詳細は分かりませんが当時流行していたプログラム、BASICで書かれていました。
　同じ号に「ルービック・キューブ解法」が載っており、それまでは分解して組み直すしか、色を揃えることが出来ませんでしたが、それを見ながら色が揃えるうちに、自分で揃えられるようになりました。

　先日またルービック・キューブに触れる機会がありましたが、解法は見事忘れていました。

お礼

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

> 1980年頃、工学社から出ていたパソコン雑誌「I/O」（アイ・オー）に
> PC-8001用の「ルービック・キューブ解法プログラム」が掲載されていたと思います。

うーん、いい話ですねえ。（私は懐古趣味者なんです。若き日が懐かしい。）

このプログラムは、囲碁や将棋のプログラムと比べたら、特段に、ものすごく簡単なロジックになるんでしょうけど、その方程式（？）が、私には、皆目見当がつきません。

回答No.1

looker1986

どこかで１００×１００ぐらいのルービックキューブを解くプログラムを見たことがあります。最短かどうかは知りませんが・・・。