Rubiks Cube/Tuple

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 (3x3 cube): 26 total cubies (mechanical pieces)

• 8 corner cubies
• 12 edge cubies
• 6 center cubies (fixed)

Rubik's Revenge (4x4 cube): 56 total cubies (mechanical pieces)

• 8 corner cubies
• 24 double-edge (dedge) wing cubies (12 left wing, 12 right wing)
• 24 center cubies

Professors Cube (5x5 cube): 25*2 + 16*3 = 98 total cubies (mechanical pieces)

• 8 corner cubies
• 24 triple-edge (tredge) wing cubies (12 left wing, 12 right wing)
• 12 triple-edge (tredge) center cubies
• 6 center (of face) cubies (fixed)
• 48 face cubies (mobile)

However, it is important to note that we are not trying to find the minimal representation of the cube, we are simply trying to find a unique representation of the cube. Listing the state of every single face requires more information - there are more faces than pieces, because corners have 3 faces and double edge pieces have 2 faces - but it is much simpler to accomplish, by thinking about "unfolding"the cube into a map of colored squares.

• The 3x3 Rubik's Cube has 9 squares on each face, and 6 faces, for a total of 54 colored squares.
• The 4x4 Rubik's Revenge has 16 squares on each face, and 6 faces, for 96 total colored squares.
• The 5x5 Professor's Cube has 25 squares on each face, and 6 faces, for 150 total colored 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 54-uple, or the state of any 4x4 Rubik's Revenge cube using a 96-uple, or the state of any 5x5 Professor's cube using a 150-uple.

Why A Tuple Representation

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

Applying a sequence of moves, such as

U R U' R'

(that is, turning the upper face clockwise, right face clockwise, upper face counter clockwise, and right face counter clockwise), to a solved cube repeatedly will eventually result in the cube returning to its original, solved state. The sequence above will return a solved 4x4 cube back to solved state after the sequence is applied 6 times.

Other sequences take much longer; the sequence

U R 

will take 105 applications to return a solved 4x4 cube back to solved state.

It turns out that the tuple representation of a cube helps simplify and streamline the representation of these move sequences. If we write the state of a cube as a tuple, we can see which squares are exchanged after a sequence of moves. For example, after applying the sequence

U R U' R'

to a solved 4x4 cube, it exchanges 10 pieces total, exchanging different groups of pieces in different orders. On the other hand, after applying the sequence

U R

to a solved 4x4 cube, it exchanges 20 pieces total, exchanging different groups of pieces.

It turns out that the placement and order in which those different groups of pieces are exchanged determines the number of times a sequence must be applied to a solved cube to reach the solved state again. This is referred to as the order of the sequence.

This intuitively makes sense: if you apply a sequence that cycles through 3 pieces, then every 3 applications of the sequence the pieces will return to their original positions. If you have another sequence that cycles through 4 pieces, then every 4 applications of the sequence the pieces will return to their original positions.

But now, if we mix these two sequences together, then the order is LCM(3,4), where LCM is the least common multiple. In this case, we need to apply the sequence 12 times to return to the original state.

Supposing we had a cycle of length 105, which factors into 105 = 3*5*7. Then this could be caused by two interlocking sequences with orders 7 and 15.

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, find the order of each permuation, and implement algorithms for everything.

Code

Code implementation: https://github.com/charlesreid1/rubiks-cycles

Specifically, the tuple representation and permutation factoring algorithms are here: https://github.com/charlesreid1/rubiks-cycles/blob/master/tup.py

More on Permutations

This article covers the tuple representation of the Rubik's Cube, with the ultimate goal of using it to describe permutations and sequences of moves on the cube.

To skip straight to the notes on permutations, see Rubiks Cube/Permutations

4x4 Rubiks Cube Representation

Numbering System for 4x4

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]

4x4 Moves Mapped to 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.

Permutations and Their Properties

Now that we have a tuple representation of the cube, we can start to use it to characterize sequences of moves, the permutations they lead to, and their properties.

See Rubiks Cube/Permutations