著者
串山, 繁; KUSHIYAMA, Shigeru
引用
北海学園大学工学部研究報告(46): 119-131
発行日
2019-02-14
Matlabを用いたルービックキューブのLBL解法
串 山
繁
＊LBL Solution of Rubik’s Cube Using Matlab
Shigeru K
USHIYAMA 要 旨 ルービックキューブはハンガリーの建築学者：Ernö Rubikが１９７４年に考案し，１９８０年代 初頭に日本で大ブームとなった立体パズルで，３×３×３タイプのルービックキューブの 色の組み合わせ数は約４．３２５２×１０１９通りある１）．ルービックキューブが如何なる不揃いの配 色状態からでも最多で何手で６面揃った状態に戻せるかの手数はGod’s Number（神の 数）と呼ばれ，ルービックキューブが発売されて以来数学者の関心事であった．その数 は，群論に基づくアプローチによりGod’s Number＝２０であることがTomas Rokicki，Her-bert Kociemba，Morley Davidson，John Dethridgeにより検証され，それ以上でも以下でも ないことが２０１０年７月に発表されている２），３）． 数学教員志望学生の卒業論文指導として，上記とは異なるアプローチ：ルービック キューブの解法として広く普及しているLBL（Layer−by−Layer）法により単純明快なプロ グラムを作成したが４），その詳細については未公表であったので，本報告で概要について 述べる．１．ルービックキューブの構造
３×３×３タイプのルービックキューブは，図−１に示す様に１つの面が３×３＝９分割さ れ，合計９×６＝５４面が６色に彩色され，夫々１面体（センターキューブ）６個，２面体 （エッジキューブ）１２個，３面体（コーナーキューブ）８個の計２６個の小キューブから成る． なお，同図は世界基準配色を前面（Front）赤，上面（Up）緑，左面（Left）黄，背面 ＊北海学園大学工学部建築学科（a）表面 （b）裏面 図−１ ルービックキューブ（世界基準配色） （a）上段のみ分解 （b）センターボールと１面体 写真−１ ルービックキューブの構造 （Back）橙，右面（Right）白，下面（Down）青として眺めた場合を示したものである． 物理的な構造は写真−１に示す通りで，キューブの中心は２６個の小キューブを連結するセン ターボールとなっている．センターボールの先端には各面の中心に位置する１面体が取り付け られ，計６個ある１面体は回転するが相対的位置関係は移動しない．一方，辺にある２面体， 頂点にある３面体は自由に回転して位置・向きが変わる仕掛けになっている．
２．ルービックキューブの色の組み合わせ数
先に述べた様に１面体を除く２面体（１２個），３面体（８個）の小キューブは自由に回転 し，配色可能な組み合わせ数は厖大となる．以下に組み合わせ数について考える． ２面体についての配置は１２!通り，更に夫々向きを持つので２１２通り，３面体についても同様 にその配置は８!通り，更に向きは３８通り，したがってそれらを掛け合わせると， １２!×２１２×８!×３８＝５１９，０２４，０３９，２９３，８７８，２７２，０００ 通り となる．しかし，この組み合わせ数は規則を無視しキューブをバラバラに分解した場合であ る．規則に従いキューブをバラバラに分解しない場合には，以下の３つの制約： １．ルービックキューブの回転を巡回置換として表すと偶置換となり，奇置換となる回転が存 串 山 繁 １２０図−２ 小キューブの面番号（１面体右横の数値は，１面体の面番号） 在しないので，色の組み合わせは１／２となる． ２．２面体の位置が全部揃ったとき，向きが反対になるのは偶数個となるので，色の組み合わ せは１／２となる． ３．３面体の位置が全部揃ったとき，向きが時計回りにずれているものの個数と反時計回りに ずれているものの個数とは，等しいかまたはその差が３の倍数であるので，色の組み合わ せは１／３となる． があり，その組み合わせ数は， １２!×２１２×８!×３８／（２×２×３）＝４３，２５２，００３，２７４，４８９，８５６，０００ 通り ∼（１） と１／１２に減少する５）．
３．ルービックキューブの数学的表現
ここでは，群論に基づくルービックキューブの数学的表現について説明する．その準備とし て，図−２に示す様にルービックキューブを展開した各面：U，L，F，R，B，Dの小キューブ の面番号を設定する．同図において，１面体は２面体，３面体とは別に付番している．更に キューブを操作する回転記号：シングマスター記法を導入する．先ず，U，L，F，R，B，Dは 夫々の面に正対して右回りに９０°回転する単位操作を表すものとする．一方，U’，L’，F’， R’，B’，D’は左回りに９０°回転する単位操作を表すものとする．同様に，U２，L２，F２，R ２，B２，D２は右回りに１８０°回転する単位操作，即ち右回りに９０°回転する単位操作を２回行 うことを表わす． 次に，置換の理論をルービックキューブに適用するために巡回置換を導入する．巡回置換と は全部の並びを１つずつずらす置換であり，例えば４次の置換は次の様に書ける６）． １２１ Matlabを用いたルービックキューブのLBL解法!!!" # # $ $ % % " ! " ∼（２） これは，a→b，b→c，c→d，d→aに置換されることを意味している．したがって，単位操作F は（２）式の表記に倣うと４次の巡回置換５つで，その他の単位操作も列挙すると以下の様に 表すことができる．これは図−２に示した展開図を切り抜いて立方体を作れば，容易に確認で きる． F＝（１７１９２４２２），（１８２１２３２０），（６２５４３１６），（８３０４１１１），（７２８４２１３） B＝（３３３５４０３８），（３４３７３９３６），（３９４６３２），（２１２４７２９），（１１４４８２７） L＝（９１１１６１４），（１０１３１５１２），（１１７４１４０），（４２０４４３７），（６２２４６３５） R＝（２５２７３２３０），（２６２９３１２８），（３３８４３１９），（５３６４５２１），（８３３４８２４） U＝（１３８６），（２５７４），（９３３２５１７），（１０３４２６１８），（１１３５２７１９） D＝（４１４３４８４６），（４２４５４７４４），（１４２２３０３８），（１５２３３１３９），（１６２４３２４０） F’＝（１７２２２４１９），（１８２０２３２１），（６１６４３２５），（８１１４１３０），（７１３４２２８） B’＝（３３３８４０３５），（３４３６３９３７），（３３２４６９），（２２９４７１２），（１２７４８１４） L’＝（９１４１６１１），（１０１２１５１３），（１４０４１１７），（４３７４４２０），（６３５４６２２） R’＝（２５３０３２２７），（２６２８３１２９），（３１９４３３８），（５２１４５３６），（８２４４８３３） U’＝（１６８３），（２４７５），（９１７２５３３），（１０１８２６３４），（１１１９２７３５） D’＝（４１４６４８４３），（４２４４４７４５），（１４３８３０２２），（１５３９３１２３），（１６４０３２２４） 上記以外の回転操作：S，M，E，S’，M’，E’は次の様に表示される． S＝（４２６４５１５），（５３１４４１０），（１４６２） M＝（７２３４７３４），（２１８４２３９），（１３６５） E＝（２１２９３７１３），（２０２８３６１２），（３４５２） S’＝（４１５４５２６），（５１０４４３１），（１２６４） M’＝（７３４４７２３），（２３９４２１８），（１５６３） E’＝（２１１３３７２９），（２０１２３６２８），（３２５４） 更に，Rw，Lw，Fw，Bw，Uw，Dwの２段を纏めて回す操作および（r），（u），（f）の持ち 替え操作とそれらに’を付けた逆回転の操作もあるが，いずれも上記に表示した単位操作の積 として表示することができる． なお，任意の置換は巡回置換の積として表せ，n次の巡回置換は（n‐１）個の互換の積に分 解できる．互換とは文字列中の２つのみを入れ替え，それ以外は動かさない並び替えである． （２）式の巡回置換は，次の様に互換の積で表される． !!! $ %" ## $" #" #" # ∼（３） 串 山 繁 １２２
図−３ 小キューブの付番 ∵ "# $#" #" #! "" #!! ! " " # $ $ # ! "! ! " # # " $ $ ! "! " " ! # # $ $ ! " ! ! ! " # # $ $ " ! "! " " ! # # $ $ ! "! " " # # $ $ ! ! " 偶数個の互換の積として表される置換を偶置換といい，奇数個の互換の積として表される置 換を奇置換という．したがって，４次の巡回置換は奇置換である．また，偶置換と偶置換の積 および奇置換と奇置換の積は偶置換であり，偶置換と奇置換の積と奇置換と偶置換の積は奇置 換となる． ここで，ルービックキューブの小キューブの移動を考える．図−３は，１面体が固定されて いるとして，２面体，３面体についてのみ識別番号を付番したものである．図−３に単位操作 Fを施す場合は次の様に表示できる． +!" $ # "! $ "& % % & & ' ' ( ( ) ) * # "! "% "" "" "# "# "$ " "% * "& "$ "' "' "( "( ") ") "* "* #! #! ! " ! " $ "& "$" ## "! "% *" # ∼（４） （４）式は４次の巡回置換の積であるから奇置換×奇置換で偶置換となることが分かる． その他の単位操作も同様に偶置換となり，ルービックキューブにおいて奇置換を生起するこ とは無い． また，単位操作は巡回置換を元とする集合から成り，その意味で対称群といえる．対称群は 次の性質を有している． １．２つの並べ替えを合成しても既知の並べ替えに等しいものがある．即ち，この集合は演算 １２３ Matlabを用いたルービックキューブのLBL解法
の合成に対して閉じている． ２．結合則が成立する．
３．単位元（順番を何も変えない操作）が存在する． ４．逆元（元に戻す逆の並べ替え）が存在する．
４．ルービックキューブのモデル化
群論の文脈によれば，解くべき問題はルービックキューブ群のHTM（Half −Turn Metric）に 関するCayleyグラフの直径（即ち，頂点間の最大エッジ距離）を決定することである３）．しか し，数学を専門としない者にとってはこの種のアプローチは難解であるため，本報告ではルー ビックキューブの解法として広く普及しているLBL（Layer−by−Layer）法を用いることとした． 群論に特化した言語として計算機代数システムGAPをインターフェースとして使用する SAGEが提供されているが，本報告では広く普及している言語を用いて分かり易いプログラム を作成する方針の下にMATLAB言語を使用することとした． MATLABは，patchコマンドを用いてルービックキューブを図化できる．このために必要な データは，次の３つ：①キューブを３×３×３に分割するメッシュ交点の座標値，②その交点 番号による小キューブ面の定義，③小キューブ面のカラーデータである．ここで，最初の２つ のデータは，ルービックキューブに操作を施してもキューブと一緒に動かず，常に最初の位置 に固定され，３番目のカラーデータのみがルービックキューブの操作に伴い変わるものと考え る．小キューブの面番号は先の図−２に示した通りであり，小キューブを規定する小キューブ 四隅の頂点番号は，図−４に示す通りとする． 解法のポイントは，特定キューブの位置・向き・カラーの把握を如何に行うかである．これ 図−４ 小キューブ四隅頂点番号の設定 串 山 繁 １２４
上段 下段 （a）位置番号の設定 （b）向きの設定 図−５ コーナーキューブの位置番号と向きの設定 上段 中段 下段 （a）位置番号の設定 （b）向きの設定 図−６ エッジキューブの位置番号と向きの設定 を把握できれば，特定の位置に特定のキューブをLBL法の手順に従い移動すればよい．本プロ グラムにおいては，図−５，６に示す様にキューブの位置・向きを設定した． カラーデータについては，初期値として６面体のカラーが揃った状態（以後，ホームポジ ション状態と呼ぶ）を与えている．カラー行の並び順はU，L，F，R，B，Dであり，先に２， ３面体について与え，最後に１面体について与えた．なお，計算開始時のランダムなカラー配 置は，２通りの方法：マニュアル入力，自動生成入力を用意した．図−７はマニュアル入力画 面の一例，図−８は図−７に対応した入力データ例（データ入力訂正例を含む）である． 自動生成入力は，最初にホームポジション状態を作成した後，それに対して毎回異なる順序 で連続した５４種類の単位操作を施して生成した． １２５ Matlabを用いたルービックキューブのLBL解法
図−７ マニュアル入力データ例 図−８ マニュアルデータ入力（図−７に対応，データ訂正を含む）
５．ルービックキューブ解法プログラム
本プログラムは，マニュアル入力状態或いは任意のランダムなスタート状態からホームポジ ション状態へ導く解を求めるプログラムである． （１）メインプログラム（Rubik_Cube_Solution_Strategy.m） 先ず，メインプログラムの入力データ等について説明する．計算は，次の４つのデータ： cal_cont_flag，figure_flag，ope_disp_flag，cal_numbを用いて指示される． cal_cont_flag＝０or１ ＝０：スタート状態を自動生成してファイルに保存後，実行（連続計算時使用） ＝１：保存スタート状態をファイルから読み込み，実行（マニュアル入力データ時或 いはデバッグ時使用） figure_flag＝０or１ 串 山 繁 １２６＝０：ホームポジションに至る単位操作毎の３Dキューブ表示無し ＝１：ホームポジションに至る単位操作毎の３Dキューブ表示有り ope_disp_flag ＝０：ホームポジションに至る一連の操作のみ表示 ＝１：ホームポジションに至る各単位操作詳細情報の表示あり（デバック時使用） cal_numb：連続計算回数（ただし，マニュアル入力データ作成時或いはデバッグ時は１と する） 上記データ読み込み後はホームポジション状態を表示した後，cal_cont_flagデータに応じ て，計算開始状態を自動生成するか保存スタート状態をファイルから読み込むかのいずれかへ 進み，計算開始状態のキューブを３D表示する．なお，任意のランダムな計算開始状態のカ ラー配置は，５４種類の単位操作の順番をrandperm関数に次の２行を追加して毎回異なる様に生 成している．
s = RandStream.create (’mt１９９３７ar’,’seed’,sum (１００＊clock))；
RandStream.setDefaultStream(s)； それ以降については，LBL法に従った各ステップのfunction.mファイルの実行に移る．最後 に，プログラム末尾で平均計算時間，平均操作手数等を出力して終了である． （２）function.mファイル（サブプログラム） function.mファイルのファンクション名およびそれらの機能は次の通りである．なお，字下 げしたファンクション名は字下げ前のfunction.mファイルにぶら下がっていることを意味す る．また，ファンクション名末尾に＊）が付随しているのは，そのファンクション名の下に本来 記すべきOperation，face_combinationを省略したことを意味している． なお，LBL法に従った解法パターンについては，文献５），７），８）を参照した． manual_input_data：マニュアルデータ入力（メインプログラムとは独立） color_def_save：２面体，３面体および１面体のカラー配置をファイルに書き込み init_perif_switch：スタート時のランダムなカラー配置の作成 mod_randperm：ランダムな操作手順の生成 Rubik_Cube_operation：ルービックキューブの各単位操作の定義 perif_switch：２面体，３面体のカラー配置巡回更新 center_switch：１面体のカラー配置巡回更新 face_combination：操作後のカラー並び順番の把握 color_def_save：（前出） １２７ Matlabを用いたルービックキューブのLBL解法
○：位置・向きが一致している場合，×：位置・向きが一致していない場合 図−９ 青色F面コーナーキューブ位置・向きの一致個数 color_def_read：２面体，３面体および１面体のカラー配置をファイルから読み取り Rotation_Judge：前面赤・上面緑・左側面黄となる視点から眺めた表示とする調整 adjust_Uface：上段キューブの色，向きを揃える Operation：一連の操作を単位操作に分割し，操作毎の結果を図化 face_combination：（前出） adjust_middle_edgeface＊）：中段の２面体を揃える search_object_position_aspect：始点の位置，向きを探索 adjust_Dface_only＊）：下段を反転した上段青面についてカラーのみを揃える （向きについては無視） adjust_Dface_corner_aspect＊）：青面を前面にしF面の３面体コーナー向きを揃える count_corner_agree：青面を前面にして位置・向きが揃っているコーナー キューブの個数確認 agree_０＊）：青面３面体コーナーキューブ４個未完成の対応 count_corner_agree：（前出） agree_２：青面３面体コーナーキューブ２個完成，２個未完成の対応 ag_two_１１０：対角スラッシュ−−＞バックスラッシュに変換 （図−９参照） ag_two_１００１：バックスラッシュ方向に２個一致している状態への対応 ag_two_１１００_１０１０：隣接して上，左縦で２個一致している状態への対応 ag_two_１１：隣接して下で２個一致している状態への対応 adjust_Dface_cross_aspect＊）：青面エッジキューブの向きを揃える count_cross_agree：青面２面体の向き確認チェック
６．実行結果
先ず，ノートPCを用いて得られた連続計算結果の一例について述べる．表−１に計算平均 所要時間，平均単位操作手数等を示す．ただし，この計算平均時間とはランダムなスタート状 串 山 繁 １２８態設定後の一連の単位操作手順を求める時間であり，連続計算は１０，０００回で且つ解法操作手順 のみを表示する場合である．同表によれば，平均計算時間は約０．１３５（sec）であり，素早く解 が得られることが分かる．ただし，単位操作毎の３Dキューブ表示を行うと２０∼３０（sec）と非 常に長い時間を要する．平均単位操作手数は，解法パターンの場合分け数を極力少なく抑えて （本プログラム例では持ち替えを除くと実質的には総数１９）プログラムをシンプルに分かり易く したため，約１６０手と多くなった．この原因の一つとして，例えば一連の操作中でD D，D２ D，U’ U，U’２U，U２U等とあるのをプログラムを分かり易くするため敢えてD２，D’，単位 元，U’，U’等と短縮していない箇所があることが挙げられる．これを短縮した場合には表中 の値よりも１５∼２５手減少する．なお，表中にadjust_middle_ edgeface異常発生率とあるのは，中 段のエッジキューブを揃える箇所での異常発生（キューブの移動が４回を超える循環ループに 陥ると異常と判定）回数を把握する目的で出力した．異常発生の可能性を否定出来ないのは， ルービックキューブの色の組み合わせ数：約４．３２５×１０１９の全てについて確認することは非現実 的で，内一部のケース（約３０，０００回）についてのみ確認したに過ぎないからである． 次に，非常に多くの手数を要することが予想されるスーパーフリップについて実行した． スーパーフリップとは，全てのエッジキューブ位置は揃っているが向きが反対である図−１０に 示した状態である．計算結果の手数は２１０手となった．なお，計算時間は各単位操作の図を全 て表示した場合３５．２５４６（sec），その図を表示しない場合０．５５２６３２（sec）であった． なお，MATLABと互換性のあるフリーソフトであるGNU Octave−３．６．４をスーパーフリップ 平均計算時間（sec） ０．１３５２５４ 平均単位操作手数（回） １５９．３１３ adjust_middle_edgeface完成時エラー発生率（％） ０ 表−１ 連続計算１０，０００回実行時の実行結果
使用コンピュータ：Panasonic CF−S９ Let’s note（プロセッサ：intel（R）Core TM i５ CPU M５６０＠２．６７Ghz，RAM：４．００GB，６４bit Operating system）
（a）F，U，L面 （b）B，D，R面
図−１０ スーパーフリップ
１２９ Matlabを用いたルービックキューブのLBL解法
に適用したところ，各単位操作の図を表示しない場合１．０７６４（sec）と約２倍の計算時間を要 した．しかし，各単位操作の図全てを表示する場合，下記に示すGNU Octaveの警告が多数発 生し，途中でプログラムの実行が停止する．これは，画像表示数がOctaveの限界容量（計算例 では１０１画像）を超えると発生する．
Warning：ft_manager：unable to load font：C：/WINDOWS/fonts/arial.ttf Warning：ft_render：unable to load appropriate font
これを回避するには，単位操作毎の全ての画像表示から各一連操作の最終操作画像のみの表 示に切り替え，画像表示数を少なく抑えればよい． なお，ランダムパターンを自動生成して始める場合には，前項で示したRandStream関数につ いてOctaveは未対応である．このためmod_randpermファンクションmファイルの代わりにrand-permファンクションmファイルを使用することとなり，Octaveを起動する度にランダムパター ンの生成は同じものとなる．
７．まとめ
MATLAB言語を用いてLBL法によるルービックキューブ解法プログラムを作成した．ルー ビックキューブ群のHTM（Half −Turn Metric）に関するCayleyグラフの直径（即ち，頂点間の 最大エッジ距離）を決定する手法によれば，どの様なランダム状態から出発しても２０手以内で ６面が完全に揃ったホームポジション状態に至ることが判明している．しかし，本報告では解 法パターンの場合分け数を極力少なく抑え（本プログラム例では持ち替えを除くと実質的には 総数１９），分かり易いプログラムとすることを優先した． ランダムな色配置の状態から解法操作手順を見出す計算を連続１０，０００回実行した結果によれ ば，画像表示を省略した平均計算所要時間は１回当たり０．１３５２５４（sec），平均単位操作手数は 約１６０手であった．また，スーパーフリップの計算例では計算時間０．５５２６３２（sec），計算手数 ２１０手を要した．ただし，各単位操作の図を全て表示した場合には３５．２５４６（sec）であった． 計算手数が多いことに難があるが，単純明快な本解法プログラムは短時間で解が得られ，計算 容量も少なくて済む利点を有する． なお，フリーソフトであるGNU Octave−３．６．４で上記の作成プログラムを実行したところ， 表示画像数に制約があるが問題無く動作することが分かった． 参考文献 １）http : //ja.wikipedia.org/wiki/ルービックキューブ ２）http : //kociemba.org/cube.htm３）Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge, “THE DIAMETER OF THE RUBIK’S
串 山 繁
CUBE GROUP IS TWENTY”, SIAM J. Discrete Math., Vol.27, No.2, pp.1082−1105, 2013. 6. ４）大友光司，“群論に基づくルービックキューブの数学的表現とLBL解法プログラムの作成”，北海学園大学 工学部平成２６年度卒業論文． ５）島内剛一，“ルービック・キューブ免許皆伝”，日本評論社，１９８１． ６）David Joyner，川辺治之（訳），“群論の味わい”，共立出版，２０１０． ７）http : //kjtmt.sakura.ne.jp/Rubik_Cube/index.html STEP１． ８）!メガハウス社製ルービックキューブ付属LBL法６面完成攻略書． １３１ Matlabを用いたルービックキューブのLBL解法
