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.

Motivation

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.

Cycle Structure & Order

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.

Connection to Group Theory / AOCP

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.

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

3x3 Rubiks Cube Representation

Numbering System for 3x3 Cube

Start with a numbering system for the 3x3 cube. The nxnxn rubiks cube solver library (https://github.com/dwalton76/rubiks-cube-NxNxN-solver) implements the following numbering system, where each face is assigned a block of 9 consecutive integers (3×3 = 9 squares per face):

             01 02 03
             04 05 06
             07 08 09

10 11 12    19 20 21    28 29 30    37 38 39
13 14 15    22 23 24    31 32 33    40 41 42
16 17 18    25 26 27    34 35 36    43 44 45

             46 47 48
             49 50 51
             52 53 54

corresponding to the following cube state:

         U U U
         U U U
         U U U

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

         D D D
         D D D
         D D D

The faces are assigned in the order Up, Left, Front, Right, Back, Down:

• U (Up): positions 1–9
• L (Left): positions 10–18
• F (Front): positions 19–27
• R (Right): positions 28–36
• B (Back): positions 37–45
• D (Down): positions 46–54

Now we can write the solved 3x3 cube as the following 54-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]

Each integer represents a colored square on the cube. In the solved state, each face consists of 9 identical squares (all U, all L, etc.), but the numbers themselves uniquely identify each square's position.

Mapping Moves to Permutations for 3x3

Each move of a face — U, D, R, L, F, B — can now be thought of as a permutation of these 54 integers.

Using the numbering system above, the rotation of each face produces a set of swaps. Each swap is recorded as an (old_index, new_index) pair meaning "the value that was at position new_index moves to position old_index."

U Move

For example, here is the U move (clockwise quarter-turn of the Up face):

Rotation of the U face itself: The 3×3 grid on the U face rotates clockwise:

1 2 3      7 4 1
4 5 6  →   8 5 2
7 8 9      9 6 3

Rotation of the surrounding top rows: The top row of each adjacent side cycles L ← F ← R ← B ← L:

[(1, 7), (2, 4), (3, 1), (4, 8), (6, 2), (7, 9), (8, 6), (9, 3),
 (10, 19), (11, 20), (12, 21),
 (19, 28), (20, 29), (21, 30),
 (28, 37), (29, 38), (30, 39),
 (37, 10), (38, 11), (39, 12)]

This is a total of 20 swaps. The center square of the U face (position 5) does not move. The remaining 34 squares (positions 13–18, 22–27, 31–36, 40–54) are unaffected by the U move.

R Move

The R move (clockwise quarter-turn of the Right face) produces the following permutation:

Rotation of the R face itself:

28 29 30      34 31 28
31 32 33  →   35 32 29
34 35 36      36 33 30

Rotation of the surrounding right columns: U right column → F right column → D right column → B left column (reversed) → U right column (reversed):

[(28, 34), (29, 31), (30, 28), (31, 35), (33, 29), (34, 36), (35, 33), (36, 30),
 (3, 21), (6, 24), (9, 27),
 (21, 48), (24, 51), (27, 54),
 (48, 43), (51, 40), (54, 37),
 (37, 9), (40, 6), (43, 3)]

Again, 20 swaps total. The center square of the R face (position 32) does not move. Squares on the L face and the middle rows/columns of the other faces are unaffected.

Other Moves

The remaining face moves (D, L, F, B) follow the same pattern. Each single-face quarter-turn on a 3x3 cube produces exactly 20 swaps (8 on the rotated face itself, plus 12 across the four adjacent faces). Inverse moves (U', R', etc.) simply reverse the direction of each swap.

Move Sequences

A sequence of moves, such as U R U' R', is simply the composition of the individual move permutations, applied in order. Once expressed as a permutation of the 54 integers, the sequence can be analyzed to determine its cycle structure and order.

3x3 Permutations and Properties

Now that we have a 54-tuple representation of the 3x3 cube and can express moves as permutations, we can analyze sequences of moves using the permutation factoring techniques described in Rubiks Cube/Permutations.

By factoring a move-sequence permutation into its independent cycles (using Algorithm A from Knuth's The Art of Computer Programming), we can determine the order of the sequence — the number of times it must be applied to return a solved cube to the solved state.

For example, the single move U produces cycles all of length 4, so its order is 4. The sequence U R produces cycles of various lengths; factoring the permutation yields the order as the least common multiple of those cycle lengths.

One important difference between the 3x3 and the 4x4 is that the 3x3 has fixed center pieces. The six center squares (positions 5, 14, 23, 32, 41, 50) never move under any face rotation, so they always appear as 1-cycles (fixed points) in any permutation. This simplifies the analysis compared to the 4x4, where center pieces are mobile and interchangeable.

For a full treatment of permutation factoring, cycle extraction, and order computation, see Rubiks Cube/Permutations.

3x3 Cube Code

The same codebase used for the 4x4 cube also handles the 3x3 case. The NxNxN solver library (https://github.com/dwalton76/rubiks-cube-NxNxN-solver) treats the 3x3 as an N=3 instance of the general N×N×N cube.

The tuple representation and permutation factoring algorithms are implemented in the rubiks-cycles repository:

• Main repository: https://github.com/charlesreid1/rubiks-cycles
• Tuple representation and factoring: https://github.com/charlesreid1/rubiks-cycles/blob/master/tup.py

The 3x3 cube uses self.size = 3 and self.squares_per_side = 9, producing a 54-tuple. The rotation_map() method (see the Code section under 4x4) works identically for any N, including N=3.

Mapping Moves to Permutations for 3x3

Each move of a face — U, D, R, L, F, B — can now be thought of as a permutation of these 54 integers.

Using the numbering system above, the rotation of each face produces a set of swaps. Each swap is recorded as an (old_index, new_index) pair meaning "the value that was at position new_index moves to position old_index."

3x3 Permutations and Properties

Now that we have a 54-tuple representation of the 3x3 cube and can express moves as permutations, we can analyze sequences of moves using the permutation factoring techniques described in Rubiks Cube/Permutations.

By factoring a move-sequence permutation into its independent cycles (using Algorithm A from Knuth's The Art of Computer Programming), we can determine the order of the sequence — the number of times it must be applied to return a solved cube to the solved state.

For example, the single move U produces cycles all of length 4, so its order is 4. The sequence U R produces cycles of various lengths; factoring the permutation yields the order as the least common multiple of those cycle lengths.

One important difference between the 3x3 and the 4x4 is that the 3x3 has fixed center pieces. The six center squares (positions 5, 14, 23, 32, 41, 50) never move under any face rotation, so they always appear as 1-cycles (fixed points) in any permutation. This simplifies the analysis compared to the 4x4, where center pieces are mobile and interchangeable.

For a full treatment of permutation factoring, cycle extraction, and order computation, see Rubiks Cube/Permutations.

3x3 Cube Code

The same codebase used for the 4x4 cube also handles the 3x3 case. The NxNxN solver library (https://github.com/dwalton76/rubiks-cube-NxNxN-solver) treats the 3x3 as an N=3 instance of the general N×N×N cube.

The tuple representation and permutation factoring algorithms are implemented in the rubiks-cycles repository:

• Main repository: https://github.com/charlesreid1/rubiks-cycles
• Tuple representation and factoring: https://github.com/charlesreid1/rubiks-cycles/blob/master/tup.py

The 3x3 cube uses self.size = 3 and self.squares_per_side = 9, producing a 54-tuple. The rotation_map() method (see the Code section under 4x4) works identically for any N, including N=3.

Other Moves

The remaining face moves (D, L, F, B) follow the same pattern. Each single-face quarter-turn on a 3x3 cube produces exactly 20 swaps (8 on the rotated face itself, plus 12 across the four adjacent faces). Inverse moves (U', R', etc.) simply reverse the direction of each swap.

Move Sequences

A sequence of moves, such as U R U' R', is simply the composition of the individual move permutations, applied in order. Once expressed as a permutation of the 54 integers, the sequence can be analyzed to determine its cycle structure and order.

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

5x5 Rubiks Cube Representation

Numbering System for 5x5

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, where each face is assigned a block of 25 consecutive integers (5×5 = 25 squares per face):

             001 002 003 004 005
             006 007 008 009 010
             011 012 013 014 015
             016 017 018 019 020
             021 022 023 024 025

026 027 028 029 030  051 052 053 054 055  076 077 078 079 080  101 102 103 104 105
031 032 033 034 035  056 057 058 059 060  081 082 083 084 085  106 107 108 109 110
036 037 038 039 040  061 062 063 064 065  086 087 088 089 090  111 112 113 114 115
041 042 043 044 045  066 067 068 069 070  091 092 093 094 095  116 117 118 119 120
046 047 048 049 050  071 072 073 074 075  096 097 098 099 100  121 122 123 124 125

             126 127 128 129 130
             131 132 133 134 135
             136 137 138 139 140
             141 142 143 144 145
             146 147 148 149 150

corresponding to the following cube state:

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

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

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

The faces are assigned in the order Up, Left, Front, Right, Back, Down:

• U (Up): positions 1–25
• L (Left): positions 26–50
• F (Front): positions 51–75
• R (Right): positions 76–100
• B (Back): positions 101–125
• D (Down): positions 126–150

Now we can write the solved cube as the following 150-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, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150]

5x5 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 150 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, 21),
 (2, 16),
 (3, 11),
 (4, 6),
 (5, 1),
 (6, 22),
 (7, 17),
 (8, 12),
 (9, 7),
 (10, 2),
 (11, 23),
 (12, 18),
 (13, 13),
 (14, 8),
 (15, 3),
 (16, 24),
 (17, 19),
 (18, 14),
 (19, 9),
 (20, 4),
 (21, 25),
 (22, 20),
 (23, 15),
 (24, 10),
 (25, 5),
 (26, 51),
 (27, 52),
 (28, 53),
 (29, 54),
 (30, 55),
 (51, 76),
 (52, 77),
 (53, 78),
 (54, 79),
 (55, 80),
 (76, 101),
 (77, 102),
 (78, 103),
 (79, 104),
 (80, 105),
 (101, 26),
 (102, 27),
 (103, 28),
 (104, 29),
 (105, 30)]

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 150 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