Home »

Symmetric Cube Positions with more than 4 symmetries

Submitted by Herbert Kociemba on Fri, 02/03/2006 - 15:31.
Symmetric cube positions tend to be deeper positions than positions without symmetry. So in the search for a 21 FTM-positon it seems natural to look for positions with a higher degree of symmetry.

For the labeling of cube symmetries there does not seem to exist a really consistent procedure. Michael Reid uses a different labeling than Jaap Scherhuis which also differs from my notation. My notation uses the Schoenflies symbols, I used for example this site for a deeper understanding.

In the symmetry editor module of my Cube Explorer program, the symmetries are sorted by the number of cubes having this symmetry. For symmetries where the associated subgroup of M has more than 4 elements, the computational time and effort is not too high to get all positions and also the optimal maneuvers (in FTM).

Because we do not want to count some positions several times, we only list cubes, which *exactly* have a given symmetry. If the positons has higher symmetry, it only is counted with the higher symmetry.

All positions with more than 4 symmetries were solved within 20 moves. So a cube position which needs 21 moves must have 4 or less symmetries.

I do not list the maneuvers for all 177 cubes having more than 4 symmetries, which need 20 moves. The 88 cubes with exactly symmetry S_6 obviously are local maxima because you can map a face of the cube to any other face with an element of S_6, so I will omit them here. From the others, I did not check this yet, but I think a fast way to check if position x is a local maximum is to generate xU, xU2... and then let the two phase solver try to find a 20 moves maneuver, which usually happens within seconds.


D' R2 F' D2 F2 U2 L' R D' R2 B F R' U2 L' F2 R' U2 R' U' (20f*) //O_h

B U' R D2 B' D2 B' R B' D2 F U R F L B2 D' U' R' U' (20f*) //T_h
B2 R' B2 F U L2 F2 L F' D B F2 L2 F2 R U L2 B' R' U' (20f*)
U F2 R2 F2 D U2 B U' L' R F' U' F2 L' D2 B' R2 D F2 R' (20f*)
B' F U L U2 B L2 B2 R2 D' L' R D L2 F2 R2 F' U2 R' U' (20f*)

D L2 F2 R2 B' D2 L R U' R2 U' F2 D' R2 U' B' F' D2 R' U' (20f*) //D_4h

D' L R2 B F2 D F2 L2 U2 L2 F L R D2 U2 F' R D' R' U' (20f*) //D_3
F' D R2 F' L' D' F U R U L2 F L' U' B U2 F2 U2 R2 U' (20f*)
R F' D F' R' D L2 U' L2 D B' F2 R D' L F2 U' L2 R' U' (20f*)
R U2 B F' U2 L F U F' D' R B D2 B U L2 R F2 R' U' (20f*)

D' L2 D F L2 B L U' B R' D' L2 B R2 F2 U2 B2 D2 R' U' (20f*) //C_4h
R' D2 B2 D2 F' L B F2 U L F R B2 D2 F' D2 R2 U' R' U' (20f*)
D2 U' F' L U' B2 L2 F L' F2 L2 U2 R' D' F' D2 F U2 R' U' (20f*)
L2 F2 L2 U B2 D' L' D2 F2 R2 F D' B R B2 L U' F' D R' (20f*)
D' L' D2 F2 L D B D2 R2 B' F' R2 D2 F D R D2 F2 R' U' (20f*)
L U2 L2 U2 L F' L' U2 R' U' B' F2 U L' F D2 R U R' U' (20f*)
F2 R' B2 F D' L' U' L2 D L' B R' F' U L2 D' B' D' R' U' (20f*)
B2 L2 B2 D B2 D' L' D2 F2 R2 F D' B R B2 L U' F' D R' (20f*)
F2 U' F R F2 R U F R B L2 R2 B' L U L2 D B R' U2 (20f*)
R D B D F D2 R' U L' U2 F' R U2 L' U' R2 D2 L' R' U2 (20f*)
U' L2 U B L2 F L D' F R' U' L2 F R2 B2 D2 F2 U2 R' U' (20f*)
B R' F' R' D' L R' B D2 F D R D2 R D B R' D' R' U (20f*)
L B D' U2 B2 L2 B' L2 U L F' U F2 L2 D2 R' B2 F' R U' (20f*)
R F L' U2 L R' U' F' R2 B' F2 L' U' B2 R B2 F' U2 R' U' (20f*)
D2 F L' F' D' F' U' B D2 U2 R' F' R F2 L' R' D' F R' U' (20f*)
U2 B F2 L' R' B' D' F' D' L' B2 F' D' B' D F' D2 U R U' (20f*)
D2 F L2 D U' B D F' L' B2 U2 L2 R' D' B2 U' B' L R' U' (20f*)
R' D2 R' B F' U' R F' U2 B2 L' F U L' F2 D2 F2 D R' U' (20f*)
R D R' D B' D2 U F L2 D' R B R2 U' L R2 F U' R' U' (20f*)
R U' F D2 B2 L' R U' R' U' B' F' R D F L U2 F2 R' U' (20f*)
F D2 B L B2 U' L2 D' L B' R' D' L F2 U R2 B D R2 U' (20f*)
U' F2 L B' L' F D R U B U2 B2 U2 L' R2 U R U2 R' U' (20f*)
U' L' D' B' F' D L F R' B F L' B R U B' F' U' R' U' (20f*)
R' B F2 U2 R F' U B2 F L B F L' F D' R B' R' D2 U' (20f*)
F2 R B F D U L U R' F' R' F' R' U' R' D2 B2 F R2 U' (20f*)
U' L' U' B' F' U L B R' B F L' F R D B' F' D' R' U' (20f*)
L' R2 B U F' R' U L D' B2 U' B U2 R2 U B2 R U2 R' U' (20f*)
R' D2 L2 U R F' D R2 D L2 F2 L' B2 D' F D L' B' R' U' (20f*)
L' B D' F' R F U' F R2 U L B2 D R2 B F D2 F R' U' (20f*)
R' D L2 F' R2 D R2 B' F U2 F2 R' D' B D2 B2 F U2 R' U' (20f*)
L R2 D2 U' B2 D2 F' R D L U2 F U' B' F2 L U B2 R2 U' (20f*)
U R' B D' U B2 L R' B2 L' B' D2 F2 L2 F' U' B' F2 R U' (20f*)

L R' F' R2 D' B' F' U L' R' D F R B D2 U' R U R' U' (20f*) //D_2h type 1
F2 L R2 B' F U2 L' D L2 R B2 D U2 F2 R' F' R F' R2 U' (20f*)
R2 U R2 B L' R' F' R2 F R U' L2 B' D2 R' F L2 R2 F2 U' (20f*)
L2 R2 D' U2 R F2 U B' F R2 U' L' R F D L2 D' U R' U' (20f*)
B R' B' U' R F2 L U' B2 U' L B' L' R2 B U R2 F' R' U' (20f*)

F' L B U' B' D2 L' F2 D F' L D L2 U' R' U B' D2 R' U' (20f*) //D_2d type 2
L2 F2 L' F L' D' B' R U B F U L B U R2 B' U2 R' U' (20f*)
F L U B L' R2 B' F2 D2 B2 D2 R' B L U F D' U2 R' U' (20f*)
D U2 L' B' U2 L2 F U' B2 F2 U R' D2 B2 R' B F U2 R' U' (20f*)
D' R2 F' U2 L' D R D' F' L' R' U' L' U B R' D2 F' R2 U' (20f*)
R' F' D B L' B' U F' U2 B' R' B2 D F2 L2 U2 R B2 R U' (20f*)
R B2 U' L U R' D' B' D' L' U' F' R B' U L' F2 D2 R2 U' (20f*)
R' U R2 B F D' F' L B2 L F' U2 F' U B F R2 D' R' U' (20f*)
B2 D' U2 L2 D' F2 U R' U L U2 B' D' L' U' R2 B' R F R' (20f*)
B' F' D L' R' D' B' F' L2 R2 U' B' F' D L' R' U L' R' U' (20f*)
B' D2 B2 R' B' D R2 B' U' R' F' U R U' R2 D F2 U2 R' U' (20f*)
F2 R D B' U' R2 D2 U2 F' R F2 R2 U' L2 R U2 B2 U2 R' U' (20f*)
B F' L D2 B2 U R F' L' D' F U2 R B2 L' F2 U' B2 R' U' (20f*)
R2 B' F D' B' U B' D' F2 R' U2 F' D' U2 B' L B' U' R' U' (20f*)
F' L' B2 D B' U F2 L' F' D' R' B2 U' L' D' L' B2 F2 R2 U' (20f*)
U2 B2 F2 U' F2 U2 B' D2 U R' F' D L B' F' R D R' U' R' (20f*)
D R D' R2 B F2 R D' U' B' F D U R' B2 F' R2 U R' U' (20f*)

F' U B2 D L' R U' B2 D' F U B2 U2 R' F2 R2 F U2 R2 U' (20f*) //D_2h type 2
R' U2 L' B2 R D2 F' R U2 B2 U L F' R' D2 F R' U' R' U' (20f*)
D L R D R' D2 U2 B F2 R B L' F' L F D2 U' L' R' U' (20f*)
D' L2 R2 F' L' B D R' B2 U2 F R D' L2 F2 U' F2 U2 R' U' (20f*)
F D B2 L B' R' F D' B' D B F2 D2 R' B L D2 B R' U' (20f*)
F' L' B' D2 U' R' D' L2 B L' D2 U' B2 L' R2 B2 F2 U' R2 U' (20f*)
D2 B L' R2 U2 F' L2 F2 D B' L2 D' L' U F' R' D' U2 R2 U' (20f*)
F2 D2 F R' B' F U' F' D' U2 F L F' U' L' D2 U F' R' U' (20f*)
U L R U B F D B' F' L' D2 B2 D2 R B L R F' R2 U' (20f*)
R' B U2 R2 F R D2 F2 D2 U F2 R U2 L' F' D B' D2 R' U' (20f*)
R2 D2 B2 L D' F R' B D L U F U R D' L' D F2 R' U' (20f*)
U' L2 R2 F2 U' L2 R2 U B' D L' U' F2 L' U L2 U2 L2 R2 F' (20f*)
U L' B F2 U2 F' R2 B' D U L2 B U L2 U' B2 F U R' U' (20f*)
D' L2 D2 L' B2 D2 R2 F R2 D2 F2 U2 R2 U L2 U2 R' U2 R2 U' (20f*)
D' L2 R2 U' R2 D2 R F2 U2 R2 D2 U2 F L2 U2 F2 L' U2 R2 U' (20f*)
D' L2 R2 D' F2 D L2 B' R2 U B2 R F U L U R B U' R' (20f*)
B' F L B2 D L2 R' D L' U R2 D R2 F' U2 R' D' F2 R' U' (20f*)
B2 L' U R F U B' F R F' U' L' R2 U' L' F' U' F' R U' (20f*)
L2 D2 F2 L D' F R' B D L U F U R D' L' D F2 R' U' (20f*)
B F U2 L' D R' F' D L F D B' U2 B' U F D' U' R' U' (20f*)
D2 R' U' L2 B2 R U B2 F R' B2 D' B U2 L D' U F R' U' (20f*)
D2 F2 R D U L2 D B' R' D' L' D2 F' U B U' R' U R' U' (20f*)
R' D' L2 D B F L B L2 R2 B2 U' B D' R U F U2 R2 U' (20f*)
U2 F L2 U' B R B' L2 F' L B' U' F' L2 U R2 D' U2 R' U' (20f*)
L' F2 D' L2 B L' D F U' L2 U2 B' L2 U2 R' B L' F2 R2 U' (20f*)

R2 D' B2 R2 B2 D' L2 B2 D' F U L' D' R2 F2 U B D' R' U (20f*) //S_6
...(87 more maneuvers omitted)
» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

Naming symmetries

Submitted by rokicki on Mon, 02/06/2006 - 14:37.
I think we need a nice clean short name for each of the symmetry classes, ideally one that is somehow constructive.

I.e., when I did my cubie space exploration, I named each symmetry class by giving a move sequence that took a cube to that symmetry class. This way all I had to do to generate, or check, the symmetry class, was to apply that sequence in all 96 different fashions, and I'd know what remappings were in that class. I'm not sure this is an ideal representation, however.

(One reason I did it this way is because of the effects of antisymmetry; it's not completely obvious what the new symmetry classes introduced by antisymmetry are, so this let me deal with it in a clean fashion.)

But I dislike having "magic knowledge" of what, for instance, D_2d type 2 means.
» login or register to post comments

Dan Hoey (a frequent contribu

Submitted by Jerry Bryan on Mon, 02/06/2006 - 18:48.
Dan Hoey (a frequent contributor to Cube Lovers) came up with such a scheme. Unfortunately, he never actually posted it to Cube Lovers, so it's not really in the public domain. The names used by Michael Reed are from Dan Hoey.

What Dan came up with was names for each of the 98 subgroups of M. The name M itself as well as the name C for the rotations are a part of this scheme. Many of the 98 subgroups are of course conjugate. There are 33 classes of conjugate subgroups. Dan's names are such things as X1, X2, X3, and X4 for four conjugate subgroups of M, with the class being called X. He also arranged the classes into a lattice (well, the classes actually arrange themselves into a lattice). Whenever possible the names are arranged such that, for example, class A and class X are both subclasses of class AX.

It's a very nice system, but it doesn't do us much good without being in the public domain.
» login or register to post comments

Nice work!!! Are you going to

Submitted by silviu on Sat, 02/04/2006 - 13:55.
Nice work!!! Are you going to do less then 4 symmetries too?
» login or register to post comments

I think you mean less or equa

Submitted by Herbert Kociemba on Tue, 02/07/2006 - 14:24.
I think you mean less or equal 4 symmetries. There are too many positions to find the optimal maneuvers fo let us say 40000 cubes in one class in reasonable time. But I could try to find the 20 moves maneuvers in this class using the two-phase-algorithm to eliminate all cases which are solvable in 19 moves or less.
I am not quite sure but I have some hints that there is a bug in my program when computing the cases wrt M-symmetry, so I am trying to solve this problem first before going to compute the 20 moves (or maybe 21 moves) maneuvers.
» login or register to post comments

Symmetric search actually is

Submitted by rokicki on Tue, 02/07/2006 - 17:18.
Symmetric search actually is a quite interesting topic that I've been meaning to dicuss for a while. It turns out that, for various reasons, the amount you can reduce your search by is not simply the symmetry class, but is somewhat more complicated (and frequently somewhat better than) that. For instance, when solving superflip, you can reduce your search by about a factor of 96, whereas for PA you can only reduce it by a factor of about 48. Different positions within a particular symmetry class (or near a particular symmetry class) can have somewhat different reductions in search space. For the known hard 26q position, the reduction I see is about 45.5, even though it has only UD symmetry.
» login or register to post comments

Symmetry reductions

Submitted by Herbert Kociemba on Thu, 02/09/2006 - 09:12.
I would be interested how you get a reduction of about 45.5 with a position which has 16 symmetries.

In the moment I myself do not think so much about symmetry reductions when computing the maneuver for a special position but for symmetry reductions when computing the cubes belonging to one of the 33 symmetry classes and I only want to count and display these cubes up to M-symmetry. My actual method is quite dumb and only works well if there are a few thousend cases. I just generate the next cube in the desired symmetry class and compare it to the already generated cubes if it is equal to any of them wrt M-symmetry and throw it away in this case.

The idea for a better method is to generate only the corners with the desired symmetry first and then compare this corner configuration with the already generated corner configurations and throw it away if it already exists up to M-symmetry. If not, the edges are computed.
But this approach does not work. You lose some configurations. It took me some time to understand why.
The correct procedure is to throw a corner configuration away only if it is eqivalent to an already computed corner configuration with respect to a subgroup X of M. X is the largest subgroup of M, in which the the symmetry group H which defines the desired symmetry is normal, that is for all x in X we must have
x^-1Hx=H .
The index of H in X is an approximation for the reduction factor if you only count cases up to M-symmetry.
If you take for example H:= UD-symmetry (called D_4h in Cube Explorer) as the desired symmetry, X is the same as H and the index of H in X is 1. So there is no symmetry reduction possible at all. There are 128 cases - if you check the "allow isomorphics" box or not.
» login or register to post comments

I've done an analysis of your

Submitted by rokicki on Mon, 02/13/2006 - 19:16.
I've done an analysis of your symmetric positions listed above, and very few of them show the type of symmetric exploration reduction I saw for Reid's position (the 45.5 reduction). It appears to be a special case. The reduction is straightforward, however. I simply keep a hash table of the earliest depth a position was seen in, in 96-symmetry, for small depths, and never explore from a position already seen. For Reid's position, this gives you a reduction in symmetry that increases as the depth you keep the hash table to increases (QTM below): 
At depth 0 saw 1 out of 1 red 1 elim 0
At depth 1 saw 2 out of 12 red 6 elim 10
At depth 2 saw 10 out of 114 red 11.4 elim 22
At depth 3 saw 34 out of 1068 red 31.4118 elim 84
At depth 4 saw 220 out of 10011 red 45.5045 elim 188
At depth 5 saw 1519 out of 93840 red 61.7775 elim 735
At depth 6 saw 11697 out of 879624 red 75.2008 elim 3328
At depth 7 saw 93536 out of 8245296 red 88.151 elim 19393
At depth 8 saw 771072 out of 77288598 red 100.235 elim 124841
At depth 9 saw 6476518 out of 724477008 red 111.862 elim 873434
Note that it is critical to eliminate the antisymmetric cases. If you don't do that you only get: 
At depth 0 saw 1 out of 1 red 1 elim 0
At depth 1 saw 2 out of 12 red 6 elim 10
At depth 2 saw 12 out of 114 red 9.5 elim 20
At depth 3 saw 74 out of 1068 red 14.4324 elim 63
At depth 4 saw 656 out of 10011 red 15.2607 elim 115
At depth 5 saw 5934 out of 93840 red 15.814 elim 368
At depth 6 saw 55156 out of 879624 red 15.9479 elim 1015
At depth 7 saw 514037 out of 8245296 red 16.0403 elim 4397
At depth 8 saw 4796804 out of 77288598 red 16.1125 elim 27244
But this is apparently pretty rare; only a few positions yield more search space reduction than their symmetries.
» login or register to post comments