ルービックキューブ
2008年06月23日（月）19:48｜久末
久末です。
ルービックキューブをやったことがありますか？ 最近私はこの古き良きパズルにはまっています。
ルービックキューブが流行ったのは1980年ころなので、私(31歳)くらいの年代だと小学生とか幼稚園生くらいですね。 私の家にも一つありましたが、2面を揃えるのがやっとで、バラバラにして組み替えて揃えるというチートをよくやりました。
ところでこのルービックキューブ、組み合わせの数はどの程度あるでしょうか？ ルービックキューブをバラバラにしてみると、6つの中心キューブが固定されているのが分かります。 また、角のキューブや角の間にあるキューブはそのキューブがもつ色の組み合わせが固定です。また、全く同じキューブは2つとありません。 このことから以下のように導き出すことが出来ます。
角のキューブ(コーナーキューブ)の組み合わせ
コーナーキューブは8カ所にありますので、色の向きを考えないと 8!(8の階乗 = 8×7×….2×1)通りあります。 また、色の向きが各3通り(3色)ありますので、3^8(3の8乗)通りあります。つまり、コーナーキューブの組み合わせは
8! × 3^8 = 264,539,520通りです
次に角の間のキューブ(エッジキューブ)の組み合わせ
エッジキューブは12カ所にありますので、色の向きを考えないと 12!(12の階乗 = 12×11×…2×1)通りあります。 また、色の向きが各2通り(2色)ありますので、2^12(2の12乗)通りあります。つまり、
12! × 2^12 = 1,961,990,553,600通りです
各面の真ん中のキューブ(センターキューブ)の組み合わせ
センターキューブは固定されているので1通りです。
全体で何通り？
各キューブの位置の組み合わせが分かったので、全体の組み合わせはこれらを掛ければよいということになりますので、
(8! × 3^8) × (12! × 2^12 ) x 1 = 519,024,039,293,878,272,000通り
が、全体の組み合わせと言うことになります。
がしかし、これは、単純に組み合わせた場合の組み合わせで、実は、全面がそろった状態から回転させるだけでは（バラバラにしたりしない）出来ない組み合わせも含まれています。Wikipediaの解説ではこう説明されています。
ルービックキューブ - Wikipedia
- 位置がずれているコーナーキューブの個数と位置がずれているエッジキューブの個数の偶奇は一致する
- 全てのエッジキューブの位置が揃っている場合、向きが異なっているエッジキューブの個数は偶数個である
- 全てのコーナーキューブの位置が揃っている場合、時計回りに向きがずれているコーナーキューブの個数と反時計回りに向きがずれているコーナーキューブの個数は3を法として合同である
1, 2, 3のそれぞれが先ほど求めた全体の組み合わせの、2分の1、2分の1、3分の1ずつ存在するためルービックキューブを全ての色がそろった状態から遷移できる組み合わせは
(全ての組み合わせ) / (2 × 2 × 3) = 43,252,003,274,489,856,000通り(4325京203兆2744億8985万6000)
と言うことになります。(Wikipediaに全部載ってますね…)
何手で揃えられるか
さて、このように組み合わせの数が分かったところで、全ての色がそろっているわけではない状態から最低何手で全ての色が揃えられるのかという疑問がわいてきませんか？この問題の解はまだ出ていませんが、多くとも25手以内に揃えられることが証明されています。また、少なくとも24手かかるパターンがあることも分かっています。
※ 「多くとも25手」は上界(じょうかい Upper bounds)といい、「少なくとも24手」を下界(かかい Lower bounds)といいます。
さてさて、この上界と下界が一致していないのは、まだすべてのパターンで検証されていないからです。この膨大なパターンはコンピュータを使っても膨大な時間がかかりますが、すべてのパターンを一つ一つ上げていくのではなく、工夫すれば少なく考えることはできます。 例えば、全面そろった状態から、上面を一回だけ回したものと、全面そろった状態から下面を一回だけ回したものは、その状態から揃える方法は同じと見なせます。 こうして、同じと見なせるパターンをいくつも考えて、計算量を減らすことで、膨大なパターンを全てあげるのではなく、本質的な部分だけに置き換えていきます。
ここでちょっと数学を。
y = x2
という式があるとき、yの最小値はいくつでしょうか？
答えは0ですね。
さて、何でこんな数式と問題が出てきたかというと、ルービックキューブの問題も数式に置き換えることが出来るからです。 そして、数式が分かれば、その数式でとりうる値の内、もっとも小さい値(とか大きい値)を求めることが出来ることがあります。 その、最も小さい値(とか大きい値)のことをルービックキューブのような問題では最適解といいます。
この最適解を求めるという行為は、産業界でも多く導入されています。もちろん、私たちの生活にもそこそこ密着していて、例えば、ある駅からある駅までの乗り換えはどういう経路が最適かを教えてくれるサービスなどで利用されています(と思います)。
ルービックキューブの問題を解くのは結構大変だと思いますが、めちゃめちゃ難しいというわけでもありません。アルゴリズムに興味があって課題を探しているならちょっと挑戦してはいかがでしょうか？←無責任
では、また。
