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

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,000I do not know if someone has already done the same analysis for the corner and edge orientations so I went ahead and generated the numbers;

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,976in the FTM metric we know that the H subgroup has a max depth of 18 and the max depth of its cosets is 12 which leads to the conclusion that God'number is bound by 18+12=30...

Can we apply the same logic using the above analysis to deduce that God's number in QTM is bound by 18+10=28??

The only difference is that the H set is a subgroup while the set of corner and edge permutations only [without orientations] is not a subgroup of the cube group. If this set is not a subgroup what is it called mathematically? and is there anyway the logic of adding the two depths still hold?

As you know the max limit in QTM is hold by Rokiki at 29q. Can the above reduce it to 28q?

## Comment viewing options

### Coset

Unfortunately, there's no obvious way to combine the results from two subgroups to get the result you seek.

The set of corner and edge permutations is indeed a subgroup; why do you think it is not? It's clearly a group and it's clearly a subset of the larger group (fixing the orientations); there are no other requirements.

Adding two depths works for a group and the cosets generated by that group, if the generators you are using to define the depth keep you in the group. For the case of corner and edge permutations, fixing the orientations, the usual generators do not keep you in the group. (Specifically, F for instance is *not* in the corner/edge permutation subgroup, since it does not maintain orientations. Unless you define your orientations differently, but clearly one of U or F must change some orientation.)

### The set of corner and edge permutations is a group

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.

### corner and edge permutations as a subgroup

ρ = 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

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 2n

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 des

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 gue

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 t

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.

### This would yield 32 or more for the upper bound

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.)

### Results for other orientation schemes

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 inde

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 t

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

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

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 expla

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 an

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*).

### Don't you mean 495 Kociemba c

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.

### Cosets

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.

### Yes, trivial coset has a 24q*

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.

### Recollections of Thistlethwaite's Algorithm

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.

## Subgroups and product groups

Consider the group Z_3 of (0,1,2) with operation + (mod 3) and generators +1 and -1; the diameter here is 1.

Consider the group Z_5 of (0,1,2,3,4) with operation + (mod 5) and generators +1 and -1; the diameter here is 2.

Their direct product Z_3 X Z_5 is ((0,0), (0,1), (0,2), (1,0) ... (2, 4)) with operation (a,b) + (c,d) = ((a + c) % 3, (b + d) % 5)). With the generators +1 = (1,1) and -1 = (2,4) the diameter is 7.

There's no way to "cheat" with these generators and do the Z_3 "part" first and then later the Z_5 "part" (which is essentially what you're doing when you're adding diameters to generate a new diameter).