Introduction
In this series of blog posts, we’ll develop a Rubik’s cube solution from first principles, using group theory and functional programming in Scala. There are already many existing solutions; optimal solutions can be computed in a fraction of a second, and many tutorials are available online that allow humans to solve a Rubik’s cube within 20 seconds. Our goal here will be to develop a solution we can really understand; a solution that’s both simple to express as a program and easy to teach to a human.
That gives us two constraints:
- We’ll avoid directly translating speedcubing methods. On one hand, human solutions rely on cube algorithms that have been computed ahead of time and memorized. Simply porting one of these solutions doesn’t really count as “understanding” the solution. On the other hand, human solutions also rely on intuition and different types of moves that are context-dependent. This is very messy to implement as a program.
- We won’t search for an optimal solution, or even one with a low move-count. Optimal solutions require deeper mathematical background and large tables of algorithms. Even if a human can be said to understand such a solution, they wouldn’t be able to calculate and execute it.
Instead, we’ll learn about the minimal building blocks we need to invent Rubik’s cube algorithms ourselves. These will be simple and general enough so that we should be able to apply them to any similar mechanical combination puzzle (or “twisty puzzle”).
Overview of topics covered
Our solution will borrow ideas from math and functional programming. The math will help us model our problem and understand our solution. The functional programming concepts will help us express our solution in elegant terms and translate the math into our problem domain. We’ll also borrow ideas and vernacular from twisty puzzle enthusiasts, modifying the math idioms to be more cube-friendly.
Permutations
Every Rubik’s Cube scramble is essentially just a permutation of its stickers and pieces. The Rubik’s Cube is an example of what’s called a “Permutation Puzzle”. You have a small set of scrambling moves (the six face turns), which you need to combine in order to unscramble the greater puzzle.
We’ll learn about permutations, and how they can be be decomposed into smaller permutations and disjoint cycles. We can decompose larger permutations (like scrambles) into smaller cycles and transpositions. We can systematically break puzzles down into smaller problems that are more manageable.
Group Theory
As it happens, the scrambles of a Rubik’s Cube have an underlying mathematical structure called a “group” (The “Rubik’s Group”). This is useful because mathematicians have already been studying groups for centuries. Groups have structure; they’re composed of simpler subgroups that interact with each other. These simpler groups and their relationships are well understood by mathematicians, and we can use existing theorems and techniques to inform how we model both the Rubik’s Cube and its solution.
Additionally, every mathematical group is analogous to a group of permutations, so any problem involving groups structure can be expressed in terms of permutations. Permutations are computationally simple to work with, and we can re-use everything we’ve learned about permutations to work with groups in the abstract.
Along the way, we’ll learn about subgroups, direct products, group actions, and homomorphism. This isn’t technically required to understand the solution, but it still serves as great example of how math can reduce the amount of work to be done by puzzle solvers and programmers alike. This section is for the nerd inside all of us that wants to really grok how things work.
Functional Programming
We’ll tie this all together with functional programming: permutations are a special type of function called a bijection, which means they always have an inverse. We’ll see how these functions can be composed with their inverses in specific ways that allow us to create custom permutations with desirable effects. This will be important, because once we break down a scramble into smaller cycles and transpositions, we’ll need to be able to invent algorithms that solve those smaller problems.
We’ll also learn about how groups relate to existing FP typeclasses that we might already be familiar with (Semigroups and Monoids). This is important because it’ll allow us to leverage techniques and libraries already used and taught by the FP community. In short groups allow us to leverage existing ideas from both Math and Functional Programming to simplify our approach to crafting a solution.
List of Articles:
- Part 1: Permutations as Functions
- Part 2: The Group Typeclass
- Part 3: Cycles, Swaps, and Permutations (upcoming)
- Part 4: Cube Algorithm DSL as a Group (upcoming)
- Part 5: Combinations, Conjugates, and Commutators (upcoming)
- Part 6: Modeling Rubik’s Cube State in Scala (upcoming)
- Part 7: Putting it all together (upcoming)