パズルとコンピュータと数学

6面そろっている状態で、標準的な位置に置いて、 例えば、 RURF と操作してみましょう。
このとき、F'R'U'R' と操作すると、最初の状態に戻ります。 R に対しては、 R' とすると、元に戻る。 互いに逆元である といいます。 UR の逆元は R'U'です。一般には U'R'ではありません。 操作の逆だということを考えてみてください。 スクランブルされた状態 A(6面がそろっていない状態) から 6面がそろっている状態 O にするためには、 O から A になるために行った操作の逆を辿ればいいですよね。 A の状態をみたときに、それがどのような操作の結果なのかを知ることができれば、 ルービックキューブは解けることになります。 ただし、この解法は現実的ではありません。
ルービックキューブの操作は 群をなす といいます。
操作をすると、とんでもないことが起こらない。 そして、何よりも 逆元 が存在します。
コーナーキューブの動きだけ見てみても、 キューブの操作は、置換群の一部 であると私たちはいいます。
R という操作を行ったあとのコーナーキューブの位置を記録します。
表 1 Rによる置換
O
R
い の位置にあったキューブは き の位置に移った
う の位置にあったキューブは い の位置に移った
という意味です。 これを R による置換 といいます。
練習してみましょう。Uという操作を行った後はどうなりますか。 実物なしで,紙に書いてある立方体の図だけでできたら,立体図形のセンスがありますね。
表 2 U による置換
O
U
R' の結果はどうなるでしょうか。 実際にやらなくても、また、頭の中で想像しなくても、 表1を 下から 上に辿るとできます。 (必要があれば 上の段のあいうえ順に 並び替えるだけです。) これが、操作の 計算に 相当します。
表 3 R' による置換
O
R'
R につづけて U を行った結果はどうなるでしょうか。 実際にやらなくても、また、頭の中で想像しなくても、 表1 と 表2 から導くことができます。 これも、操作の 計算に 相当します。
例えば、く の位置のキューブは R によって、う に移り、 Uによって、えに行くので、結果
表 4 RU による置換
O
RU
U につづけて R を行った結果はどうなるでしょうか。 計算してみましょう。
表 5 UR による置換
O
UR
表4 と 表5 は一致しませんね。 これは RとU は非可換である といいます。
では全部非可換かというと、 RとL は可換です。
このルービックキューブの操作は、 R, L, U, D, F, B とその逆の12種類あります。 操作だけ考えると、場合に限りがありません。 12文字でできる文字列に限りがないからです。 しかし、キューブの状態は有限しかありません。 また、先にみたように RL と LR は等しいですし、 RL' は全体として左右方向を軸として90° 回転させていることと同じで、 つまり、何もしていないことになります。 他にも一連の操作では、違うものなのに同じ効果をもたらすもの があるということです。 それを、操作の関係 といいます。
あとで、ちょっと見てみますが、 コーナーキューブの位置が同じでも、 面の色は異なる場合があります。 それでも、キューブの状態は有限です。 実は、3x3x3 の場合、どんなにスクランブルされている状態でも、 多くて 20手(この場合の 手 は,長さ20 の一連の操作という意味です。) あれば、初期状態に復元できることが証明されています。
この計算を、コンピュータ上でできるようにしたものが、 これです。 R, L, U, D, F, B のキーを押すと、その操作を実行します。 例えば、R' をさせたかったら、ALTキーを押しながら R を押します。 コンピュータを使ってキューブを操作して(シミュレーションという)、 できるだけ多くの場合を記録しておけば、逆を辿って問題は解けます。 ただ、それは現実的ではありません。
一連の操作によって、 どのようにキューブの状態が変わるかを知識として持っておいて(手)、 現在の状態を分析して、適した手を用いて 元の状態に近づけていきます。 もっと、具体的には、8個のコーナーキューブ、 正確には24個の面の色について、 ほんの一部だけ変わるような、一連の操作を見つけておいて、 それを 手 として持っておくことになります。

つづく