ルービックキューブ
立方体が上下方向左右方向前後方向にそれぞれ3分割され、上下左右前後各面が回転できるようになったパズル。
世界配色基準では、上が黄、下が白、左が青、右が緑、前が赤、後が橙となっている。
https://gyazo.com/f8002e7fea3ace7afba54139e0b6b29b
日本で販売されていたものは、上が青、下が白、左が黄、右が緑、前が赤、後が橙となっていたが、2013年に発売されたルービックキューブver2.0からは配色が世界標準のものに移行された。
また、2000年代に特許が失効して以降は中国製の類似商品が販売されている。その中には内部構造の工夫によりタイムアタックに適した物がある。
ルービックキューブに関する議論において、U, D, L, R, F, B という略称が用いられる。
これはUが上、Dが下、Lが左、Rが右、Fが前、Bが後を表す。また、これらの記号はそれぞれの面を90度右回転させる操作も表す。回転を表す記号体系では、 U' のようにダッシュ記号をつけることで90度左回転を表し、U2 のように2をつけることで180度回転を表す。
UU=U2、DD=D2、LL=L2、RR=R2、FF=F2、BB=B2
UUU=U'、DDD=D'、LLL=L'、RRR=R'、FFF=F'、BBB=B'
ルービックキューブが回転操作によって揃えることができる任意の状態$ Sにおいて、その状態からキューブを揃えるまでの操作回数の最小を最短操作回数$ n(S)とする。最短操作回数の最大$ \max_S n(S)を神の数（God's Number）と呼ぶ。
180度回転を1手と数える場合、神の数は20、180度回転を2手と数える場合、神の数は26であることが示されている。20, 26 ルービックキューブを分解すると、頂点パーツ8個、辺パーツ12個、そして中心パーツが得られる。中心パーツは6面の中心がキューブ全体の中心に接続された物で、1つのパーツとして得られる。分解したキューブを組み立てる際に頂点パーツの位置は$ 8!=40,320通り、頂点パーツの向きは$ 3^8=6,561通り、辺パーツの位置は$ 12!=479,001,600通り、辺パーツの向きは、$ 2^{12}=4096通りあり、ルービックキューブの取りうる状態の数は以下のようになる。
$ 8!\times3^8\times12!\times2^{12}=519,024,039,293,878,272,000\approx5.19\times10^{20}
この中には回転操作のみによって（分解せずに）揃えることができない状態も含まれている。詳細は次に述べるが、回転操作のみによって揃えることができる状態の数はこれを$ \frac{1}{12}した$ 43,252,003,274,489,856,000\approx4.33\times10^{19}通りである。
回転操作のみによって揃えられる状態について考えるために、頂点パーツの向きと辺パーツの向きを見分ける方法を用意する。以下の図のように頂点パーツと辺パーツに印をつける。
https://gyazo.com/d7129d4795f7670c86449a7d64ba4185
頂点パーツの印は、上面Uと下面Dにのみつける。
辺パーツの印は、各面の中の行や中の列を回転させても印の配置が変わらないようにつける。すなわち、各辺パーツに1つずつ印をつける際に、同面同行には1つの印を、同面同列には1つの印をつけ、各面の印が2つになるようにする。
各パーツの向きを定める際に、キューブが揃っている状態の時と同じ位置を$ 0とする。頂点パーツが向き$ 0から右方向に120度捻った向きになっていればその頂点の向きを$ 1とする。また、頂点パーツが向き$ 0から右方向に240度捻った向きになっていればその頂点の向きを$ 2とする。
https://gyazo.com/e88bb9cdd4451bf34a080fd5612438fd
辺パーツの向きは2通りなので、$ 0でない方の向きを$ 1とする。
頂点の向きの総和を3で割った余りは任意の回転操作に対して0のまま保存される。
U回転によって、頂点の向きは右隣の頂点の向きに移動する。
U面の各頂点の向きが、ある頂点を始点として右回りに$ (a,b,c,d)である時、U回転させると、各頂点の向きは$ (d,a,b,c)になる。
このため、U回転によって頂点の向きの総和は保存される。
D回転によって、頂点の向きは右隣の頂点の向きに移動する。
D面の各頂点の向きが、ある頂点を始点として右回りに$ (e,f,g,h)である時、U回転させると、各頂点の向きは$ (h,e,f,g)になる。
このため、D回転によって頂点の向きの総和は保存される。
L回転によって、
R回転によって
F回転によって
B回転によって
辺の向きの総和を2で割った余りは任意の回転操作に対して0のまま保存される。