Document

ルービックキューブについて
北海道情報大学情報メディア学部
情報メディア学科新井山ゼミ
0321604 大石貴弘
前回までの成果
• 前回までの成果
– 15パズルについてのプログラム
– ルービックキューブについての下調べ
今回までの進捗状況
• ルービックキューブについて
– 3×3のルービックキューブの組み合わせ配置の
内訳
– 2×2のプログラム
2×2のプログラム
• 幅優先探索で探索
– 予想より盤面の種類が多数
– メモリの負担が多大
→非効率的
ルービックキューブの組み合わせ配置
• ルービックキューブは
– 辺の中央にあるパーツ（2面に色） 12個
– 頂点にあるパーツ（3面に色） 8個
– 面の中心にあるパーツ（1面に色） 6個
ルービックキューブの組み合わせ配置
• これをバラバラにして1から組みなおす場合
– 面の中心は動かない
– 辺のパーツ 12個を順に並べる。さらにそれぞれについ
て色の置き方が各2種類
→ 12！ × 2^12（2の12乗）
– 頂点にあるパーツ 8個を順に並べるそれぞれについて
の色の置き方が各3種類
→ 8！ × 3^8
上記のふたつをかけたものが組み合わせの総数 … (1)
ルービックキューブの組み合わせ配置
• さらにそこから、６面をそろえた状態から到達
できない盤面を省く
– 辺の中央のパーツについて
– 色が入れ替わっている数の合計は常に偶数
→ (1)から入れ替わっている数が奇数の盤面を引
く
– 入れ替わっている数は奇数か偶数か分けられ
るので、盤面の数は 1 / 2
ルービックキューブの組み合わせ配置
– 頂点のパーツ色が入れ替わっている数の合計
が常に3の倍数
– バラバラから組み立て場合、色が入れ替わって
いる箇所は1から２４まで
– その中で3の倍数は1/3 よって（1）の盤面も1/3
• 最終的に組み合わせの数は
• 12!×2^12 × 8!×3^8 ／（2×3）
＝ 43,252,003,274,489,856,000 通り
群論について
• 『群』論……数学の分野
• 前記のふたつの条件は群論によって判断
• ルービックキューブの解法は『群』論で説明
次回までの成果誓約
• 『群』論とルービックキューブの関わり

Download Report