Notes on Tuple Representation of Rubiks Cube

Let's first explain what we mean when we talk about a tuple representation of a cube, and why this is useful.

Tuple Representation

A tuple representation means, we are representing one possible permutation of the Rubik's Cube using a tuple, ideally a tuple of N items arranged in some particular way.

Now, if we think about how a 3x3 Rubik's Cube or 4x4 Rubik's Revenge is mechanically constructed, we see that the cube consists of:

Rubik's Cube: 26 total (mechanical) pieces

8 corner pieces
12 edge pieces
6 center pieces

Rubik's Revenge: 56 total (mechanical) pieces

8 corner pieces
24 double-edge pieces (12 left-hand, 12 right-hand)
24 center pieces

However, it is important to note that we are not trying to find the minimal representation of the Rubik's Cube, we are simply trying to find a unique representation of a Rubik's Cube. Representing faces requires more information than representing pieces, but it is a lot simpler and accomplishes what we need:

The 3x3 Rubik's Cube has 9 squares on each face, and 6 faces, for a total of 36 squares.
The 4x4 Rubik's Revenge has 16 squares on each face, and 6 faces, for 96 total squares.

Now, if we were looking for a minimal representation, we would utilize the fact that some of these squares are innately linked (for example, the three faces representing a corner piece are always positioned in the same way relative to one another, even though they may move relative to the rest of the pieces on the cube).

However, we simply want a unique representation, so we can represent the state of any 3x3 Rubik's Cube using a 36-tuple, or the state of any 4x4 Rubik's Revenge using a 96-tuple.

Why A Tuple Representation

Finding a tuple representation enables us to study the properties of various move sequences and understand how the cube works.

For example, if we repeatedly apply any sequence of moves to a Rubik's Cube, eventually it will return back to the solved state. To predict how many times a sequence must be applied to a cube to return to the solved state, we can use techniques demonstrated by Donald Knuth in Volume 3 of The Art of Computer Programming (see AOCP) to derive a permutation algebra, factor permutations into cycles, and find the sequence length via the lcm of each cycle length.

Tuple representation: https://github.com/charlesreid1/rubiks-cycles/blob/master/tup.py

4x4 Rubiks Cube Representation

Numbering System

Start with a numbering system for the cube. The nxnxn rubiks cube solver library I'm using (https://github.com/dwalton76/rubiks-cube-NxNxN-solver) implements the following numbering system:

             01 02 03 04
             05 06 07 08
             09 10 11 12
             13 14 15 16

17 18 19 20  33 34 35 36  49 50 51 52  65 66 67 68
21 22 23 24  37 38 39 40  53 54 55 56  69 70 71 72
25 26 27 28  41 42 43 44  57 58 59 60  73 74 75 76
29 30 31 32  45 46 47 48  61 62 63 64  77 78 79 80

             81 82 83 84
             85 86 87 88
             89 90 91 92
             93 94 95 96

corresponding to the following cube state:

         U U U U
         U U U U
         U U U U
         U U U U

L L L L  F F F F  R R R R  B B B B
L L L L  F F F F  R R R R  B B B B
L L L L  F F F F  R R R R  B B B B
L L L L  F F F F  R R R R  B B B B

         D D D D
         D D D D
         D D D D
         D D D D

Now we can write the solved cube as the following 96-tuple:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96]

Moves as Permutations

Each move of a face - U, D, R, L, F, B, and other two-layer or second-layer moves, as well as sequences of moves - can now be thought of as a permutation of these 96 integers.

I modified the nxnxn rubiks cube library to print out the permutation corresponding to each type of move. For example, here is U:

In [7]: r.rotation_map('U')
Out[7]:
[(1, 13),
 (2, 9),
 (3, 5),
 (4, 1),
 (5, 14),
 (6, 10),
 (7, 6),
 (8, 2),
 (9, 15),
 (10, 11),
 (11, 7),
 (12, 3),
 (13, 16),
 (14, 12),
 (15, 8),
 (16, 4),
 (17, 33),
 (18, 34),
 (19, 35),
 (20, 36),
 (33, 49),
 (34, 50),
 (35, 51),
 (36, 52),
 (49, 65),
 (50, 66),
 (51, 67),
 (52, 68),
 (65, 17),
 (66, 18),
 (67, 19),
 (68, 20)]

Now the starting state of a cube can be written as the above tuple, and rotations of various faces can be written as permutations.

Once we can write a sequence of moves as a permutation of 96 integers, we can start to dig deeper into the effect that it has on the cube state.

Permutation Algebra

In order to create a system for talking about and dealing with permutations, we follow Volume 3 of Knuth's The Art of Computer Programming (see AOCP).

Writing a Permutation

Knuth introduces the top-bottom notation for permutations, in which a particular permutation of a sequence of $$ n $$ integers is written by first writing each element of the sequence in increasing order on the top row, then writing the occurrence of each element in the order it occurs on the bottom row:

$a = \bigl(\begin{smallmatrix} 1 & 2 & 3 & \cdots & n-1 & n \\ 2 & 3 & 4 & \cdots & n & 1 \end{smallmatrix}\bigr)$

Intercalation Product

We now define an intercalation operation with two permutations; this is basically an operation that interleaves two permutations. We will see why this is useful in a moment.

Suppose we have two permutations, $\alpha$ and $\beta$ , of four objects $\{a, b, c, d\}$ , each occurring multiple times:

$\alpha = \bigl(\begin{smallmatrix} a & a & b & c & d \\ c & a & d & a & b \end{smallmatrix}\bigr)$

$\beta = \bigl(\begin{smallmatrix} a & b & d & d & d \\ b & d & d & a & d \end{smallmatrix}\bigr)$

Then we can define the intercalation product $\alpha \top \beta$ as the elements of these permutations combined in a way that interleaves elements of both, in a way that groups all elements by the letter on the top row, but sorts within those letters according to the original order in $\alpha$ and $\beta$ . For our example:

$\alpha \top \beta = \bigl(\begin{smallmatrix} a & a & b & c & d \\ c & a & d & a & b \end{smallmatrix}\bigr) \top \bigl(\begin{smallmatrix} a & b & d & d & d \\ b & d & d & a & d \end{smallmatrix}\bigr) = \bigl(\begin{smallmatrix} a & a & a & b & b & c & d & d & d & d \\ c & a & b & d & d & a & b & d & a & d \end{smallmatrix}\bigr) =$

This is basically an interleaving operation. All top-bottom pairs with $$ a $$ at the top are grouped together; all from $\alpha$ come first, and all from $\beta$ come second.

The first two $$ a $$ items in $\alpha \top \beta$ come from $\alpha$ , the third $$ a $$ item comes from $\beta$ .

Etc.

Properties of Intercalation

Before using the intercalation product, let's define a few properties :

If $\alpha \top \pi = \beta \top \pi$ or $\pi \top \alpha = \pi \top \beta$ this implies $\alpha = \beta$
Identity element exists such that $\epsilon \top \alpha = \alpha \top \epsilon = \alpha$
Commutative property only holds if $\alpha$ independent of $\beta$ ; then $\alpha \top \beta = \beta \top \alpha$ . This property does not hold in general.

Cycles and Intercalation

Cycles are elements that are swapped in some prescribed way. For example, suppose we have a sequence,

$\bigl(\begin{smallmatrix} x_1 & x_2 & \dots & x_n \end{smallmatrix}\bigr)$

and further suppose that we shift this sequence to the left by one element, and write in the two line notation:

$\bigl(\begin{smallmatrix} x_1 & x_2 & \dots & x_{n-1} & x_n \\ x_2 & x_3 & \dots & x_{n} & x_1 \end{smallmatrix}\bigr)$

We can observe that the product of disjoint cycles is the same as their intercalation.

Now we have a full "product" permutation.

Factoring Permutations

Suppose we have a permutation:

$\pi = \bigl(\begin{smallmatrix} a & a & b & b & b & b & b & c & c & c & d & d & d & d & d \\ d & b & c & b & c & a & c & d & a & d & d & b & b & b & d \end{smallmatrix}\bigr)$

and suppose that we want to "factor" the permutation - that is, to write the permutation as the intercalation product of independent, disjoint cycles $\pi = \alpha \top \beta \top \dots \top \gamma$ .

We can assemble each factor one at a time using the following algorithm:

Start by supposing that the first factor $\alpha$ contains the first symbol $$ a $$ . If this assumption is true, then $\alpha$ must map $$ a $$ to the same thing that the final permutation maps $$ a $$ to, namely, the first column of $\pi$ , which is the combination $\begin{smallmatrix} a \\ d \end{smallmatrix}$ . This means that the first entry in $\alpha$ must turn $$ a $$ into $$ d $$ .

Now we suppose that $\alpha$ contains $$ d $$ , as a consequence of the prior step. Let's find the leftmost $$ d $$ in the top line, and see what symbol it will map to. It maps to b. This means that the first entry in $\alpha$ must turn $$ d $$ into $$ d $$ and should therefore contain $\begin{smallmatrix} d \\ d \end{smallmatrix}$

Now we start with the outcome of the previous step, which is another $$ d $$ . Since we already used the first d-d pairing, we look for the second leftmost d, which is part of the combination/mapping $\begin{smallmatrix} d \\ b \end{smallmatrix}$ . This implies the mapping d-b should be in $\alpha$ , and we use the mapping outcome b as the starting point for the next step.

If we keep doing this, eventually we will get:

$\alpha = \begin{smallmatrix} a & d & d & b & c & d & b & b & c \\ d & d & b & c & d & b & b & c & a \end{smallmatrix}$

Pause:

Let's pause for a moment and see what's happening. What we're doing is following a thread between the top and bottom rows of the permutation; this thread tells us how elements are being moved around to create permutations.

(A simpler but easier way to see this is by comparing two permutations of 1 2 3 4 5 6: consider the permutation 2 1 3 4 6 5, versus the permutation 2 4 5 6 1 3. The first permutation swaps positions 0 and 1, and positions 4 and 5, independently; the second permutation mixes all positions together.)

We are assembling $\alpha$ piece by piece, by pulling out pairs from the top and bottom row of $\pi$ and putting them into $\alpha$ . At some point we will come back to the starting point, the symbol $$ a $$ , and we will be finished finding the first factor $\alpha$ , which is a disjoint cycle.

Resume:

We then continue the process of assembling factors from what is left of $\pi$ . (Note that if $\pi$ is prime, every element of $\pi$ will appear in $\alpha$ and there will be no further products.) Eventually we will have a number of factors,

$\pi = \alpha \top \beta \top \dots \top \gamma$

The result of applying this procedure, of skipping between the top and bottom rows, is a set of 1 or more permutation factors. If we continue with the example $\pi$ above, we'll eventually get: