ルービックキューブと群論
について
北海道情報大学 情報メディア学部
情報メディア学科 新井山ゼミ
0321604 大石 貴弘
前回までの成果
• 前回までの成果
– 幅優先探索の2×2を解くプログラム
– ルービックキューブの組み合わせ配置の内訳に
ついて
読んだ本について
• メタマジック・ゲーム
– ダグラス・R・ホフスタッター 著
– 竹内郁雄・斉藤康己・片桐恭弘 訳
– 白揚社
• 14章
• 15章
ルービックキューブと群論
• ルービックキューブは群
– 群である条件
– 結合法則
• 計算の順序を変えても同じ結果がでる場合、それを満
たす。ルーブックキューブの並びを計算される要素、
計算を回転させる行為
– 単位元の存在
• ルービックキューブの並びをaとした時にa * e = e * a
= aが成り立つために eという要素があること
• ルービックキューブの場合は『何もしない』が単位元
– 逆元の存在
• 逆の操作。右回しに対する左回し
ルービックキューブと群論
• ルービックキューブの最小手数について
– 置換群で表現(ブロックを回転させる事の集まり)
• 各方向に2方向回転することが可能
• 2×3=6のどこかを移動
– 各要素について、群作用で移動できる要素と繋いで
グラフを作成(ケーリーグラフ)
– そのグラフの直径(元と問題の面の間の距離)が最短
手数になる。
– 現在の所、計算量が多く不可能
ルービックキューブと群論
• また、ルービックキューブは、6個の回転で表され
るので
6^30=221,073,919,720,733,357,899,776
• これはルービックキューブのすべての組合せ
43,252,003,274,489,856,000通りよりも大
• どんな配置も最短解は30手以内
ルービックキューブと群論
• ルービックキューブを解くための共役の利用
– 解けている所から解けていない所を解く
• ルービックキューブの面の隣同士を入替える方法が判
っている(解き方が判明)
• 離れた所だけを入替えるには、入替えたい所を隣に
移動…A
• 隣同士を入れ替える
• Aと逆の移動をして以前の状態に逆行
今後の課題
• 知識の不足
– 数学セミナー
– 雑誌 1981年8月号
– 日本評論社 刊
の借用予定
次回までの成果誓約
• ルービックキューブについての更なる知識
習得
• 2×2を解くプログラムの制作
ダウンロード

Document