Symmetries and Antisymmetries of Rubik's cube positions

[Herbert Kociemba]

I just finished the classification of all Rubik's cube concerning their symmetry/antisymmetry. If you are interested, have a look at
http://cubezzz.dyndns.org/drupal/?q=node/view/526

 

[Christopher Mowla]

From doing my single commutator project, I have become very interested in symmetry reductions and other reductions to manage to only have 967 corner cases to solve with a single commutator instead of (8!/2)(3^7) (which I have completed) and currently 3407 cases for middle edges (but I am currently trying to prove yet another reduction that will handle take out an additional 1316 cases, and I hope to find more reductions after that) instead of (12!/2)(2^11) to test. (I'm coding software in Mathematica to help me make these calculations and generate cases so that I'm positive that I am not making any mistakes).

I have heard off and on about symmetries of the cube, but I have minimal knowledge of group theory and don't seem to posses the aptitude to grasp the abstract material at hand without some illustrative examples. From my commutator project, I believe I am actually practicing group theory without any prior knowledge, but it still bothers me that I have to teach myself these concepts from scratch as I need them instead of having the aptitude to benefit from the works of others before my time. Jaaps pages are not helpful for me either (neither is Wikipedia).

Would you be kind enough to give cube states (in maneuver form) which are symmetrical to each other to express to people like me exactly what you're doing in a more concrete form?

 

[Herbert Kociemba]

Would you be kind enough to give cube states (in maneuver form) which are symmetrical to each other to express to people like me exactly what you're doing in a more concrete form?

First of all it is important not to confuse a symmetry of a cube in general with the symmetry of a specific Rubik's cube.
A cube in general has 24 ways of rotating it into different positions. The mirror images of these positions contribute another 24 cases. So the group M of cube symmetries has 48 elements, each one describing how to rotate/mirror a cube into the new position.
If you have a specific Rubik's cube x, each of these 48 elements can act on x. This is called the group action of M. Let's take the cube x for example be the cube with the generator U R. The 24 rotations of M acting on this cube give (including the do nothing rotation) the new cubes with the generators:

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

Try it. You can always fix two points of the U R cube with two fingers and rotate it into a new position for each of the generators given above.

For the mirror images I personally prefer the point reflection at the center of the cube. The point reflection sends U to D', U2 to D2 and U' to D. It sends R to L', R2 to L2 and R' to L......
Doing this for the 24 maneuvers given above we get:

D' L', U' B', U' F', B' R', R' U', F' R'........

All these 48 cubes look different, but essentially they are the same. The action of M on x generated 48 different cubes, these 48 cubes are called the orbit of x under the group action.

Not lets take another cube y = U.

If you apply the 48 elements of M to this cube, you only get

U, R, F, D, L, B, D', L', B', U', R', F'.

The orbit of y has only 12 different cubes. This is, because y itself has some symmetry. If you rotate y about the UD-axis, nothing will happen. There are 4 elements of M, which keep y fixed: UD-Axis do nothing rotation, UD-Axis 90 deg rotation, UD-Axis180 deg rotation and UD-Axis 270 deg rotation.
We say the cube y has the symmetry of the group C4, or the group C4 is the stabilizer group of the cube y.

There are are essentially 33 different subgroups of M and therefore 33 different kinds of symmetry a specific cube can have. You can find them on my homepage.

 

[d2alphame]

This is the best explanation I have ever seen. Thanks Herbert.

 

[academicmaslow]

I just finished the classification of all Rubik's cube concerning their symmetry/antisymmetry. If you are interested, have a look at
http://cubezzz.dyndns.org/drupal/?q=node/view/526

Dear Herbert,
Your classification of symmetric patterns is truly foundational—thank you for your work. It greatly enhances the understanding of the mathematical nature of the cube.
As a cube mosaic creator, I’ve been exploring cube symmetry through dual-sided color patterns. In particular, I’ve been developing a system of Mirror Dual-Sided Inverse (MDSI) color patterns, with some input from your colleague Tomas Rocicki, who assisted me in optimizing algorithms for two-color MDSI mosaics. I’ve started a thread on this topic to share ideas and examples.
I’d like to ask how might MDSI patterns relate to your classification of symmetric cube patterns? More broadly, do you think MDSI patterns could be meaningfully considered a form of cube symmetry?
I would greatly appreciate your insights.

 

[abunickabhi]

Dear Herbert,
Your classification of symmetric patterns is truly foundational—thank you for your work. It greatly enhances the understanding of the mathematical nature of the cube.
As a cube mosaic creator, I’ve been exploring cube symmetry through dual-sided color patterns. In particular, I’ve been developing a system of Mirror Dual-Sided Inverse (MDSI) color patterns, with some input from your colleague Tomas Rocicki, who assisted me in optimizing algorithms for two-color MDSI mosaics. I’ve started a thread on this topic to share ideas and examples.
I’d like to ask how might MDSI patterns relate to your classification of symmetric cube patterns? More broadly, do you think MDSI patterns could be meaningfully considered a form of cube symmetry?
I would greatly appreciate your insights.

Thanks for the 10 year bump.

It is good to revisit and look at the nice classification created by Herbert.

 

[Herbert Kociemba]

Dear Herbert,
Your classification of symmetric patterns is truly foundational—thank you for your work. It greatly enhances the understanding of the mathematical nature of the cube.
As a cube mosaic creator, I’ve been exploring cube symmetry through dual-sided color patterns. In particular, I’ve been developing a system of Mirror Dual-Sided Inverse (MDSI) color patterns, with some input from your colleague Tomas Rocicki, who assisted me in optimizing algorithms for two-color MDSI mosaics. I’ve started a thread on this topic to share ideas and examples.
I’d like to ask how might MDSI patterns relate to your classification of symmetric cube patterns? More broadly, do you think MDSI patterns could be meaningfully considered a form of cube symmetry?
I would greatly appreciate your insights.

Certainly you can say that this a sort of symmetry because reflection at FB-plane + color swap does not change the F and B side of the cube. But it has not much in common with the symmetry classification of these 33 different types which refer primarily to the permutations and twists/flips of corner and edges and not so much on the colors of the stickers.
But let us take a look which of the 33 symmetry types https://kociemba.org/symmetric2.htm make the same color swap F<->B R<->L and U<->D too. It is all symmetry subgroups which include the point reflection in the center (violet dot in the center of the pictogram), this is
C_i
C_2h (a)
C_2h (b)
D_2h(face))
D_2h(edge)
C_4h
D_4h
S_6
D_3d
T_h
O_h

The difference to your MDSI patterns is that the mirror image on the opposite side is upside down and this occurs simultanously on all 3 pairs of opposite faces, so we could call it a Point Mirror Six-Sided Inverse (PMSSI) color pattern
You can click on each of the symmetry groups to see some examples.
Btw, you can create such cubes with the symmetry tab of Cube Explorer where you also can choose how many colors are allowed on each face.

 

[academicmaslow]

Certainly you can say that this a sort of symmetry because reflection at FB-plane + color swap does not change the F and B side of the cube. But it has not much in common with the symmetry classification of these 33 different types which refer primarily to the permutations and twists/flips of corner and edges and not so much on the colors of the stickers.
But let us take a look which of the 33 symmetry types https://kociemba.org/symmetric2.htm make the same color swap F<->B R<->L and U<->D too. It is all symmetry subgroups which include the point reflection in the center (violet dot in the center of the pictogram), this is
C_i
C_2h (a)
C_2h (b)
D_2h(face))
D_2h(edge)
C_4h
D_4h
S_6
D_3d
T_h
O_h

The difference to your MDSI patterns is that the mirror image on the opposite side is upside down and this occurs simultanously on all 3 pairs of opposite faces, so we could call it a Point Mirror Six-Sided Inverse (PMSSI) color pattern
You can click on each of the symmetry groups to see some examples.
Btw, you can create such cubes with the symmetry tab of Cube Explorer where you also can choose how many colors are allowed on each face.

Thank you Herbert! Very interesting points — both your comment and the concept of the Point Mirror Six-Sided Inverse (PMSSI) pattern!
I’ve just tried the symmetry editor, and it seems it can indeed work for my MDSI patterns — I just need to append an F2 or B2 move to the final algorithm.
As I expected it takes a lot of time (and machine resiources) to generate the algorithms: for a random three-color pattern it took 3 minutes 13 seconds, and for a six-color pattern — nearly 20 minutes.
When I began developing a method for solving MDSI patterns, I anticipated that algorithm generation time could be a challenge for creating cube mosaics (which is my goal). Therefore, I devised a four-stage, layer-by-layer construction method that can generate any of the 10,077,696 possible dual-sided patterns using fewer than 500 algorithms. This method is fully executable by hand, without any programming. However, I also wrote a Python script that can instantly generate any of these algorithms automatically, leveraging your kociemba Python package at the final stage.
I plan to present this approach at the Bridges Conference on Mathematics and Art in Eindhoven this July.
A few days ago (on May, 5), I sent a more detailed description of my method to your public email address. I would be very grateful if you had time to review it and share any feedback you might have!

 

[Herbert Kociemba]

As I expected it takes a lot of time (and machine resiources) to generate the algorithms: for a random three-color pattern it took 3 minutes 13 seconds, and for a six-color pattern — nearly 20 minutes

I don’t understand what you mean. Cube Explorer finds a <=20 move solution for a given position usually in fractions of a second.

 

[academicmaslow]

I probably did something wrong when configuring the symmetry editor. But I tried again and realised that I had selected "Optimal", which sometimes takes more time for generating algorithms. Without "Optimal", algorithms are longer, but the search completes in a fraction of a second - yes. Thank you, it's clear now.

 

[Neel Khandelwal]

Hey Mr. Kociemba!
I have no knowledge about the group theory, but I was very intrigued by your algorithm that I had to implement it.
My question only revolves around symmetries, as that is one thing I do not at all understand.

My cube is a object with
cornerCubieOrientation (URF, UFL, ULB, UBR, DFR, DLF, DBL, DRB) array
edgeCubeOrientation (UF, UL, UB, UR, DF, DL, DB, DR, FR, FL, BL, BR) array
udSliceLocation array (which does not account for order or permutation, but 0 if it does not exist and 1 if it exists at the location).

Example:
Given a cube with:
corners: 1 0 1 2 0 0 0 2
edges: 0 1 1 1 0 1 0 0 1 1 0 0
udSlc: 0 0 0 0 1 0 0 0 0 1 1 1

What would be the symmetries of this. Because that would help me understand what they are all about and the logic behind it!

A reply would be so greatfull!!!

 

[Herbert Kociemba]

Hey Mr. Kociemba!
I have no knowledge about the group theory, but I was very intrigued by your algorithm that I had to implement it.
My question only revolves around symmetries, as that is one thing I do not at all understand.

My cube is a object with
cornerCubieOrientation (URF, UFL, ULB, UBR, DFR, DLF, DBL, DRB) array
edgeCubeOrientation (UF, UL, UB, UR, DF, DL, DB, DR, FR, FL, BL, BR) array
udSliceLocation array (which does not account for order or permutation, but 0 if it does not exist and 1 if it exists at the location).

Example:
Given a cube with:
corners: 1 0 1 2 0 0 0 2
edges: 0 1 1 1 0 1 0 0 1 1 0 0
udSlc: 0 0 0 0 1 0 0 0 0 1 1 1

What would be the symmetries of this. Because that would help me understand what they are all about and the logic behind it!

A reply would be so greatfull!!!

 

[Herbert Kociemba]

It would be much easier for me and less error-prone if you enter the cube you have in mind into Cube Explorer with the facelet editor and supply me with a generator.

 

[Neel Khandelwal]

It would be much easier for me and less error-prone if you enter the cube you have in mind into Cube Explorer with the facelet editor and supply me with a generator.

Okay. Let me try with another example then.
If its a cube with the generator:
R B2 D2 B2 L2 U2 F2 R' F2 L' F2 U' F L B' R U F R F2 D'

Then given that, you mentioned on your website, I do not need to fall back to the facelet level; how would I go about implementing the symmetries using the cubie level descriptions. Because my cube object is just made with corner and edge orientation arrays. So how would a symmetry (rotation) alter the orientation arrays, giving rise to a new cube structure, but which is symmetrically equivalent to the original cube.

 

[Herbert Kociemba]

This cube has no symmetry. Indeed Cube Explorer checks symmetries on the cubie level. Cube moves like R, D2 etc are handled in the same way as the 48 possible cube rotations and reflections. All are represented in the same format as a cube state on the cubie lev, though for cube reflections things are a bit more complicated since reflected corners are described by orientations 3, 4 and 5. You can multiply those states/reflections/rotations. Now a cube C has a symmetry S if applying S*C*S^-1 =C and this is what Cube explorer or the Python implementations checks. S^-1 is the inverse of S, that is if S for example is some rotation by 120° around some main diagonal, S is a rotation by -120°. So you have to represent the 48 symmetry operations on the cubie level (eventually only use the 24 symmetries which do not involve reflections) and you have to define a multiplication for two cubes/rotations/reflections on the cubie level. Sound a bit complicated but indeed it is not trivial.
https://github.com/hkociemba/RubiksCube-TwophaseSolver/blob/master/cubie.py
has Python code how to multiply edges and corners on the cubie level and
https://github.com/hkociemba/RubiksCube-TwophaseSolver/blob/master/symmetries.py
shows how 4 basic symmetries are defined on the cubie level. All other symmetries then are generated by multiplications of these for basic symmetries.

 

[Neel Khandelwal]

This cube has no symmetry. Indeed Cube Explorer checks symmetries on the cubie level. Cube moves like R, D2 etc are handled in the same way as the 48 possible cube rotations and reflections. All are represented in the same format as a cube state on the cubie lev, though for cube reflections things are a bit more complicated since reflected corners are described by orientations 3, 4 and 5. You can multiply those states/reflections/rotations. Now a cube C has a symmetry S if applying S*C*S^-1 =C and this is what Cube explorer or the Python implementations checks. S^-1 is the inverse of S, that is if S for example is some rotation by 120° around some main diagonal, S is a rotation by -120°. So you have to represent the 48 symmetry operations on the cubie level (eventually only use the 24 symmetries which do not involve reflections) and you have to define a multiplication for two cubes/rotations/reflections on the cubie level. Sound a bit complicated but indeed it is not trivial.
https://github.com/hkociemba/RubiksCube-TwophaseSolver/blob/master/cubie.py
has Python code how to multiply edges and corners on the cubie level and
https://github.com/hkociemba/RubiksCube-TwophaseSolver/blob/master/symmetries.py
shows how 4 basic symmetries are defined on the cubie level. All other symmetries then are generated by multiplications of these for basic symmetries.

Woah! That cleared a lot of confusion because I initially thought about applying a move M, and then applying rigid rotations to the newly received cube state after M.

But through the example you gave above about the symmetries formed by the generator U R. I understood that you rigidly first rotated your cube in 24 different ways, apply the same generator, and then reverse the rotation. And that gives rise to different cubes generated by U R, D F, D B, etc.
I could not think about the generator logic before.

I now implemented it correctly and also ran few tests to verify the same. And now I would want to ask you how do you choose the canonical representative.
I store each cube state as (((co*2048+eo)*495)+ud). And I chose my canonical value as the minimum of all symmetries for a given generator.

And then to create a pattern database: I perform a reverse BFS from an original state (null generator {} )(depth 0) to all different possible generators and enqueue only the newly found canonical values. Doing that I noticed that the the canon value of a null generator is 0, and the canon value of any of the first(depth 1) 18 moves is also 0. Because all the 18 moves are symmetrical to U, which is almost a neutral move.

My BFS expands by applying all 18 moves on a new element. But as 0 already exists, it does not enqueue any of those 18 new generators, because 0 already exists. And now I'm stuck. How do I go about implementing this, given that I got the symmetries right. Plus, how long does this pdb generation take?

I'm sorry my doubts sound very amateur . But I really wish to implement your algorithm completely as there is so much to learn from it and you. And you are the only person I can approach to, at this time.

 

[Herbert Kociemba]

I store each cube state as (((co*2048+eo)*495)+ud). And I chose my canonical value as the minimum of all symmetries for a given generator.

This is the right way. But which symmetries do you use? For corner orientation co you may use only those 16 symmetries (or 8 if you do not use reflections) which fix the UD-axis. Without reflections these are 8 rotations. The same holds for UD slice coordinate ud. But edge orientations is even worse. A U and R move does not change eo if applied to the original state, but F does. To be able to reduce eo by the 16 symmetries you have to combine ud and eo in a single coordinate (0..495*2048-1) and find the representants. If you use 16 symmetries it will be exactly 64430 equivalence classes, using only the 8 rotations will give a bit less than twice of this.

And then to create a pattern database: I perform a reverse BFS from an original state (null generator {} )(depth 0) to all different possible generators and enqueue only the newly found canonical values. Doing that I noticed that the the canon value of a null generator is 0, and the canon value of any of the first(depth 1) 18 moves is also 0. Because all the 18 moves are symmetrical to U, which is almost a neutral move.

This is exactly what you are doing wrong. F and B moves by 90° change edge orientation.

 

[bcube]

I am wondering:

• is there an easy way to calculate the count of unique symmetry-reduced states for NxNxN 3-color (same color on opposite faces) and 6-color cubes?

The ratio between the count of states without symmetry reduction and the count of unique symmetry-reduced states:

• 3-color 2x2x2: 25,515/2,540 = 10.045 (source)
• 6-color 2x2x2: 3,674,160/154,608 (24-fold symmetry, see the next post) = 23.764 (source)
• 3-color 3x3x3: 10,863,756,288,000/226,331,259,372 = 47.9994 (source)
• 6-color 3x3x3: 43,252,003,274,489,856,000/901,083,404,981,813,616 = 47.99999982 (source)
• 3-color 4x4x4: 196,027,906,155,517,884,227,905,125,000/? = ? (source)
• 6-color 4x4x4: 7,401,196,841,564,901,869,874,093,974,498,574,336,000,000,000/? = ? (HTR having 192 symmetries - source. However, 1 corner is not fixed here, whereas in the 2x2x2 cases above 1 corner is fixed as a reference point)

 

[bcube]

In this post, Herbert is saying: "[...] the fixed corner irritates me a bit."

It irritates me a bit that the following ratios are much less than the expected value of a little bit less than 48. The cause for it is the fixation of 1 corner.

• 3-color 2x2x2: 25,515/2,540 = 10.045 (source)
• 6-color 2x2x2: 3,674,160/154,608 = 23.764 (source)

6-color 2x2x2 above is for 24-fold symmetry. The number of unique states with 48-fold symmetry is 77,802 (source), so 3,674,160/77,802 = 47.224

Without 1 corner being fixed we will get:

• 3-color 2x2x2: 153,090/3,393 = 45.12 (source)
• 6-color 2x2x2: 88,179,840/1,841,970 = 47.87 (source)