表１．回転と捻り量の変化の関係（全81通りの一部）

Presentation on theme: "表１．回転と捻り量の変化の関係（全81通りの一部）"— Presentation transcript:

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