ルービックキューブをコンピュータで解く考え方

ルービックキューブを コンピュータで解く考え方 宇佐見公輔 2025-02-16 / 第 32 回日曜数学会

自己紹介 • 宇佐見公輔（うさみこうすけ） • 本業はプログラマー 近況 月刊 I/O に記事をいくつか書きました • 8〜9 月号 : ルービックキューブの解法 • 10 月号 : パズルキューブ スクエア 1 • 12 月号 : 組版ソフトウェア Typst 1 / 21

今回の話 ルービックキューブの解法はコンピュータ計算で求めることが可能で す。その考え方を、群論の言葉を使って説明します。 ルービックキューブを理解するためにわざわざ群論の言葉を使う必要 はないのですが、使うとシンプルにとらえることができます。 余談 実は以前、ルービックキューブと群論の話をしました。 • ルービックキューブと群論 ‣（第 7 回関西日曜数学友の会 / 2020-10-03） • ルービックキューブ群を SageMath で見る ‣（第 19 回日曜数学会 / 2020-10-31） 2 / 21

ルービックキューブ群

ルービックキューブ 今回は標準的な 3x3x3 のルービック キューブを扱います。 ルービックキューブを解くとは、各面の色 がバラバラになっている状態から、面を回 転させる操作によって、完成状態（各面が 1 色）にすることです。 ルービックキューブ群 4 / 21

基本操作 𝑈 / 𝐷 / 𝐹 / 𝐵 / 𝑅 / 𝐿 : 各面を時計回りに 90 度回転 （図は https://tribox.com/3x3x3/solution/notation/ より引用） ルービックキューブ群 5 / 21

• https://tribox.com/3x3x3/solution/notation/

ルービックキューブ群 基本操作で生成される置換群を、ルービックキューブ群と呼びます。 𝐺 = ⟨𝑈, 𝐷, 𝐹, 𝐵, 𝑅, 𝐿⟩ • 単位元 1 : 完成状態 • 𝑅 : 完成状態から右面を時計回りに 90 度回転 • 𝑈𝑅 : 右面を 90 度回転、さらに上面を 90 度回転 補足 記法の都合上、右から順に操作を適用することにしておきます。 ルービックキューブ群 6 / 21

ルービックキューブの解法

主な解法 コーナー・エッジ法 • まずコーナーだけ揃え、次にエッジを揃える • 数学的な理屈として自然な発想 LBL（Layer by Layer）法 • 1 段目、2 段目、3 段目の順に揃える • 初心者向けの手順が整備されている CFOP 法 • Cross、F2L、OLL、PLL の 4 段階で揃える • スピード競技向けにパターン化されている ルービックキューブの解法 8 / 21

CFOP 法 Cross F2L (First 2 Layers) OLL (Orientation of the Last Layer) PLL (Permutation of the Last Layer) ルービックキューブの解法 9 / 21

共通する考え方 • まず、一部分を完成状態にする • 次に、完成部分を崩さずに、他の部分を完成状態にする • これを何段階かにわけて行う 補足 •「完成部分を崩さずに」 ‣ 一時的には崩れても、あとで元に戻るような手順を使う •「何段階かにわけて」 ‣ たとえば CFOP 法なら 4 段階にわけている ルービックキューブの解法 10 / 21

解法を群論の言葉で

部分群で考える • 解法の考え方「完成部分を崩さずに」 ↓ • 完成部分を崩さない操作手順だけを使う ↓ • 完成部分を崩さない操作がなす部分群で考える 解法を群論の言葉で 12 / 21

部分群の系列を考える • 解法の考え方「何段階かにわけて」 ↓ • 部分群の系列を考える 𝐺 = 𝐺 0 ⊃ 𝐺 1 ⊃ 𝐺 2 ⊃ … ⊃ 𝐺 𝑛 = {1} 解法を群論の言葉で 13 / 21

剰余類を使う 𝐺 = 𝐺 0 ⊃ 𝐺 1 ⊃ 𝐺 2 ⊃ … ⊃ 𝐺 𝑛 = {1} 𝐺 𝑘 から 𝐺 𝑘+1 への移行は、左剰余集合 𝐺 𝑘 /𝐺 𝑘+1 を考えます。 • 𝑔𝑘 ∈ 𝐺 𝑘 を含む左剰余類 𝑥𝐺 𝑘+1 をとる • 𝑔𝑘+1 ≔ 𝑥−1 𝑔𝑘 とすると、𝑔𝑘+1 ∈ 𝐺 𝑘+1 となる 解法を群論の言葉で 14 / 21

CFOP 法を群論の言葉で 𝐺 = 𝐺 0 ⊃ 𝐺 1 ⊃ 𝐺 2 ⊃ 𝐺 3 ⊃ 𝐺 4 = {1} • 𝐺 1 : Cross を崩さない操作がなす部分群 • 𝐺 2 : F2L を崩さない操作がなす部分群 • 𝐺 3 : OLL を崩さない操作がなす部分群 • 𝐺 4 : PLL を崩さない操作がなす部分群（完成状態のみ） • Cross を揃える : 𝐺 から 𝐺 1 へ（𝐺/𝐺 1 の元を探す） • F2L を揃える : 𝐺 1 から 𝐺 2 へ（𝐺 1 /𝐺 2 の元を探す） • OLL を揃える : 𝐺 2 から 𝐺 3 へ（𝐺 2 /𝐺 3 の元を探す） • PLL を揃える : 𝐺 3 から 𝐺 4 へ（𝐺 3 /𝐺 4 ≃ 𝐺 3 の元を探す） 解法を群論の言葉で 15 / 21

コンピュータで解く考え方

部分群の系列を考える 人間が解くための解法では、それぞれの段階の完成状態が認識しやす いものでないと困ります。 （Cross 状態、F2L 状態、など） しかし、コンピュータで解く場合はそのような制約はなく、自由に部 分群の系列を考えることができます。 補足 剰余類を使うので、単なる部分集合でなく部分群を考えます。 コンピュータで解く考え方 17 / 21

コシエンバ法（Two Phase Algorithm） 𝐺 = 𝐺 0 ⊃ 𝐺 1 ⊃ 𝐺 2 = {1} 𝐺 1 ≔ ⟨𝑈, 𝐷, 𝐹 2 , 𝐵2 , 𝑅2 , 𝐿2 ⟩ • 𝐺/𝐺 1 の元を探す • 𝐺 1 /𝐺 2 ≃ 𝐺 1 の元を探す 𝐺 1 は次のような特徴があります。 • 各ピースの向きを変えない • U 面や D 面を側面に移動できない （https://kociemba.org/twophase.htm に解説があります） コンピュータで解く考え方 18 / 21

• https://kociemba.org/twophase.htm

コシエンバ法の手数 • 𝐺/𝐺 1 の剰余類の代表元は、高々 12 手である • 𝐺 1 の元は、高々 18 手である • この 2 つの群の元を探すことで、高々 29 手で解く手順が見つかる 手数が少なめで、それぞれの元の探索は、アルゴリズムの工夫により 実用的な時間で行えます。 （今回はこのあたりの話は省略） コンピュータで解く考え方 19 / 21

まとめ

群論の言葉は便利 • ルービックキューブの解法は、群論の言葉を使って説明できる • 必要な知識は、部分群や剰余類といった基本的なものだけ まとめ 21 / 21