Group Theory

First, we have to build a foundation of how we can represent Rubik’s Cubes in the language of mathematics. That foundation is called group theory. A group is defined to be a set equipped with an operation (denoted or ) that follows the following group axioms:

• There exists an identity element such that for any element of the group , .
• For all elements , , , . In other words, the operation is associative.
• For each in the group, there exists such that . In other words, every element has an inverse with respect to the group operation.

Importantly, commutativity is not required. So let’s see how this definition applies to the Rubik’s Cube. To form a group, we need a set, and for the Rubik’s Cube, this set is the infinite set of all move sequences that you can apply to a puzzle. For example, doing nothing is an element of the set. If you turn the top face then that’s an element of the set. If you just scramble your cube randomly, then even that sequence of moves is part of the set.

Next, we need an operation. For the Rubik’s Cube, this will be jamming together the sequence of moves. We will call this operation composition because it is very similar to function composition.

Now, let’s verify that all of the group axioms hold. First, we need an identity element. This identity is simply the “do nothing” sequence! Lets verify this, and let be an arbitrary scramble:

Regardless of what the first move sequence is, appending the “do nothing” algorithm will lead to the same sequence. Next, lets verify associativity, letting , , and be arbitrary scrambles.

Because of the nature of how jamming together algorithms works, parentheses can essentially be ignored. Therefore, the composition operation is associative. Finally we must show that every sequence of moves has an inverse. In our case, an inverse exists simply because we can undo the entire move sequence. Here is an algorithm to find that inverse:

function inverse(moves: List<Move>): List<Move> {
  reverse(moves)
  for (move in moves) {
    if move.ends_with("'") {
      remove(`'` from move)
    } else if move.ends_with("2") {
      // Leave it
    } else {
      append(`'` to move)
    }
  }
  return moves
}

function inverse(moves: List<Move>): List<Move> {
  reverse(moves)
  for (move in moves) {
    if move.ends_with("'") {
      remove(`'` from move)
    } else if move.ends_with("2") {
      // Leave it
    } else {
      append(`'` to move)
    }
  }
  return moves
}

This works because any clockwise base move X cancels with it’s counterclockwise pair X’ and vice versa, and any double turn X2 cancels with itself.

Next, it is important to distinguish a cube state from an algorithm to reach that cube state. We just described a group of Rubik’s cube algorithms but not a group of Rubik’s cube states. We can say that the group of Rubik’s cube algorithms is an action on the group of Rubik’s cube states. It turns out that Rubik’s cube states can actually form a group by themselves without having to think about algorithms. We will explore this group of Rubik’s cube states next, because it turns out that it is much more amenable to mathematical analysis and representation inside of a computer. After all, move sequences alone don’t give us insight into the structure of the puzzle itself.