Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
1 contributor

Users who have contributed to this file

144 lines (141 sloc) 4.48 KB

Introduction

Hello!

All you really need to know

Commutators and Conjugate

  • Inverse: A’ reads “A inverse”
  • Commutator: A B A’ B’
  • Conjugate: C Algorithm C’

How-to

  1. Invent a Commutator
  2. Use a Commutator
  3. ???
  4. Profit!

Goals

  • Practical? Maybe.
  • How math informs solution
  • Have fun with Math + Puzzles + Programming
  • Ask questions!

Group Theory

Define Group

Monoid w/ Inverse

trait Group[A] {
  def identity: A
  def inverse(a: A): A
  def combine(a: A, b: A): A
}

Permutation Group

  • Consider Finite Groups
  • Inverse && complete =>

Every element

  • is a bijection

Every element is

  • a permutation

Every group is

  • isomorphic to a permutation group!

Examples

Integers & Cyclic Groups

S3/D3 & Cayley Graph

Street Map Directions

Concepts

Parity

  • Permutations decompose into disjoint cycles
  • Cycles decompose into sum of swaps
  • 3-Cycles are even
  • Even/odd, positive/negative, true/false

Conjugate

  • A B A’
  • A: setup moves
  • B: useful alg

Commutator

  • A B A’ B’
  • Measure of non-abelian-ness
  • Even permutation
  • Minimal intersection is a 3-cycle

Rubik’s Cube

Mechanical Structure

48 stickers: A Permutation!

  • Center stickers are stationary
  • “Homomorphism into S48”
  • ie., permutation of 48 points
  • Difficult to see structure
  • Array[Int] contains many illegal scrambles

21 pieces: Product of disjoint Permutations

  • Stickers cluster on pieces
  • 8 corners, 12 edges, 1 core
  • Edge and Corner pieces are distinct
  • Centers pieces are fixed to core
  • 8! * 3^8 * 12! * 2^12 ???
  • Not quite…

Piece Orientations (demo)

  • Each corner has 3 orientations
  • Each edge has 2 orientations
  • Orientation definitions are arbitrary

Group Structure

Generators

  • <U, D, R, L, F, B>
  • Each is a paired 4-cycles
  • Edge and corner parity are synced
  • Orientation of final piece is fixed

Subgroups

  • CO: Corner Orientation
  • CP: Corner Permutation
  • EO: Edge Orientation
  • EP: Edge Permutation
  • Orientation is Normal
  • Semidirect product of Orientation and Permutation
  • Or subdirect product of Edges and Corners

Minimal operations (summary)

  • Orientation flips are paired
  • 3-cycles of edges/corners
  • or swap 2 edges and 2 corners

43 quintillion

  • (8! * 12!) * 3^8 * 2^12 (overcounts)
  • (8! * 12!)/2 * 3^7 * 2^11 (corrected)

Solution

Approaches

Thistlewaite (Computers)

  • <U2, D2, R2, L2, F2, B2> - Half-turn subgroup (even perm)
  • <U, D, R2, L2, F2, B2> - CO preserved
  • <U, D, R, L, F2, B2> - EO preserved
  • <U, D, R, L, F, B> - Full Rubik’s Group

Layer-by-layer (Humans)

  • Demo
  • CFOP: Cross, F2L, Orientation, Permutation

Blind (Cycle decomposition)

  • Memorize Cycles
  • eg. CubeState
  • Commutators!
  • No demo. (sorry)

Model (Demo Code)

Cube State

https://github.com/stewSquared/twisty-groups/src/main/scala/twistygroups/cube/model/CubeState.scala

Algorithms DSL

https://github.com/stewSquared/twisty-groups/src/main/scala/twistygroups/cube/algs/Alg.scala

Corner Commutators (Live Coding Demo)

https://github.com/stewSquared/twisty-groups/src/main/scala/twistygroups/example/CornerComms.scala

Solve! (Cube Demo)

Resources and References

Libraries

Reading

Buy Puzzles

You can’t perform that action at this time.