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
Table of Contents
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
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:
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:
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
-
"Rubik's Cube". Charlesreid1.com wiki, Charles Reid. Edited 14 January 2017. Accessed 14 January 2017. <https://charlesreid1.com/wiki/Rubiks_Cube>
-
"Rubik's Revenge". Charlesreid1.com wiki, Charles Reid. Edited 14 January 2017. Accessed 14 January 2017. <https://charlesreid1.com/wiki/Rubiks_Revenge>
-
"Rubik's Cube/Tuple". Charlesreid1.com wiki, Charles Reid. Edited 14 January 2017. Accessed 14 January 2017. <https://charlesreid1.com/wiki/Rubiks_Cube/Tuple>
-
"Rubik's Cube/Permutations". Charlesreid1.com wiki, Charles Reid. Edited 14 January 2017. Accessed 14 January 2017. <https://charlesreid1.com/wiki/Rubiks_Cube/Permutations>
-
"Github - dwalton76/rubiks-cube-NxNxN-solver". dwalton76, Github Repository, Github Inc. Accessed 11 January 2017. <https://github.com/dwalton76/rubiks-cube-NxNxN-solver>
-
"Rubik's Cube NxNxN Solver". Git repository, git.charlesreid1.com. Charles Reid. Updated 14 January 2017. <https://git.charlesreid1.com/charlesreid1/rubiks-cube-nnn-solver>
-
"Rubiks Cube Cycles". Git repository, git.charlesreid1.com. Charles Reid. Updated 14 January 2017. <https://git.charlesreid1.com/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