An analysis of the corner and edge orientations of the 3x3x3 cube

What I meant is that the set of corner and edge permutations is a group only if you ignore the orientations _completely_, but if you look at this set while still defining each element of it using its orientation then the set is not a group because the product of two elements is not necessarily an element of the set.

The H set however is a group regardless if the coordinate of its cossets are ignored or not as the product of two elements in H is always an element of H no matter what coordinates are used.

I am not sure I explained myself well.

Thank you for your Z_3 X Z_5 example.

I think I may have commented before that the usual definition of a subgroup requires the subgroup to contain a subset of elements of the original group (as opposed to consisting of a partitioning of the elements of the original group). However, we can define:

ρ = U' R2 U R2 U2 F' L' U' B U2 B' L F R' U'
λ = U' L2 U L2 U2 B' R' U' F U2 F' R B L' U'
φ = L B2 R' F2 D' R B2 L' U' F2 R' F2 R U'
β = R F2 L' B2 D' L F2 R' U' B2 L' B2 L U'

Then clearly <U, D, ρ, λ, φ, β> is a subgroup of <U, D, R, L, F, B>. Just think of ρ as an "R" that doesn't affect orientation, and similarly λ, φ, and β being like L, F, and B.

Thanks Bruce.

Correct, the subgroup generated by U, D, ρ, λ, φ, β is clearly a subgroup of U, D, R, L, F, B. This subgroup has elements that have all possible corner and edge permutations but all elements have the exact same orientation. This set of elements however is not the same set described by the depth table you generated:

Distance       Positions    
--------       ---------    
 0q                    1    
 1q                   12    
 2q                  114    
 3q                1,068    
 4q               10,011    
 5q               93,840   
 6q              877,956   
 7q            8,197,896   
 8q           76,405,543   
 9q          710,142,108   
10q        6,565,779,580   
11q       59,762,006,092   
12q      506,821,901,799   
13q    2,893,096,350,672   
14q    4,311,353,832,128   
15q    1,874,759,336,092   
16q        3,517,320,867   
17q                  220   
18q                    1   
       -----------------   
       9,656,672,256,000 

The elements of the above table have all possible corner and edge permutations but they do not have necessarily the same orientation. And the product of two elements of this set does not belong necessarily to the set and that is why this set is not a subgroup.

In other words we are talking about two sets, one set is defined as:

1)All elements that have the exact same orientation and different corner and edge permutations [this is indeed a subgroup].

2)All elements that have different corner and edge permutations and where the orientation of each element is the closest orientation to START. [This is the set for which you have generated the above depth table and this set is not a subgroup].

BTW, how did you come up with these 19q four generators?:

ρ = U' R2 U R2 U2 F' L' U' B U2 B' L F R' U'
λ = U' L2 U L2 U2 B' R' U' F U2 F' R B L' U'
φ = L B2 R' F2 D' R B2 L' U' F2 R' F2 R U'
β = R F2 L' B2 D' L F2 R' U' B2 L' B2 L U'

Are they the longest elements of the subgroup U, D, ρ, λ, φ, β?

Thanks.

mdlazreg, I agree that the 2nd set that you're trying to describe is clearly not a group. But I would not really agree that that set is how I interpret my table.

The 20 pieces (8 corners and 12 edges) can legally permuted in 12!*8!/2 = 9656672256000 different ways (ignoring how the pieces may be oriented). Thus, the sum of the positions in the table equal that number. The way I view the table is like this: for each possible permutation of the cubies (ignoring their orientation), it was determined how many quarter turns are required to move all the cubies into their correct locations (again, ignoring orientation), and the table shows the resulting number of these permutations that are at each each (optimal) maneuver length.

The analysis I did actually created a table (many gigabytes in size) that gives the actual distance for each permutation configuration after reduction by symmetries. Thus, that table can be used to quickly determine an optimal QTM move sequence to correctly permute the cubies for any given permutation. Taking the inverse of that sequence will then give a move sequence to generate a position in the cube group with that permutation of cubies. To my understanding, such elements would be what comprise what mdlazreg meant by the 2nd set. I note that some permutation cases may have multiple orientation configurations that can be solved in the same optimal number of moves for that case. Comparing my table with Jerry Bryan's or Tom Rokicki's tables for the whole cube group, one can see that such cases must occur at distance 6q and higher.

I also note that my table does, in fact, specify the number of positions at each distance in the Cayley graph of <U, D, ρ, λ, φ, β>, assuming the "basic moves" are considered to be U, D, ρ, λ, φ, and β (and their inverses) instead of U, D, L, R, F, and B (and their inverses). I would say that the use of "q" in the table is then technically incorrect, since we are using a metric based upon U, D, ρ, λ, φ, and β instead of the QTM generators U, D, L, R, F, and B.

To come up with the ρ and φ maneuvers, I simply chose a common orientation scheme, brought up Cube Explorer, applied R (or F) to the solved cube and then fixed the orientations of the pieces in the orientation scheme I chose. Then I had Cube Explorer generate optimal generating sequences for them. The maneuvers for λ and β are simply derived from the other two sequences.

I note that there are four rather logical EO (edge orientation) schemes and three rather logical CO (corner orientation) schemes. These can be combined to produce 12 orientation schemes (but really three after symmetries are used). I'll assume we use <U, D, R2, L2, F2, B2> for corner orientation. Then, for EO we could use:
(1) <U, D, R, L, F2, B2> EO scheme (or <U, D, R2, L2, F, B> EO scheme)
(2) <U2, D2, R, L, F, B> EO scheme
(3) EO scheme where every quarter-turn of a face is considered to change the orientation of the edges that are moved.

I mention this because in the original post, mdlazreg did not mention which orientation scheme was being used in his analysis, but I am guessing he probably used the first one in the above list. (There are, of course, many other possible orientation schemes than these.)

Let me give an example to describe the way I interpret your table:

take the START position in the whole cube group. This START position has all cubies in their home positions and all orientations are 0 [by convention]. This START position has 2^11*3^7 other sister positions that all have the cubies in their home positions but the orientations are not in the START orientation. Your table basically discards all these other positions and only cares about the START position because it is the first position "hit" among the 2^11*3^7 positions in a breadth-first search.

This is true for any other position, let's call it P[CL,CO] where CL is the cubies locations coordinate and CO is the cubies orientations coordinate, if you fix the CL coordinate then you have 2^11*3^7 similar positions. Your table basically discards all of them except one representative that has an orientation that is the closest to START [the first one "hit" in a breadth-first search...].

So your table is simply a breadth-first search except that for each new generated position you only compare the CL coordinate against existing positions. This means that out of each set of 2^11*3^7 positions, only the closest orientation is counted...

So really both interpretations are correct:

1)The table describes positions generated by U,D,R,L,F,B where the CO is ignored. This means that the position with the closest orientation to START is what is taken as a representative of all positions of a fixed CL.

2)The table describes positions generated by U, D, ρ, λ, φ, β. This means all positions in the table have the exact same orientation CO and all possible CL coordinates.

You are right, in my orientation analysis I used the first orientation scheme.

Basically I started a breadth-first search using the generators U,D,L,R,F,B while comparing new positions against old positions using only their CO coordinate... The search is very quick and stops at a depth of 10 as all possible positions are generated.

Well yes, mdlazreg, I can guess you can look at my analysis your way if you find that useful to you.

I'll just note that my analysis did not bother keeping track of any orientation information whatsoever. To store 1 orientation value per permutation would have added immensely to the amount of disk storage required, and would have significantly impacted the execution time of an already very ambitious analysis.

Yes I know you did not keep track of any orientation information explicitly but implicitly it was there, for each new permutation you were storing you can view it as a permutation with the closest orientation to start.

What would be very interesting is to generate the depth table for cubies permutations with a fixed orientation.

Silviu has already generated the table for the group that fixes cubies:

Distance        Nr of pos       Unique wrt M    Unique wrt M + inv

0q              1               1               1
2q              0               0               0			
4q              0               0               0
6q              0               0               0
8q              0               0               0
10q             0               0               0
12q             441             11              8
14q             3944            87              52
16q             32110           708             396
18q             456025          9656            5009
20q             2873194         60399           30978	
22q             1113236         23652           12424
24q             25              4               4
                --------        -----           ------
                4478976         94518           48872 

It would be nice if we can have the table for the group that fixes the orientations. If the diameter of that table is D then the cube diameter has an upper bound of 10+D.

> It would be nice if we can have the table for the group that fixes the orientations.

That would be the group I referred to as <U, D, ρ, λ, φ, β>
(unless you want to choose a different orientation scheme).

If you look at the estimated distribution of distances for QTM from this thread:


http://cubezzz.homelinux.org/drupal/?q=node/view/139


it appears that over 15% of the positions in the cube group are at least 22q*.
So it would seem that a large subset of positions such as those in the group
<U, D, ρ, λ, φ, β> would have some 22q* positions.

I took, for example, the position corresponding to the distant-18 position from my
analysis, and found that its representative in
<U, D, ρ, λ, φ, β> is indeed 22q*.
So we know this subgroup contains
at least one 22q*.

F U' F L' F' D F' R' L U' D F R' L D R' D L' F' L U' L (22q*)

So the upper bound determined this way would be at least 10+22 = 32.

(I also checked for optimal QTM maneuvers for ρ and φ and found that they
are actually 17q* positions.)

Converting the solver sequences into generating sequences by taking the inverse, I got:
ρ = D U L F2 U' L R D L' R' U F2 L' D' U' (17q*)
φ = L F L' F' U' F' R' F' R2 F U' F' R' F U2 (17q*)

(I used Rokicki's QTM solver to find the optimal solutions above.)

I thought I might have analyzed the orientation graph before myself, so I looked in this program I've written where I have done a number of miscellaneous analyses. Sure enough, I had done an orientation analysis, except that I had used the 3rd orientation scheme of those I mentioned earlier. With some minor changes, I was able to modify the code to do all 3 schemes, in both FTM (aka HTM) and QTM.

I also note that from a Google search, I have found that Jaap had earlier posted the results for the first orientation scheme in both metrics. ( link )

I note that regardless of which of these orientation schemes is used, the worst case positions are 10 moves for QTM and 9 moves for FTM. The results I got are tabulated below.

Orientation schemes
Scheme 1: <U, D, L2, R2, F2, B2> corners, <U, D, L, R, F2, B2> edges
Scheme 2: <U, D, L2, R2, F2, B2> corners, <U2, D2, L, R, F, B> edges
Scheme 3: <U, D, L2, R2, F2, B2> corners, all quarter-turns "flip" the edges moved

Quarter-turn metric

     Scheme 1  Scheme 2  Scheme 3

  0         1         1         1
  1         4         6         6
  2        34        51        51
  3       300       438       464
  4      2556      3696      4116
  5     21276     30732     34172
  6    168539    236736    268236
  7   1038210   1324634   1529652
  8   2562320   2506952   2417110
  9    683124    375596    225128
 10      2612       134        40
      -------   -------   -------
total 4478976   4478976   4478976


Face-turn metric

     Scheme 1  Scheme 2  Scheme 3

  0         1         1         1
  1         4         6         6
  2        46        67        75
  3       504       700       878
  4      5662      7572     10272
  5     61008     78880    111544
  6    549711    684194    980413
  7   2422226   2561608   2968674
  8   1431344   1140034    407069
  9      8470      5914        44
      -------   -------   -------
total 4478976   4478976   4478976

I am glad my numbers are independently confirmed. I apologize to Jaap as I have not seen his earlier results.

I like scheme 3 better because it has fewer positions at higher depths. This means that it might be less effort checking such positions one by one to prove they do not reach the D+10 limit.

By observing that the antipodes in the orientations table must have a move that takes them to a cosset closer to START we can deduce that the upper bound is really D+9.

Solving the other positions one by one might reduce the D+9 limit further.

If we assume that D is 22 then D+9 is 31 which is only 2 from the current 29 proved limit.

BTW, do you have the above tables with symmetry applied? Thanks.

I am responding to parts of the previous post by mdlazreg, quoting the parts that I am responding to.

> By observing that the antipodes in the orientations table
> must have a move that takes them to a cosset closer to START
> we can deduce that the upper bound is really D+9.

I don't follow this argument. I note that with this approach, we are solving orientation optimally, and then solving permutation without changing the orientation. When we get down to 1q away from solving orientation, there will always be two choices of move to finish solving the orientation. That guarantees we have at least two possibilities of avoiding a 22q* (or higher) case. But I still don't see how we can conclude we can avoid 22 + 10.

> If we assume that D is 22 ...

Of course, this is an assumption (as mdlazreg said). The task of proving it seems to be a rather large task. I note that my cubie permutation analysis was basically a breadth-first search, and used 48x symmetry reduction. This analysis requires moving through positions outside this subgroup, so it is not a simple breadth-first search. Symmetry reduction would only be 16x because of corner orientation. Symmetry + antisymmetry would get it up to 32x reduction. So we're talking in excess of 300 billion positions to solve.

> BTW, do you have the above tables with symmetry applied? Thanks.

No, I did not use symmetry reduction.

When you get down to 1q away from solving the orientation you have two possiblities but there is nothing that guarantee that at least one of them is going to be less than D... It is very much possible that both of them will hit a D position. So I am not sure you can reduce it this way or I am missing something.

The D + 10 limit however can be avoided because if you take a position at the D distance then you look at its 2612 antipodes in:

Distance       Positions    
--------       ---------  
0q                     1
1q                     4
2q                    34
3q                   300
4q                 2,556
5q                21,276
6q               168,539
7q             1,038,210
8q             2,562,320
9q               683,124
10q                 2612
       -----------------   
               4,478,976 

they must have a move that connects them to a position among the 683,124 positions in a coset that is at distance < D. This means that the 2612 antipodes have a limit of D - 1 + 10, the rest of the positions have a limit of D + 9. So in both cases it is D + 9.

We now know that D is at least 24. So the upper limit proved this way is at least 33.

I still don't follow what you're saying. You seem to be talking about "positions" in the orientation set (where the permutation of the cubies is ignored) and positions in the cube group as if they are the same thing. You are talking about cosets without specifying the subgroup for the coset. The logical subgroup for defining the cosets would seem to be the subgroup of all cube positions where the cubies are permuted but always oriented. Perhaps you are making an implicit assumption that if a cube position g requires n moves to bring it to the identity coset, then the inverse of g also requires n moves to bring it to the identity coset. Clearly that's not the case - consider RU (distance 2q) and and its inverse U'R' (distance 1q, since the move R brings the cube back into the identity coset).

So far, I'm unconvinced your D+9 conclusion is a valid one.

(This post was edited to fix the description of the subgroup. I realized I originally described the wrong subgroup.)

Hi Bruce,

Let me try explaining this using the following diagram:

                  B-----A
                   |  /|
                   | / |
                   |/  |
                  b|----a
                   |   |
                   |   |
-----------------------
S                  E   F

The point S represents the START position.
The segment SF represents the permutations in the solved orientation and has a depth of D.
The segment AF represents the orientations cosset which has a depth of 10, The point F is an antipode in the group of permutations with a solved orientation and is the starting position for the cosset AF.
The point A represents antipodes positions on the antipodes orientations cosset.
The segment BE reprensents another orientation cosset that is one depth lower than the cosset AF.

Now if you look at the 2612 antipode positions represented by A they have 3 possibilities for their moves, 1)stay on the same cosset and go to a, 2)change the cosset and go to B or 3)change the cosset and go to b.

The steps to go to the START position in the three cases are:

1)Aa + aF + FS = 1 + 9 + D = D + 10
2)AB + BE + ES = 1 + 10 + (D-1) = D + 10
3)Ab + bE + ES = 1 + 9 + (D-1) = D + 9

So obviously the last case is the most advantageous provided that we can prove that for each antipode there is such a move the will go from A to b. This is very easy to check since while we are generating the numbers:

1            4
2           34
3          300
4         2556
5        21276
6       168539
7      1038210
8      2562320
9       683124
10        2612

we know about the direction of each move for each position, if it is going up, down, if it is staying in the same cosset or if it is jumping to another one. For the 2612 positions the numbers are after a unique sort like this:

 US DS  UD DD    S
 0  1    0 10    1
 0  1    0 11    0
 0  1    0  3    8
 0  1    0  4    7
 0  1    0  5    6
 0  1    0  5    6
 0  1    0  6    5
 0  1    0  7    4
 0  1    0  7    4
 0  1    0  7    4
 0  1    0  8    3
 0  1    0  8    3
 0  1    0  9    2
 0  1    0  9    2
 0  2    0 10    0
 0  2    0  3    7
 0  2    0  4    6
 0  2    0  5    5
 0  2    0  6    4
 0  2    0  6    4
 0  2    0  6    4
 0  2    0  7    3
 0  2    0  7    3
 0  2    0  8    2
 0  2    0  8    2
 0  2    0  9    1
 0  3    0  6    3
 0  3    0  7    2
 0  3    0  8    1
 0  3    0  9    0
 0  4    0  6    2
 

Where

US: number of moves that go Up while staying on the Same cosset
DS: number of moves that go Down while staying on the Same cosset
UD: number of moves that go Up while going to a Different cosset
DD: number of moves that go Down while going to a Different cosset
S : number of moves that stay on the same depth.

As you can see from above for the 2612 positions they have the US=UD=0 because they have no move that takes them to higher depth.

Most importantly their DD is never 0, which means they have all the time a move that takes them one depth lower to a different cosset and since the AF segment cosset is an antipode cosset we conclude that all its 2612 antipodes positions have a move that take them to a lower position in a cosset that is at a lower depth [segment BE]. CQFD.

This is a very interesting analysis.

Those 300B positions boil down to just 45 Kociemba cosets, so they can pretty easily be run exhaustively.

But I'm pretty sure there will be at least one 24q* in there. Right now my machines are cranking on some other stuff, but I could probably run all 45 cosets to completion.

Even the trivial coset has, I believe, at least a 23q* and possibly a 24q* by itself.

That said, the 29q* proof I did relied on only about 25,000 cosets. The proof of 28q* is in fairly easy reach; anyone with access to a few machines can probably do it pretty quickly. (I believe proving 26q* overall will be a fair bit easier than proving 20f*, because there are many 20f* positions, and most cosets are 19f* with a substantial fraction at 20f*, whereas most cosets are probably 23q* and I do not believe very many at all are 25q* or 26q*).

I was incorrect; 81 Kociemba cosets must be run. The orientation convention selected does not respect all of the 16-way symmetry of the Kociemba group.

Don't you mean 495 Kociemba cosets? Because a Kociemba coset conserves the orientations and the four edges in the UD-slice (between the U-face and D-face) stay isolated in that slice.

If we remove the last restriction and conserve only the orientation one we have a group that has 495 Kociemba cosets...

BTW, Silviu posted the result to this forum here:

   0q                1 
   1q                4 
   2q               10 
   3q               36 
   4q              123 
   5q              368 
   6q            1,320 
   7q            4,800 
   8q           15,495 
   9q           54,016 
  10q          194,334 
  11q          656,752 
  12q        2,222,295 
  13q        7,814,000 
  14q       26,402,962 
  15q       89,183,776
  16q      297,590,924
  17q      929,624,528
  18q    2,573,889,614
  19q    5,506,671,444 
  20q    6,551,983,325
  21q    3,219,955,376 
  22q      301,913,989
  23q          249,300
  24q                8 

He noted that the 24q* position is a local maximum which means it can all the time be avoided.

F R F R' L F R L' B L' F' B2 R L' F U2 R' B' L' B R' F (24q*, 22f)

I am very interested in solving these 495 cosets. I have access to some machines so let me know if I can help running your coset solver.

Yeah, there are 495 cosets, but there are only 45 equivalence classes of these cosets under symmetry. The 495 count is (12 choose 4), but of course for instance the coset with all middle edges in the upper layer is symmetrically equivalent to the coset with all middle edges in the lower layer, so only 45 need be solved.

If you want to talk machines and running these cosets, let's discuss this by chat or email. I'm just "rokicki" and I use the gmail service.

Page 5 of Silviu Radu's "New Upper Bounds" paper
does indeed show that there are multiple 24q* in
the trivial coset.

Do a web search for the number 3219955376 if you
can't find it any other way.

There are lots of published algorithms for manual solution of Rubik's cube.  A typical example might be something in the vein of: 1) solve the top layer, 2) solve the middle layer (the middle between top and bottom), and 3) solve the bottom layer.  If you don't like this particular manual technique, simply substitute your own.

To the best of my knowledge, all such manual solutions have the following characteristics: 1) they implicitly define a sequence of nested subgroups, and 2) it is not possible to proceed from subgroup to subgroup without temporarily "losing your progress" because the usual generators occasionally take you outside the current subgroup.  For example, the manual algorithm I just described implicitly defines the following sequence of nested subgroups: 1) G itself, 2) the subgroup that fixes the top layer, 3) the subgroup that fixes the two top layers, and 4) the subgroup consisting only of the identity.  When you "lose your progress" in this manner, distances to progress from subgroup to subgroup are no longer additive.  As Tom already pointed out, the subgroups that respectively fix the positions and fix the orientations have the characteristic that they "lose your progress" when moving from one subgroup to the other because the usual generators do not keep you in the original subgroup.

That brings us to the Thistlethwaite algorithm.  It was based on a sequence of subgroups where you could indeed transition from subgroup to subgroup without temporarily "losing your progress" as you made the transitions.  That is, the usual generators would keep you in the current subgroup as you transitioned to the next smaller subgroup.  The Thistlethwaite algorithm was developed in the earliest days of cubing, and it was the first algorithm that had this characteristic.  It seems to me that most if not all modern computer algorithms for solving the cube are derivative in some manner or other from the Thistlethwaite algorithm.  The main difference between modern algorithms and the original Thistlethwaite algorithm is simply that modern algorithms use a much more efficient set of nested subgroups than did Thistlethwaite.