1. - 北海道大学電子科学研究所 数理科学研究部門 動的数理

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

similar documents