Pocket cube について

数学１班 守澤秀亮 藤⾕佑 ⼾部尚征 藤原亮空
指導教員 瀬々将吏 先⽣

1. はじめにポケットキューブとは、俗に⾔う2×2×2のルービックキューブのことであり、ラリー・ニコルス⽒が考案、開発したものである。ルービックキューブが20⼿以内に必ず解けることを知り、興味を持った我々は、そのことが本当なのかを確かめたいと思ったが、ルービックキューブのすべての配置の仕⽅が4000京通りを超え、膨⼤にあることから断念し、すべての配置の仕⽅がルービックキューブよりも少ないであろうポケットキューブを題材とした。

2.⽬的
ポケットキューブの最短⼿数の最⼤値「God’s number」を求め、数ある最短⼿数から法則を⾒つけ出す。「God's number」とは、ルービックキューブ最短⼿数の最⼤値のことで、「God’s number」= t とすると、ルービックキューブはどのような配置でも t ⼿以内で必ず解ける。以下のサイトにはポケットキューブの「God'snumber」は11⼿であると記載されていた。
※ IT⽤語の解説+判じ絵 https://www.daido-it.ac.jp/~oishi/TH5/rubic.html

3.実験⽅法
I.
II.

III.

総配置数(ポケットキューブの全配置の総和)を求める。
googlecolaboratoryでpythonを⽤いてポケットキューブをすべての⾊が揃った状態からn⼿(nは1から1ずつ⼤きくする)動かし、できた配置がlist内にあるかを調べ、ある場合はlistに保存せず、ない場合はlistに保存するというプログラ
ム を作成する。list内の配置の総和が総配置数と等しくなったときのnの値を求める。そのnの値が「God's number」である。※なぜlist内の配置の総和が総配置数と等しくなったときのnの値が「God'ｓnumber」と⾔えるのかというと、n=kのときに初めてでてきたある配置から⾊が揃った状態に戻すためには、最短でk⼿必要となるから。(nの値は1から1ずつ⼤きくしていき、list内に同じ配置があった場合は、保存しないため、n=k-1まで動作を⾏い出てこずn=kのときに初めて出てきた配置の最短⼿数はk⼿となる)
list内の配置とその配置に⾄るまでの⼿順をたよりに法則性を⾒つける。

4.実験の実⾏〈Ⅰ.総配置数を求める〉

８個のブロックに分解し１つのブロックを固定し考える。
また、その⾊は考えない。
固定したブロック以外の７つのブロックの配置は７︕通りある。
また、ひとつのブロックには⾊が３⾊あるためブロックの向きは３通り、これを７個分考えるため３７ 通りとなる。よって計算式は
３７✕７︕となるがこのままでは普通にポケットキューブを動かしただけでは起こりえない、パリティと呼ばれる状態も含まれてしまう。
よってパリティを除くためにパリティが起こる確率を考えていく。

〈パリティの証明〉

先⾏研究ではポケットキューブでパリティが起こる確率は2/3とされていたが、その証明が記載されていなかったためその証明をしていく。
完成状態に対して向きに相違がある状態を「向きズレ」、位置に相違がある状態を「位置ズレ」と呼ぶことにする。

向きズレ

位置ズレ

下の図のように時計回りに120°ズレているピースの個数＝ｃ（clock cyclic）
反時計回りに120°ズレているピースの個数＝uc（unticlock cyclic）とする。

反時計まわり時計まわり

ポケットキューブを 正⾯をF⾯、背⾯をB⾯、左⾯をL⾯
右⾯をR⾯、上⾯をU⾯、下⾯をD⾯とするとD⾯が揃っているとして、U⾯のピースの位置ズレと向きズレの関係性を考える。 すると、下表のような結果になった。
位置ズレ
（個）

向きズレ
（個）

０ｃ=0
uc=0

c=1
uc=1

c=2 uc=2c=3uc=0c=0
uc=3

２ｃ=0
uc=0

c=1
uc=1

c=2 uc=2c=3uc=0c=0
uc=3

３ｃ=0
uc=0

c=1
uc=1

c=2 uc=2c=3uc=0c=0
uc=3

表は、向きズレの起きているピースの個数を表している。また、位置ズレが0,2,3個のいずれのときでも向きズレの組み合わせはすべて起こっていた。（位置ズレは1個だけで起こらないため、位置ズレの個数は、0,2,3のいずれかである。）表より、ピースの位置ズレに関係なく、cとucは３を法として合同であることに気づいた。このことから、パリティにならない条件はこのことと等しいのではと仮定して次のようなことを考えた。

パリティが起こるのはcとucがmоd３で合同かつD⾯が揃っていない場合も同様に成り⽴つのでは︖
よって次のことを考える。「パリティが起こる要因は向きズレのみであるから、ピースの向きを変化させていきパリティが起こる確率を求める。ひとつのキューブを固定して考える。c＝ｘ個、uc＝ｙ個としてキューブが揃うには０≦ｘ＋ｙ≦７（ｘ＋ｙ≠１）ー①ｘ≡ｙ（mоd３）ー②を満たすことが必要である。
①を満たすｘ、ｙの組は36組ある。これはパリティを含む。
また①かつ②を満たす組は12組ある。これはパリティを含まない。
このことから、パリティの起こらない確率【Ｐ①(②)】＝Ｐ(①∧②)/Ｐ(①)＝12/36＝1/3(条件つき確率)であると⾔える。
ただし、これは⼗分性の証明であり、必要性の証明が⾜りていないため、その証明もしていく。

パーツに存在するU⾯またはD⾯の⾊が、U⾯かD⾯を向いている状態を「正規状態」と呼ぶことにし、正規状態におけるパーツの向きのベクトルを０
時計回りに120°ズレているピースの向きのベクトルを＋１
反時計回りに120°ズレているピースの向きのベクトルをー１とする。

⼀般に、基本操作では向きの総和は変わらないことが⽰されている。
例えば、右上の図は正規状態からRの操作を⾏ったものでも向きの総和は０になる。
「完成状態での向きの総和は０」
つまり、パリティでない限り、どんな配置でも向きの総和は０なので向きにおいて完成状態にもっていくための条件はｃとucが３を法に合同となる。
また、これはｄ⾯u⾯に限らず成り⽴つので前のページで仮定した２つの条件と⼀致する。以上により条件の必要性を確認できたので、前のページで提起した条件が必要⼗分条件であることが証明できた。
よってパリティは2/3であるため、パリティを除いた計算式は3７ ✕ 7︕ ✕ 1 / 3 = 3,674,160
したがって、総配置数は3,674,160通りである。

〈Ⅱ.プログラミング〉①ポケットキューブを動かすプログラムの作成
ポケットキューブの動かし⽅は以下の通りである。

Uの⾯の動かし⽅は右と左のみで、右に動かすときUr、左に動かすときUl、180°回転させるときU180°、Dもまた同様である。
Lの⾯の動かし⽅は上か下のみで、上に動かすときLu、下に動かすときLd、180°回転させるときL180°、Rもまた同様である。
Fの⾯の動かし⽅は右か左のみで、右に動かすときFr、左に動かすときFl、180°回転させるときF180°、Bもまた同様である。
つまり、⾒る⽅向を変えることで、次のことが成り⽴つ。
Ur=Dl Ul=Dr U180°=D180°
Ld=Ru Lu=Rd F180°=B180°
Fr=Bl Fl=BrF180°=B180°※r=右に90° l=左に90° d=下に90° u=上に90°
よって、キューブの動かし⽅が、9通り(U,F,Rが3つずつ)のときすべての動かし⽅で動かすことができるため、すべての配置を作ることができる。
また、このとき1つのブロックが全く動かない。）(B⾯,D⾯,L⾯に含まれるブロック②ｎ⼿を求めるプログラムの作成
すべての⾊が揃った状態のポケットキューブの8つのブロックの配置(位置と向き)をキューブを回す動作をn⼿分変更し、できた配置が既にあればlistの中に保存せず、なければ保存する。
ｎの値を１から順にこの動作を繰り返し⾏い、1⼿⽬からn⼿⽬までの配置数の値が求めた総配置数の値と等しくなったときのnの値を求める。
このプログラムを、ブルートフォース法と呼ばれる⽅法で⾏った。
※ブルートフォース法とは考えられるものすべてを試⾏する⽅法。
例:)n=3のとき
上記より動かし⽅は、9通りあるから、考えられる動かし⽅の総数は
9^3=729通り
11⼿⽬まで試⾏すると34926271571通り
キューブの定義のコード⇓

上の３つはFr Ru Ulの３つの回し⽅の定義である
このプログラムはキューブの１つのブロックのベクトルに向きと位置の２つの要素を持たせ、キューブを回す動きに合わせて要素を変更してキューブを動かす動作を再現している。

５.結果

Ⅰ.総配置数は
7!×3^7÷３より3674160通り。
Ⅱ.プログラムの作成には成功したが、nの値が⼤きくなるほど配置がlist内に存在するかどうかを確認する動作にかかる時間が膨⼤になってしまい、list内の配置の総和が総配置数となるまではいかなかった。具体的には、8⼿⽬で1時間、9⼿⽬は3時間以上待っても計算が終了せず、さらに時間がかかりそうだったため中断した。したがって、現在到達できているのは8⼿⽬までで1159968通りとなった。
ここまでで試⾏し、できた配置は同じものを含めて、48427561通りであった。
また、それまでの結果は下表のとおりである。
⼿数

新規配置数

総配置数０１１１９１０２５４６４３３２１３８５４

１８４７２２３２５９９９２

１２２２４

６５０１３６６２３６０

７２２７５３６２８９８９６

８８７００７２

１１５９９６８

この結果は先⾏研究で求められていたものと⼀致し、我々のコードが正しい結果を与えることが検証できた。
Ⅲ.Ⅱが終了していないため⾏うことができなかった。

６.今後の展望

プログラムの中のポケットキューブの定義⾃体をコンピュータが処理しやすいものに変更して１つ１つの動作を効率化することで最適化をする。
できたプログラムを⽤い「God’s number」を求める。
プログラムからキューブを解く最短⼿順を取り出して、最短⼿順の法則を⾒つける。