Document

ルービックキューブの探索プログラム
北海道大学理学部数学科４年大島知樹
指導教員秋山正和（電子科学研究所）
４．数値計算結果
4．効率的な探索手法の必要性
１．研究動機
ルービックキューブは，ハンガリーの建築学者である
エルノー・ルービックが1974年に考案したパズルである
（図１）．３×３×３個の立方体からなるように見えるこの
立方体は，各列を独立して回転させることができる．こ
のパズルは、その回転を用いて６色に塗り分けられた面
をバラバラにし，それを回転により再び揃えて遊ぶもの
である．パズルとしての操作は各列の回転のみであり，
一見簡単そうに見えるが，各回転は様々な面に影響す
るため，見た目に反して難易度の高いパズルである．
今後，ルービックキューブは一般のサイズのものを考える．ルービックキューブの回転
によって得られるパターン数は１，２，３面体の位置と２，３面体の向き，及び前述の３面体
の捻り量の条件に加えて，２面体の捻り量の条件がある．さらに奇数サイズのものは，中
心部分の２面体（図１１）と３面体の相互の位置関係の条件がある．これらを考慮すると，
ルービックキューブの回転によって得られるパターン数は（4.1）のようになる．
図１．ルービックキューブ
ルービックキューブはパズルとしてのみならず，数学
的対象としても興味深いものとして知られている．ルー
ビックキューブの小面の状態を元とする集合を考え，
回転操作をその集合上の演算とみなすと，その集合と
演算の組は群をなすことが知られている（＊）．例えば，
ルービックキューブにある複数の回転操作を施したあ
とに，その逆の操作を行うとルービックキューブは元に
式１．群の定義
戻る．これはちょうど，群における元とその逆元の存在
に対応している（式１）．
ルービックキューブは，その明快さから子供から大人まで広く愛されているパズルであ
るが，そのようなものに数学の群構造が含まれていることに私は純粋な興味を持った．ま
た，ルービックキューブの群構造のみならず，難易度の高いこのパズルを数学的手法を
用いて解決することにも興味を持った．
＊：群論の味わい置換群で解き明かすルービックキューブと15パズル（David Joyner 著，川辺治之訳，共立出版，2010年）
２．ルービックキューブと群構造
今後，ルービックキューブは世界標準配色のものを考える（図
２）．橙の１面体を含む面を右面（Right）と定義する．同様に，赤，
黄，白，青，緑の１面体を含む面を，左面（Left），前面（Front），後
面（Back），上面（Up），下面（Down）と定義する．
右面を正面に見て，右面を右に９０°回転する操作をRと定義す
る．また，１８０°回転する操作，２７０°回転する操作をそれぞれ，
R2，R'と書く．他面の回転も同様に定義する．なお，中心列の回
転は定義しない．これは，中心列の回転は，その中心列以外の２
列の回転により実現できるためである．
各小面に図２のように番号を付ける．すると，Rによる小面の移
動は，置換群の表記を用いて（2.1）のように記述できる．
(1)
(3)
（4.1）
(2)
(3)
(4)
サイズ
パターン数
１秒に１京パターンを
発見できるスパコンの
計算時間
２×２×
２
3.67×106
１秒未満
３×３×
３
4.32×1019
約１時間１２分
7.40×1045
約２３４垓年
４×４×
４
表２．回転によるパターン数と計算時間
2.82×1074
約８９４極年
５×５×
５
図１１．中心部分の２面体
（4.1）より，２×２×２から５×５×５サイズのパ
ターン数を求めると，表２のようになる．仮に，全
探索で１秒間に１京（1.00×1016）パターンの速さ
で解法を見つけられるスパコンがあったとしても，
ルービックキューブのサイズが大きくなると，現実
的な時間で解法を見つけることは不可能になる．
このため，ルービックキューブの解法探索では，
効率的な探索手法が必要不可欠となる．
5．探索プログラム
図２．世界標準配色の展開図と
各面の番号付け
図１２．探索プログラムによる解法表示
他の回転についても，同様にして置換群の表記を用いて記述できる．それらをそれぞれ，
，，，，とする．
R2はRを２回施して得られる回転なので，置換群の表記を用いるととなる．同様にR'
はRを３回施して得られる回転なので，となる．このことより，ルービックキューブの回転
操作による置換群は単純に（2.2）のようになる．以後をルービック群と呼ぶ．
図
図１３．入力画面
図１４．カメラ機能
説明
Ⅰ．回転の全探索により，左図のような"６個"か"８個"
のブロックを見つける．
（2.2）
Ⅱ．Ⅰで見つけたブロックを起点に，回転の全探索によ
り，左図のような"１２個"のブロックを見つける．規定手
数以内に見つからなかった場合，Ⅰに戻る．
ルービック群は，明らかに５４次置換群の部分群である．このように置換群との関連付
けをすることにより，ルービックキューブを置換群の部分群として扱うことができる．
Ⅲ．Ⅱで見つけたブロックを起点に，一部回転を制限し
た回転の全探索により，左図のような"２層揃い"のブ
ロックを見つける．規定手数以内に見つからなかった場
合，Ⅱに戻る．
3．回転により得られないパターン
Ⅳ．OLL（Orientation of the Last Layer）と呼ばれる回転
処理を行い，"２層揃い+１面揃い"の形を作る（左図）．
その後，PLL（Permutation of the Last Layer）と呼ばれる
回転処理を行い，完成形（右図）を作る．
図３．３面体（全８個）
図４．２面体（全１２個）図５．１面体（全６個）
表３．３×３×３の解法の探索手法
ルービックキューブを分解し組み直すと，図６のようなパターン
が得られる．しかし，このパターンは，完成状態からの回転操作
では作ることができない．以後，このことを示す．
上面と下面を基準面とし，基準面の色を基準色とする．基準
色の小面が基準面に面している場合，その３面体の捻り量は０
であると定義する（図７）．同様に，基準色の小面が基準面に対
し，図８，図９のような位置関係にあるとき，その３面体の捻り量
はそれぞれ１，２であると定義する．
８個ある３面体の捻り量の和を捻り量の総和と呼ぶことにする．
例えば，完成状態のルービックキューブは，全ての基準色の小
面が基準面を向いているので，捻り量の総和は０である．
次に，回転によって３面体の捻り量がどのように変化するかを
考える．まず，Rについて考える．Rに関わる４つの３面体に図１
０のように番号を付ける．１，２，３，４の３面体の全ての捻り量
の組み合わせと，その状態にRを施した後の捻り量の関係をま
とめると表１のようになる．表１より，全ての捻り量の状態に対し，
Rは捻り量の総和を３で割った余りを変化させないことが分かる．
同じようにまとめると，L，F，Bについても同様のことが分かる．
また，U,Dは全ての３面体の捻り量を変化させない．
以上のことと，完成状態のルービッ
クキューブの捻り量の総和が０であ
ることより，回転によって得られるパ
ターンは，全て捻り量の総和を３で
割った余りが０であることが分かる．
図６のパターンは捻り量の総和が１
であることより，回転によって得るこ
とのできないパターンであるというこ
とが分かる．
(4)
ルービックキューブの解法を探索するプログラムを制作した（図１２，図１３）．解法の探
索手法は表３の通りである．このプログラムに，入力された面情報が回転によって完成状
態にできるものであるか，２，３面体の捻り量や位置を元に判定する機能を実装した．
また，OpenCVという画像処理ライブラリを用い
て，ウェブカメラを使って面情報の入力ができる
機能を実装した（図１４）．
（2.1）
ルービックキューブを構成する小立
方体のうち，３面が表に面しているも
のを３面体と定義する（図３）．同様に
２面体，１面体を定義する（図４，図５）．
ルービックキューブは８個の３面体，１
２個の２面体，６個の１面体からなる．
(1) ２×２×２のパターン数
(2) ３×３×３のパターン数
(3) ２面体の配置のパターン数
(4) １面体の配置のパターン数
また，３×３×３の探索手法を応用して，一般
のサイズに対するプログラムも制作した（図１５，
１６）．２×２×２サイズのものは，完成形までの
全探索により，解法を求める．一般のサイズの
ものは，まず，１面体を揃えた後（図１７），揃え
た１面体を維持しながら２面体を揃え（図１８），
最終的に３×３×３サイズの探索手法を用いて，
解法を求める．
図６．回転により得られない
パターン
図７．捻り量０
図８．捻り量１
図１５．２０×２０×２０サイズ
図１６．２×２×２サイズ
図９．捻り量２
図１０．３面体の
番号付け
3面体
1,2,3,4の捻り量
（１）
（１）の和を
３で割った余り
Rを施した後の
1,2,3,4の捻り量
（２）
（２）の和を
３で割った余り
0,0,0,0
0
2,1,2,1
0
0,0,0,1
1
0,1,2,1
1
：
：
：
：
1,2,0,1,
1
0,2,1,1
1
：
：
：
：
2,2,2,1,
1
0,0,1,0
1
2,2,2,2
2
1,0,1,0
2
表１．回転と捻り量の変化の関係（全81通りの一部）
図１７．１面体揃え
図１８．２面体揃え
6．まとめ
研究開始時は，ルービックキューブに触れることすら初めての状況であったが，最終的
に一般的なサイズのルービックキューブに対しての解法プログラムを作ることができて，
非常に満足している．ただ，当初の目的であった，数学的手法による解法によるものでは
ないことに関しては満足していない．また，３×３×３サイズにおいて，俗に"神の数字"と
呼ばれる回転数の下限の上限（２０手）からは，ほど遠い手数の解法しか見つけられない
ことに関しても不満がある．
ルービックキューブは既によく研究されているが，一般的なサイズのものに関しては，ま
だ不十分なことが多々ある．この先，数学の発展はもちろん，コンピュータ性能もますま
す向上していくものと思われる．数学，コンピュータ双方からのアプローチによって一般の
サイズのものに関しても，より研究が進むことを願っている．

Download Report