# 4x4 Rubik's Cube: Part 3: Factoring Permutations

Posted in Rubiks Cube

This is Part 3 of a 4-part blog post on the mathematics of the 4x4 Rubik's Cube, its relation to algorithms, and some curious properties of Rubik's Cubes.

See Part 1 of this blog post here: Part 1: Representations

See Part 2 of this blog post here: Part 2: Permutations

You are currently reading Part 3 of this blog post: Part 3: Factoring Permutations

See Part 4 of this blog post here: Part 4: Sequence Order

# Introduction

So far we have been discussing representations of the Rubik's Cube, with the ultimate intention of investigating some of its properties.

In this post, we define and explore the properties we are interested in studying.

## Cycles

(Definition of cycle)

We use the two-line notation introduced in the last blog post, so a permutation of a 5-tuple might look like this:

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

In this permutation, we see that $$a$$ and $$b$$ swap places, and $$c$$, $$d$$, and $$e$$ exchange places as well. These two groups form two cycles.

Think of the cycles as the particular way that pieces of the permutation are exchanged with one another.

## Sequences

We are interested in studying the properties of the cube, but in particular we are interested in the properties of move sequences applied to the cube.

There are 36 possible moves on a cube, and a series of moves applied in a particular order defines a sequence. The 36 possible rotations were given in the prior blog post and cover clockwise and counterclockwise rotations of each of the six faces - either the first layer, the second layer, or both of the first two layers.

These moves are denoted with six letters (UDLRFB) for the upper, downward, left, right, front, and back face of the cube, respectively.

Moves indicated should be clockwise unless they contain an apostrophe character ', which indicates counterclockwise rotation.

A capital letter indicates a rotation of the first layer only (e.g., U indicates a clockwise rotation of the first layer of the upper face).

A lowercase letter indicates a roration of the first and second layers (e.g., r indicates a clockwise rotation of the top two layers of the right face).

A 2 before the letter indicates that the second layer should be rotated (e.g., 2F indicates a clockwise rotation of the second layer of the front face).

Each move sequence can be translated into a tuple representation (see Part 1 blog post). Once we have the tuple representation of a permutation, we can do several things, beginning with finding the cycles that compose the moves of the sequence.

## Order

The quantity we are truly interested in is the order of a given cycle.

The order of a sequence of moves is the number of times that sequence must be applied to the cube to get the cube to return back to its original state. A more convenient way to think about it is, if you applied a move sequence to a solved cube, how many times would you have to apply it until you reached a solved cube again?

We begin with the move sequence, which applies a particular permutation to the cube, exchanging particular pieces in a particular order. We want to obtain a tuple representation of the permutation that results from a particular sequence of moves.

Once we have the tuple representation of a sequence's permutation, we can factor it into independent cycles using the techniques covered in this blog post.

The factoring a permutation into cycles will yield the order; the order is the least common multiple of the lengths of eacch cycle that is a factor.

Using this, we can investigate the properties of the order of different move sequences.

# Intercalation Product

In Part 2 of this blog post, we discussed the tuple representation of a permutation; for example, one permutation $$\pi$$ of an $$n$$-tuple might be written:

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

The top row consists of the elements in the tuple in sorted order; the second row consists of elements of the tuple corresponding to that permutation.

In the discussion that follows we'll keep it general, and talk about multisets - the case in which the top row has multiple occurrences of different items.

For the following discussion, we will suppose two permutations $$\alpha$$ and $$\beta$$ composed 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)$$

## Definition

Now we define the intercalation product $$\alpha \top \beta$$ of these permutations as the elements of each permutation organized in an interleaved way - each element of $$\alpha$$ and $$\beta$$ are grouped by the letter that appears on the top row, and within those groups they are ordered as they appear in $$\alpha$$, then as they appear in $$\beta$$.

For our example, the intercalation product is the following combination of $$\alpha$$ and $$\beta$$:

$$\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 - and within the group, everyone from $$\alpha$$ comes first, everyone from $$\beta$$ comes second.

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

### Side Note: Why Define an Intercalation Product?

You may be wondering what the intercalation product has to do with Rubik's Cubes or finding the order of a sequence. It turns out that the intercalation product will allow us to establish a system of permutation algebra, define certain operations and properties of permutations, and use these to factor permutations into independent groups of faces being exchanged.

## Properties

We can state some properties of the intercalation algebra already:

If $$\alpha \top \pi = \beta \top \pi$$ or $$\pi \top \alpha = \pi \top \beta$$, this implies $$\alpha = \beta$$.

An identity element exists such that $$\epsilon \top \alpha = \alpha \top \epsilon = \alpha$$.

The commutative property for the intercalation product (whether $$\alpha$$ and $$\beta$$ can be exchanged in expressions) only holds if $$\alpha$$ and $$\beta$$ are independent of each other (if they permute different elements). If this condition holds, then $$\alpha \top \beta = \beta \top \alpha$$.

This property does not hold in general.

(An example of permutations that would be independent on the Rubik's Cube would be the moves U and D. These each rotate a different group of faces.)

# Factoring Permutations Using Knuth's Theorem A

Volume 3 of Donald Knuth's The Art of Computer Programming gives the following theorem on page 26, which gives a very useful property of intercalation products:

Theorem A. Let the elements of the multiset $$M$$ be linearly ordered by the relation "<". Every permutation $$\pi$$ of $$M$$ has a unique representation as the intercalation

$$\pi = ( x_{1,1} \dots x_{1,n_1} y_1 ) \top ( x_{2,1} \dots x_{2,n_2} y_2 ) \top \dots \top ( x_{t,1} \dots x_{t,n_t} y_t )$$

where

$$y_1 \leq y_2 \leq \dots \leq y_t$$

and

$$y_i < x_{ij} \qquad \mbox{ for } 1 \leq j \leq n_i, 1 \leq i \leq t$$

## Significance of Factors

Theorem A is central to our goal of studying move sequences (and computing their order). To understand why, consider the factors that result from Theorem A, and what they mean in the specific example of a Rubik's Cube.

In a regular n-tuple, the factors represent groups of items in the tuple that are being exchanged. A tuple that factors into the intercalation of many very small tuples means the permutation mostly consists of swapping pairs or triplets of things. A tuple that factors into the intercalation of two large tuples means, all of the things are divided into two groups, and within that group, everybody is mixed in with everybody else.

On a Rubik's Cube, the tuple consists of faces being moved, so a permutation's factors indicate how many faces are being swapped. The size of each group of faces gives some indication as to how long it takes for the cube to "sync up" with its original state if the permutation is repeatedly applied; a permutation with fewer large factors will take longer than a permutation with many small factors.

For example, suppose a move sequence permutes three corner pieces on a cube each time it is applied. Then if we write the two-line tuple corresponding to that permutation, and we factor it into the intercalation product of several tuples, several factors of the permutation will have a length of three, and will contain the set of three faces being exchanged.

On the other hand, if a move sequence permutes six corner pieces on a cube each time it is applied, some of the factors will be groups of six faces being exchanged when the sequence is applied.

Thus, the (sizes of the) factors of a permutation determine the order of the permutation.

## How to Factor Permutations

To factor a permutation, we perform the opposite of the intercalation product. Now supppose we wish to factor the 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)$$

into the intercalation of multiple independent, disjoint cycles,

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

We can extract each factor one at a time using the following algorithm.

Start by assuming the first factor $$\alpha$$ contains the first symbol $$a$$ in its top row.

(It turns out this assumption can't be false - if there is an $$a$$ in the top row of $$\pi$$ then there is an $$a$$ in the top row of at least one factor. We're simply going to pull out those factors with this assumption.)

Given this assumption, we know $$\alpha$$ must map $$a$$ to the same letter as the final permutation maps $$a$$ to, in the very first column of $$\pi$$. The first column of $$\pi$$ is $$( a d )$$ (a on top, d on bottom). That means that if our assumption holds, if $$\alpha$$ contains $$a$$, then it must permute all $$a$$'s into $$d$$'s and thus $$\alpha$$ should contain the same column $$(a d )$$.

Now suppose that $$\alpha$$ contains $$d$$, which it must if our prior step is true. ($$\alpha$$ cannot turn $$a$$ into $$d$$ if it does not have a $$d$$!). We find the leftmost $$d$$ on the top line, and see that it maps to the symbol $$d$$, due to the column $$( d d )$$ (d on top, d on bottom). Thus, $$\alpha$$ should also contain the column $$( d d )$$.

We keep going. Suppose that $$\alpha$$ contains another $$d$$, as a consequence of the prior step. Since we already used the first d column in $$\pi$$, we use the next column, $$( d b )$$ Thus, $$\alpha$$ should also contain the column $$( d b )$$, and we use the outcome $$b$$ as the starting point for the next step.

The process stops as soon as the starting point for the next step is the letter we began with, $$a$$. That's because, at that point, we've formed a "closed loop" of pieces that permute with one another. That closed loop forms the first intercalation factor of the permutation $$\pi$$.

If we keep repeating the process described, we eventually wind up with $$\alpha$$:

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

### Side Note: Why Does This Work?

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.

By starting from the top row and following where it leads in the bottom row, and continuing until we return to the original starting element in the top row, we can carve up the permutation into groups of pieces exchanged with one another and not with any other pieces, or groups of pieces that don't move.

## How to Factor Permutations (Cont'd)

Recall that our goal was to factor the permutation $$\pi$$ into the intercalation of multiple independent and disjoint cycles, $$\pi = \alpha \top \beta \top \dots \top \gamma$$. We gave a procedure to extract factors and used it to extract the first factor, $$\alpha$$.

However, this is not the end of the factoring process: there are still several elements of $$\pi$$ that have not been used to form $$\alpha$$, and those remaining elements themselves form a permutation that can be factored.

We begin with the original permutation $$\pi$$:

$$\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)$$

When we pull out the first factor $$\alpha$$, we get:

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

When we pull out the second factor $$\beta$$, we get:

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

The third factor can be pulled out as well, which leaves the last factor, a single column $$( d d )$$ by itself, indicating an element that is not moved by the permutation.

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

Thus the permutation $$\pi$$ can be expressed as the intercalation of four independent cycles.

This procedure illustrates Knuth's Theorem A.

(Note: had we initially assumed $$\alpha$$ contained $$b$$ instead of $$a$$, we would end up starting by pulling out a different factor, but we would ultimately end up with the same set of four factors.)

To relate this back to the Rubik's Cube, we can start with a sequence of interest, like U R D D B, and write the tuple representing the outcome of this sequence when it is applied to the cube. In this way we represent a move sequence as a tuple or as a permutation.

Next, we factor this permutation the way we factored $$\pi$$, into the intercalation product of independent cycles. These are groups of pieces being swapped each time the cycle is applied.

Now if one factor is of length 4 (group of 4 faces being permuted), one factor is of length 3, and one factor is of length 20, then the number of times the sequence must be applied before the cube will come back to its original, solved state is $$LCM(3,4,20) = 60$$.

## Algorithm A

Algorithm A is an algorithm written to perform the factoring process described above.

We started with the two-row representation above, so our function will start with the top and bottom rows of the two-row representation.

The procedure started with the first entry of the top row, and got the corresponding entry of the bottom row. It then moved to the index of that item on the top row, and got the coresponding entry of the bottom row, and so on, assembling the components of the permutation by stepping through each.

In code, this will require us to switch between items in a list, and the indices of occurrencs of items in the list. Fortunately, this is an easy and common operation.

Following is the pseudocode, then the Python code, to implement Algorithm A on the two-row representation of a tuple.

## Pseudocode

Our function takes two arguments: the top and bottom rows of the two-row representation of this permutation.

define function factor_permutations( top row, bottom row )

create bit vector to mark columns as factored or not

initialize list of factors

initialize pointer to active location

initialize starting index

while there are still zeros in the bit vector:

initialize this factor

run until break reached:

set bit vector at active location to 1

get active location entries on top row (leader) and bottom row (follower)

get next active location (index of follower in top row)

break if next active location out of bounds

break if next active location is starting element

append follower to this factor

add starting element to end of factor

add factor to list of factors

set next start index to index of first 0 in bit vector

return factors


## Python Code

(Code for Algorithm A)

def factor_permutation(perm_top,perm_bot):
"""
Factor a permutation into its lowest terms
"""
MAX = 96
# Need a way to also mark them as used... bit vector
used_vector = [0,]*len(perm_top)

i = 0
start = perm_top[0]
used_vector[0] = 1

factors = []

# If we still have values to pick out:
while(0 in used_vector):

factor = []

while(True):
used_vector[i] = 1
follower = perm_bot[i]

i = perm_top.index(follower)
while(used_vector[i]==1):
i += 1
if(i>=MAX):
break

if(i>=MAX):
break
elif(follower==start):
break
else:
factor.append(follower)

factor.append(start)

factors.append(factor)
try:
i = used_vector.index(0)
start = perm_top[i]
except ValueError:
break

factorsize = set()
check = 0
for factor in factors:
check += len(factor)
return factors


# Preview of Part 4

We concluded with an algorithm that will be central to our task of computing the order of a Rubik's Cube move sequence.

In the next post, we'll apply our method of representing Rubik's Cubes using the two-line tuple notation, and use the factoring algorithm above, which will allow us to factor Rubik's Cube permutations into their corresponding intercalation products.

From there, we can count the size of each intercalation product, and the least common multiple of the sizes gives the order of the permutation.

# References

1. "Rubik's Cube". Charlesreid1.com wiki, Charles Reid. Edited 20 January 2017. Accessed 20 January 2017. <https://charlesreid1.com/wiki/Rubiks_Cube>

2. "Rubik's Revenge". Charlesreid1.com wiki, Charles Reid. Edited 20 January 2017. Accessed 20 January 2017. <https://charlesreid1.com/wiki/Rubiks_Revenge>

3. "Rubik's Cube/Tuple". Charlesreid1.com wiki, Charles Reid. Edited 20 January 2017. Accessed 20 January 2017. <https://charlesreid1.com/wiki/Rubiks_Cube/Tuple>

4. "Rubik's Cube/Permutations". Charlesreid1.com wiki, Charles Reid. Edited 20 January 2017. Accessed 20 January 2017. <https://charlesreid1.com/wiki/Rubiks_Cube/Permutations>

5. "Github - dwalton76/rubiks-cube-NxNxN-solver". dwalton76, Github Repository, Github Inc. Accessed 11 January 2017. <https://github.com/dwalton76/rubiks-cube-NxNxN-solver>

6. "Rubik's Cube NxNxN Solver". Git repository, git.charlesreid1.com. Charles Reid. Updated 20 January 2017. <https://charlesreid1.com:3000/charlesreid1/rubiks-cube-nnn-solver>

7. "Rubiks Cube Cycles". Git repository, git.charlesreid1.com. Charles Reid. Updated 20 January 2017. <https://charlesreid1.com:3000/charlesreid1/rubiks-cube-cycles>

# 4x4 Rubik's Cube: Part 2: Permutations

Posted in Rubiks Cube

This is Part 2 of a 4-part blog post on the mathematics of the 4x4 Rubik's Cube, its relation to algorithms, and some curious properties of Rubik's Cubes.

See Part 1 of this blog post here: Part 1: Representations

You are currently reading Part 2 of this blog post: Part 2: Permutations

See Part 3 of this blog post here: Part 3: Factoring Permutations

See Part 4 of this blog post here: Part 4: Sequence Order

# Introduction

In this post, we'll be connecting material from Part 1, about how to represent the state of the cube in a mathematical way, to the ultimate goal of exploring properties of particular move sequences.

In paticular, we'll expand on the tuple notation from Part 1, and demonstrate the two-row permutation notation of Knuth. This notation is useful for representing permutations in a way that makes it possible to create a system for describing permutations using algebra.

We will not discuss the aim of representing permutations in this way in the present post, but this will be described in Part 3.

Next, we discuss move sequences on the Rubik's Cube - these are sequences of rotations of particular faces on the Rubik's Cube. We discuss the application of the two-row permutation notation to describe moves and to describe move sequences.

Finally, we discuss rotation maps, a useful concept in the implementation of permutations via move sequences.

# Representing Permutations: Two-Row Notation

We begin by expanding on and streamlining the tuple notation introduced in Part 1 of this post so that we have a common basis for comparing two permutations. We do this using a two-row notation, where the first row denotes the "solved" or default state of the system.

In the case of the Rubik's Cube, this is equivalent to starting a cube in the solved state, then describing where each face ends up, in order to completely specify the outcome of a move or a sequence of moves.

## Two-Row Notation

We begin by considering a permutation of an $$n$$-tuple, which, in the last post, we resolved to denote

$$(2 3 4 \dots n 1)$$

Now, let us write this as two rows: the first row consists of each element of the tuple in ascending order, while the second line will the tuple corresponding to the order of the elements in this particular permutation:

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

We can think of the first row as denoting the "solved", default configuration, and the second row denoting how each item is permuted.

If we had a different permutation, we would simply change the second row:

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

## Two-Row Notation for Rubik's Cube

If we adopt the above two-row notation for the Rubik's Cube, and we utilize the face numbering and tuple indexing from Part 1, the top row consists of the integers from 1 to 96:

(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)


Now suppose we perform a rotation of the upper row U on the cube. Then we end up with the following tuple:

(13 9 5 1 14 10 6 2 15 11 7 3 16 12 8 4 33 34 35 36 21 22 23 24 25 26 27 28 29 30 31 32 49 50 51 52 37 38 39 40 41 42 43 44 45 46 47 48 65 66 67 68 53 54 55 56 57 58 59 60 61 62 63 64 17 18 19 20 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)


This tuple denotes the permutation corresponding to the move U performed on a solved cube.

# Sequences

## Review of Move/Sequence Notation

Let's quickly recap what we already know from prior posts about the properties of move sequences on the Rubik's Cube.

There are 36 possible moves on a cube, and a series of moves applied in a particular order defines a sequence. The 36 possible rotations were given in the prior blog post and cover clockwise and counterclockwise rotations of each of the six faces - either the first layer, the second layer, or both of the first two layers.

These moves are denoted with six letters (UDLRFB) for the upper, downward, left, right, front, and back face of the cube, respectively.

Moves indicated should be clockwise unless they contain an apostrophe character ', which indicates counterclockwise rotation.

A capital letter indicates a rotation of the first layer only (e.g., U indicates a clockwise rotation of the first layer of the upper face).

A lowercase letter indicates a roration of the first and second layers (e.g., r indicates a clockwise rotation of the top two layers of the right face).

A 2 before the letter indicates that the second layer should be rotated (e.g., 2F indicates a clockwise rotation of the second layer of the front face).

## How Moves Permute the Cube

This will be a little easier to understand if we consider a particular move sequence. We'll start simple and consider the move sequence U. This results, as we saw before, in:

U:
(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)
(13 9 5 1 14 10 6 2 15 11 7 3 16 12 8 4 33 34 35 36 21 22 23 24 25 26 27 28 29 30 31 32 49 50 51 52 37 38 39 40 41 42 43 44 45 46 47 48 65 66 67 68 53 54 55 56 57 58 59 60 61 62 63 64 17 18 19 20 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)


Now let's consider the move sequence U U, a double rotation of the cube's top layer:

U U:
(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)
(16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 49 50 51 52 21 22 23 24 25 26 27 28 29 30 31 32 65 66 67 68 37 38 39 40 41 42 43 44 45 46 47 48 17 18 19 20 53 54 55 56 57 58 59 60 61 62 63 64 33 34 35 36 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)


Third, we consider the move sequence U U U, equivalent to U', a counterclockwise rotation of the top layer:

U U U:
(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)
(4 8 12 16 3 7 11 15 2 6 10 14 1 5 9 13 65 66 67 68 21 22 23 24 25 26 27 28 29 30 31 32 17 18 19 20 37 38 39 40 41 42 43 44 45 46 47 48 33 34 35 36 53 54 55 56 57 58 59 60 61 62 63 64 49 50 51 52 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)


The fourth application of U, of course, will return the cube back to its solved state:

U U U:
(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)
(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)


Now if we examine the relationship between each of these tuples, we see that the faces are exchanged according to specific patterns.

These groups of four numbered faces are exchanged with one another:

( 4, 16, 13,  1)
( 8, 15,  9,  2)
(12, 14,  5,  3)
( 7, 11, 10,  6)
(65, 49, 33, 17)
(66, 50, 34, 18)
(67, 51, 35, 19)
(68, 52, 36, 20)


There are 8 total faces, composing one upper quadrant of the face being rotated.

The remaining 64 faces do not move:

(21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 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)


# Rotation Maps

While the 96-tuple representation is useful, a better computational representation of the tuple is a rotation map, which consists of 2-tuples of face index numbers that are permuted. For example, the tuple $$(4,16)$$ would indicate that the position at face 4 would become face 16 after the rotation.

As a reminder, here is the solved cube's face index layout:

             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


Thus, the rotation map representation of each move would be:

## U Rotation Map

Upon a U rotation, the face 1 will become face 13, indicated by (1,13).

U:
---------------------
[(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)]


## D Rotation Map

D:
----------------------------------------
[(81, 93),
(82, 89),
(83, 85),
(84, 81),
(85, 94),
(86, 90),
(87, 86),
(88, 82),
(89, 95),
(90, 91),
(91, 87),
(92, 83),
(93, 96),
(94, 92),
(95, 88),
(96, 84),
(29, 77),
(30, 78),
(31, 79),
(32, 80),
(45, 29),
(46, 30),
(47, 31),
(48, 32),
(61, 45),
(62, 46),
(63, 47),
(64, 48),
(77, 61),
(78, 62),
(79, 63),
(80, 64)]


## L Rotation Map

L:
----------------------------------------
[(17, 29),
(18, 25),
(19, 21),
(20, 17),
(21, 30),
(22, 26),
(23, 22),
(24, 18),
(25, 31),
(26, 27),
(27, 23),
(28, 19),
(29, 32),
(30, 28),
(31, 24),
(32, 20),
(1, 80),
(5, 76),
(9, 72),
(13, 68),
(33, 1),
(37, 5),
(41, 9),
(45, 13),
(81, 33),
(85, 37),
(89, 41),
(93, 45),
(68, 93),
(72, 89),
(76, 85),
(80, 81)]


## R Rotation Map

 R:
----------------------------------------
[(49, 61),
(50, 57),
(51, 53),
(52, 49),
(53, 62),
(54, 58),
(55, 54),
(56, 50),
(57, 63),
(58, 59),
(59, 55),
(60, 51),
(61, 64),
(62, 60),
(63, 56),
(64, 52),
(4, 36),
(8, 40),
(12, 44),
(16, 48),
(36, 84),
(40, 88),
(44, 92),
(48, 96),
(84, 77),
(88, 73),
(92, 69),
(96, 65),
(65, 16),
(69, 12),
(73, 8),
(77, 4)]


## F Rotation Map

 F:
----------------------------------------
[(33, 45),
(34, 41),
(35, 37),
(36, 33),
(37, 46),
(38, 42),
(39, 38),
(40, 34),
(41, 47),
(42, 43),
(43, 39),
(44, 35),
(45, 48),
(46, 44),
(47, 40),
(48, 36),
(13, 32),
(14, 28),
(15, 24),
(16, 20),
(20, 81),
(24, 82),
(28, 83),
(32, 84),
(81, 61),
(82, 57),
(83, 53),
(84, 49),
(49, 13),
(53, 14),
(57, 15),
(61, 16)]


## B Rotation Map

 B:
----------------------------------------
[(65, 77),
(66, 73),
(67, 69),
(68, 65),
(69, 78),
(70, 74),
(71, 70),
(72, 66),
(73, 79),
(74, 75),
(75, 71),
(76, 67),
(77, 80),
(78, 76),
(79, 72),
(80, 68),
(1, 52),
(2, 56),
(3, 60),
(4, 64),
(17, 4),
(21, 3),
(25, 2),
(29, 1),
(93, 17),
(94, 21),
(95, 25),
(96, 29),
(52, 96),
(56, 95),
(60, 94),
(64, 93)]


## How To Use Rotation Map

The rotation map enables us to represent a 4x4 Rubik's Cube as a simple tuple, and just use a Rubik's Cube object from the forked rubikscubesolver library at git.charlesreid1.com to get the rotation maps.

# Python code:
cube0 = list(range(1,96+1))
cube1 = cube0.copy()
cube_prior = cube0.copy()
r = get_cube()

for c,move in enumerate(rot.split(" ")):

# Get the rotation map
rotmap = r.rotation_map(move)

# (Print the rotation map here)

# Apply each transformation in the rotation map to the new cube
for m in rotmap:
# shift item at index m[0] to item at index m[1]
cube1[cube_prior.index(m[0])] = m[1]

cube_prior = cube1.copy()


## Face Map Code

In this section we present a portion of the code that actually generates these face maps. This functionality was not in the original Rubik's Cube solver library from Github user @dwalton76, so the library was forked and the functionality added to the forked Rubik's Cube solver library.

The actual implementation is in the rotation_map(action) method, defined for the Rubik's Cube object at the same place as the rotate(action) method. This definition is in rubikscubennnsolver/__init__.py on line 581:

link to rubikscubennnsolver/__init__.py

This method returns a list containing the tuples of index permutations (old,new) that correspond to this particular move. Call it like this:

order = 'URFDLB'
cube = RubiksCube444(solved_4x4x4, order)
cube.rotation_map('U')


# Tuples for Move Sequences

So far we have shown the tuple representation for the Rubik's Cube and how it works, and created a more convenient representation for implementing the cube on a computer and applying rotations.

Now, we can achieve the goal of this post, which is to be able to represent the state of a cube, after a certain number of rotations, in a quantitative and mathematical way.

In Part 3, we'll develop an algebra of permutations to use and understand the tuple representations we are presenting in this post.

## Applying Rotation Maps for Sequences

The concept here is simple: we use the rotation maps that we defined above to permute elements according to the formula prescribed for that particular rotation.

By applying these permutations sequentially, we can permute the 96-tuple in a way that represents the permutations created by a given sequence of moves.

For example, after applying four sequence maps corresponding to the move sequence U R U' R' we get:

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


# Preview of Part 3

As a preview of where we are going with Part 3, let's return to the permutation corresponding to U R U' R':

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


It turns out that, unlike the U move by itself, this move sequence results in groups of either three or six faces exchanging places. (In Part 3 we will cover the algorithm for finding these groups, which, crucially, relies on the work we did in this post.)

The groups of six faces that are permuted are:

[77, 65, 96, 52, 64, 4]
[16, 20, 36, 33, 49, 13]


These two sets of six faces all live on corners of the cube, so this move sequence swaps six corners.

Likewise, the groups of three faces that are permuted are:

[73, 15, 8]
[69, 14, 12]
[50, 56, 34]
[51, 60, 35]


These are all faces on double edge pieces:

• [73, 15, 8] and [51, 60, 35] are faces on right-handed double edge pieces
• [69, 14, 12] and [50, 56, 34] are faces on left-handed double edge pieces

The remaining faces do not permute:

[1, 2, 3, 5, 6, 7, 9, 10, 11, 17, 18, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 53, 54, 55, 57, 58, 59, 61, 62, 63, 66, 67, 68, 70, 71, 72, 74, 75, 76, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95]


What we will discover is that the least common multiple of these two numbers, 6 and 3, yields the number of times this move sequence needs to be applied to a solved cube (6) in order to return the cube back to its solved state.

# References

1. "Rubik's Cube". Charlesreid1.com wiki, Charles Reid. Edited 14 January 2017. Accessed 14 January 2017. <https://charlesreid1.com/wiki/Rubiks_Cube>

2. "Rubik's Revenge". Charlesreid1.com wiki, Charles Reid. Edited 14 January 2017. Accessed 14 January 2017. <https://charlesreid1.com/wiki/Rubiks_Revenge>

3. "Rubik's Cube/Tuple". Charlesreid1.com wiki, Charles Reid. Edited 14 January 2017. Accessed 14 January 2017. <https://charlesreid1.com/wiki/Rubiks_Cube/Tuple>

4. "Rubik's Cube/Permutations". Charlesreid1.com wiki, Charles Reid. Edited 14 January 2017. Accessed 14 January 2017. <https://charlesreid1.com/wiki/Rubiks_Cube/Permutations>

5. "Github - dwalton76/rubiks-cube-NxNxN-solver". dwalton76, Github Repository, Github Inc. Accessed 11 January 2017. <https://github.com/dwalton76/rubiks-cube-NxNxN-solver>

6. "Rubik's Cube NxNxN Solver". Git repository, git.charlesreid1.com. Charles Reid. Updated 14 January 2017. <https://charlesreid1.com:3000/charlesreid1/rubiks-cube-nnn-solver>

7. "Rubiks Cube Cycles". Git repository, git.charlesreid1.com. Charles Reid. Updated 14 January 2017. <https://charlesreid1.com:3000/charlesreid1/rubiks-cube-cycles>

# Appendix: Cube with Numbered Faces

             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


# 4x4 Rubik's Cube: Part 1: Representations

Posted in Rubiks Cube

This is Part 1 of a 4-part blog post on the mathematics of the 4x4 Rubik's Cube, its relation to algorithms, and some curious properties of Rubik's Cubes.

You are currently reading Part 1 of this blog post: Part 1: Representations

See Part 2 of this blog post here: Part 2: Permutations

See Part 3 of this blog post here: Part 3: Factoring Permutations

See Part 4 of this blog post here: Part 4: Sequence Order

# Introduction: Why The Rubik's Cube

In this series of four posts, we'll take a look at the 4x4 Rubik's Cube. The Rubik's Cube is an interesting puzzle that has some profound mathematical connections to group theory and combinatorics.

Group theory is a branch of mathematics that applies to any system that exhibits symmetry; combinatorics is the mathematics of counting things.

The Rubik's Cube gives us the opportunity to apply concepts in group theory and combinatorics to better understand how the cube works, and to learn how to apply these principles to real world systems.

Finally, we will wrap up by discussing some of the algorithms that are required to deal with a Rubik's Cube computationally.

In the next two posts, we'll talk more about the mathematical representation of permutations of the Rubik's Cube, and how to use this representation to understand some of the properties of move sequences when applied to the cube.

## Why The 4x4 Rubik's Cube

The 4x4 Rubik's cube, also known as the Rubik's Revenge cube, is larger than the standard 3x3 Rubik's Cube - 96 faces, instead of the ususal 36. The 4x4 cube exhibits some particularly interesting properties as a result of having an even number of squares on each edge.

# How the Rubik's Cube Works

Let's start with a discussion of cube mechanics, since this is important to coming up with an accurate mathematical model of the cube.

## The Pieces

The 4x4 Rubik's Cube consists of six faces of sixteen squares each, for a total of 96 face squares. These face squares are not completely interchangeable, however - the 4x4 cube is actually composed of three types of pieces, called "cubies".

Figure 1: Corner pieces are green.

The first type of piece is a corner piece, which contains 3 faces. Note that it is impossible for the corner pieces to change their chirality (direction of rotation). There are 8 corner pieces, each of which can be oriented in 3 different ways.

Figure 2: Double edge pieces are blue.

The second type of piece is a double edge (dedge) piece. Each edge is composed of two double edges. There are 24 total double edge pieces, which can be further classified into 12 left-handed and 12 right-handed dedge pieces.

Figure 3: Center pieces are blue.

Lastly, there are 4 center pieces in the center of each face, for a total of 24 center pieces. Note that each of the center pieces of a given color are interchangeable, unlike the double edge pieces or corners.

## Face Notation

To refer to particular faces on the cube, we use six letters to indicate different faces:

U - upper face (the top of the cube)

D - downward face (the bottom of the cube0

F - front face (the front of the cube)

B - back face (the back side of the cube)

L - left face of the cube (on the left side when facing the front F face)

R - right face of the cube

This will help refer to how we will rotate the cube.

## Color Notation

In the solved state, each cube face has one of six colors. The orientation of these colors relative to one another is always fixed; the red and orange colored faces, for example, are never adjacent. This is due to the nature of the mechanical pieces that compose the Rubik's Cube.

The standard faces for each color on a solved cube are:

• U = White
• D = Yellow
• F = Green
• B = Blue (Back-Blue)
• L = Orange
• R = Red (Red-Right)

Note that on a 3x3 cube, we can always determine the final color a face will have, because the six center pieces on each side of a 3x3 cube always remain fixed.

On a 4x4 cube, however, all four center squares can rotate and move, meaning all 24 center squares are totally interchangeable, and there is no link between the center colors on a 4x4 cube and the final color that will be on that face when the cube is solved.

## Move Notation

Using the face notation explained above, we can denote multiple types of moves on the 4x4 Rubik's Cube.

We have 36 total moves that we can make on the 4x4 Rubik's Cube, which can be grouped by the dozen:

L l r R
U u d D
B b f F

L' l' r' R'
U' u' d' D'
B' b' f' F'

2L 2L' 2R 2R'
2U 2U' 2D 2D'
2B 2B' 2F 2F'


Let's go through the details of the notation.

### Regular Face Rotations

The regular face turns are denoted with capital letters: L R U D B F refer to a single clockwise rotation of the respective face. Here, "clockwise" means the direction that is clockwise when facing the given face head-on.

### Reverse Face Rotations

The ' apostrophe following moves, as in L' R' U' D' B' F', indicates that the move shoud be a counter-clockwise rotation of the given face, instead of clockwise.

### Double Face Rotations

Rotations that are indicated using a lowercase letter refer to two-layer rotations: l r u d b f.

Figure 4: Cube state after move u.

That is, the lowercase u refers to the clockwise rotation of the top two layers of the cube; the lowercase r refers to the clockwise rotation of the rightmost two layers of the cube; and so on.

The apostrophe also serves to indicate a counter-clockwise rotation: 'l r' u' d' b' f' indicate counter clockwise rotations of the two left, two right, two upper, two bottom, two back, and two front layers, respectively.

We have covered the first 24 moves - clockwise and counter-clockwise rotations of single and double layers.

### Second Layer Face Rotations

Figure 5: Cube state after move 2U.

The 2 notation indicates a rotation of the second layer only. For example, 2U refers to the clockwise rotation of the second layer from the top. This is equivalent to the move sequence u U'.

Likewise, the apostrophe indicates a counterclockwise rotation.

# Computer Representation of a Rubik's Cube

The computer representation we are using is the rubiks-cube-NxNxN-solver library by Github user @dwalton.

We have modified this library to provide additional functionality needed in the project; the fork used in this project is available at git.charlesreid1.com: rubiks-cube-nnn-solver

Using this library, here's how we create a 4x4 Rubik's Revenge cube:

In [1]: from rubikscubennnsolver.RubiksCube444 import RubiksCube444, solved_4x4x4

In [2]: order = 'URFDLB'

In [3]: cube = RubiksCube444(solved_4x4x4, order)

In [4]: cube.print_cube()
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


## Operations and Functionality

Some important functionality:

• Obtaining each side
• Applying rotation
• Applying sequence of rotations
• Each side
• Side face numberings, centers, edges

To obtain each side, use the sides attribute:

In [8]: print(cube.sides)
OrderedDict([('U', <rubikscubennnsolver.RubiksSide.Side object at 0x11172d358>),
('L', <rubikscubennnsolver.RubiksSide.Side object at 0x11172d240>),
('F', <rubikscubennnsolver.RubiksSide.Side object at 0x11172d5c0>),
('R', <rubikscubennnsolver.RubiksSide.Side object at 0x11172d5f8>),
('B', <rubikscubennnsolver.RubiksSide.Side object at 0x11172d518>),
('D', <rubikscubennnsolver.RubiksSide.Side object at 0x11172d390>)])


Each Side object has a long list of methods, including methods to obtain the index numbers of corner, edge, or center faces on a particular side.

To apply a rotation of a single face, use the rotate() method and pass the name of the face:

In [10]: cube.rotate("U")

In [11]: cube.print_cube()
U U U U
U U U U
U U U U
U U U U

F F F F  R R R R  B B B B  L L L L
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


Unfortunately, the rotate method does not take sequences of moves, but this is easily resolved:

In [12]: cube = RubiksCube444(solved_4x4x4, order)

In [13]: sequence = "U L U' L'"

In [14]: for move in sequence.split():
...:     cube.rotate(move)
...:

In [15]: cube.print_cube()
L U U U
U U U U
U U U U
U B B L

D F F F  R L L F  U R R R  B B B B
L L L L  F F F F  R R R R  B B B U
L L L L  F F F F  R R R R  B B B U
L L L L  F F F F  R R R R  B B B U

D D D D
D D D D
D D D D
B D D D


## Face Numbering

Here is the numerical representation of the faces, which we will make extensive use of:

In [6]: cube.print_cube_layout()
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


# Tuple Representation

We have a goal of finding a way of representing the state of the 4x4 Rubik's Revenge using a tuple, which is a mathematical object that will enable us to investigate properties of sequences, moves, and rotations.

It is important to note that the mechanics of the cube restrict some of the 96 total faces to only occur in particular configurations. By using a tuple of 96 integers, we are overspecifying the state of the cube, and we would be able to do much better if our goal were a minimal representation of the Rubik's Cube state.

However, our goal is not a minimal representation of the cube, but a unique representation of the cube. As we will see in a later post, the schema we use does not actually matter, so long as we can represent each unique state of the cube using a sequence of integers of arbitrary length.

## Tuple Representation Requirements

The 4x4 cube, in the solved state, has a few characteristics that can be used to indicate a particular permutation or configuration:

• Face indciators UDFBLR
• Colors WYGBRO
• Integers 1-96 to number each face

Here is how the faces representation looks:

In [17]: cube.print_cube()
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


The equivalent color representation is:

         W W W W
W W W W
W W W W
W W W W

O O O O  G G G G  R R R R  B B B B
O O O O  G G G G  R R R R  B B B B
O O O O  G G G G  R R R R  B B B B
O O O O  G G G G  R R R R  B B B B

Y Y Y Y
Y Y Y Y
Y Y Y Y
Y Y Y Y


However, the tuple representation cannot use colors to represent the state of the cube. This is because a tuple representation using "R" to represent each red face would give us no way of distinguishing between the (non-interchangeable) red faces on the cube. For example, if the red-green double edge piece were replaced with a red-blue double edge piece, oriented with the red face at the same location, the n-tuple needs to reflect that this face has a different value than it did the prior move.

For this reason, we must use an integer to index each distinct face:

             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


We can rearrange this into a 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)


If we apply a rotation, for example U R, we will end up with a different cube:

             13 09 05 01
14 10 06 02
15 11 07 03
48 44 40 36

33 34 35 84  61 57 53 49  16 66 67 68  17 18 19 20
21 22 23 24  37 38 39 88  62 58 54 50  12 70 71 72
25 26 27 28  41 42 43 92  63 59 55 51  08 74 75 76
29 30 31 32  45 46 47 96  64 60 56 52  04 78 79 80

81 82 83 77
85 86 87 73
89 90 91 69
93 94 95 65


This particular sequence of moves results in a cube state uniquely represented by the following 96-tuple:

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


## Tuple Representation

Now, we have managed to find a unique representation for any given cube state by labeling each individual face 1-96.

But we aren't quite done yet. It turns out that our statement, that our representation should treat each face as unique, is not strictly true for all 96 faces.

The square pieces are completely interchangeable, due to the fact that they are not connected to any other faces (and therefore have no orientation or way of differentiating them from one another).

If we are doing anything that involves counting configurations, it is important to account for this fact, by treating the following groups of face indices as interchangeable:

(6, 7, 10, 11)
(22, 23, 26, 27)
(38, 39, 42, 43)
(54, 55, 58, 59)
(70, 71, 74, 75)
(86, 87, 90, 91)


In Part 2 and Part 3 of this series, we will encounter these concepts again, and it will become more clear what these caveats and notes mean through example.

Following is a preview of Part 2 of this 3-part blog post.

# Preview of Part 2

In Part 2 of this series, we will utilize the n-tuple representation of the 4x4 Rubik's Cube in order to write permutations of the cube corresponding to specific states, and turn a sequence of moves on the cube into permutations.

We will also create a map for each type of move, telling us where each face index will end up.

In Part 3 we will use these to predict properties of rotations applied to the 4x4 Rubik's Cube.

# References

1. "Rubik's Cube". Charlesreid1.com wiki, Charles Reid. Edited 11 January 2017. Accessed 11 January 2017. <https://charlesreid1.com/wiki/Rubiks_Cube>

2. "Rubik's Revenge". Charlesreid1.com wiki, Charles Reid. Edited 11 January 2017. Accessed 11 January 2017. <https://charlesreid1.com/wiki/Rubiks_Revenge>

3. "Rubik's Cube/Tuple". Charlesreid1.com wiki, Charles Reid. Edited 11 January 2017. Accessed 11 January 2017. <https://charlesreid1.com/wiki/Rubiks_Cube/Tuple>

4. "Rubik's Cube/Permutations". Charlesreid1.com wiki, Charles Reid. Edited 11 January 2017. Accessed 11 January 2017. <https://charlesreid1.com/wiki/Rubiks_Cube/Permutations>

5. "Github - dwalton76/rubiks-cube-NxNxN-solver". dwalton76, Github Repository, Github Inc. Accessed 11 January 2017. <https://github.com/dwalton76/rubiks-cube-NxNxN-solver>

6. "Rubik's Cube NxNxN Solver". Git repository, git.charlesreid1.com. Charles Reid. Updated 11 January 2017. <https://charlesreid1.com:3000/charlesreid1/rubiks-cube-nnn-solver>

7. "Rubiks Cube Cycles". Git repository, git.charlesreid1.com. Charles Reid. Updated 11 January 2017. <https://charlesreid1.com:3000/charlesreid1/rubiks-cube-cycles>