# Optimal solutions for two important subgroups

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 Following table for the group that fixes edges has been computed by Tomas Rokicki and independently by myself: dep arrangements M M+inv 0f 1 1 1 8f 528 11 6 9f 360 8 5 10f 2521 63 43 11f 5220 117 68 12f 72008 1541 821 13f 217374 4584 2378 14f 1084624 22743 11690 15f 4905894 102419 51896 16f 16944222 353629 178786 17f 20029566 418360 212304 18f 827386 17502 9419 19f 216 7 7 --------- ------ ------ 44089920 920985 467424 Group that fixes edges quarter turn metric 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 240 5 3 10q 288 6 3 12q 8764 197 113 14q 116608 2475 1303 16q 1075761 22536 11588 18q 9978950 208393 105516 20q 30348006 633616 320955 22q 2561302 53756 27942 -------- ----- ------ 44089920 920985 467424

## Comment viewing options

### I still am not sure of the nu

I've put the 11588 unique length 16q sequences in the file http://tomas.rokicki.com/16q.txt. I've verified these are unique and I've verified they are canonical; the sequences given are all of length 16.

So either I've got a major bug somewhere, or I'm misunderstanding something. The fact that we agree on 0..14 would seem to contradict the latter.

Anyone see what I'm doing wrong?

### Re:Error in calculations

Have you verified the other depths?

Have you verified the group that fixes cubies?

### Re:

19f 216 (7 unique w.r.t M + inv)

18f 827386

17f 20029566

16f 16944222

15f 4905894

14f 1084624

13f 217374

12f 72008

11f 5220

10f 2521

9f 360

8f 528

7f 0

6f 0

5f 0

4f 0

3f 0

2f 0

1f 0

0f 1

The positions needing 19f in generator form:

F U D2 R2 L2 F2 B' U' L2 B U B D L2 F2 D2 L2 F2 U2

R2 B' R2 L2 U2 B2 D' B2 D2 F' R2 L2 D' R2 U2 B2 U B2 D'

R U R' B2 L U' R2 L U' F2 R L2 B2 U' R2 D2 R2 D B2

U2 B R2 B2 U R2 U B' D F2 L2 B D' R2 F2 R2 L2 D' F2

R' U D' L B2 R' L U' B2 D B2 R' D R2 F2 D F2 L2 U

U B2 D2 R2 D' R2 B2 D' F' U L2 D B' R2 U2 B U' L2 F'

R2 D L2 D' L2 F D F' R2 F U' B' L2 B L2 B' U L2 F'

Can you see if you get the same for this?

### I confirm all those numbers:

dep | arrangements | M | M+inv |

0 | 1 | 1 | 1 |

8 | 528 | 11 | 6 |

9 | 360 | 8 | 5 |

10 | 2521 | 63 | 43 |

11 | 5220 | 117 | 68 |

12 | 72008 | 1541 | 821 |

13 | 217374 | 4584 | 2378 |

14 | 1084624 | 22743 | 11690 |

15 | 4905894 | 102419 | 51896 |

16 | 16944222 | 353629 | 178786 |

17 | 20029566 | 418360 | 212304 |

18 | 827386 | 17502 | 9419 |

19 | 216 | 7 | 7 |

44089920 | 920985 | 467424 |

### With my silly algorithm, it t

Feel free to put it any of this stuff on the main page as you will.

### At least one number wrong

### Re:Wrong numbers

I am almost sure that GAP has a way to do it. I will try to find something in the manual.

### I haven't really played with

http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Martin_Schoenert__Re__The_real_size_of_cube_space.html

### Optimal Solutions in Half Turn Metric?

### Time to compute the tables

### FTM results for fixed edges

I myself have optimized the maneuvers for all symmetric cubes of kind O_h, D_3d, T_h, C_3v, T, D_4h, D_3, D_4, D_2d, C_4v, C_4h (see Cube Explorer for the definitions of these symmetries) and found 42 cubes which need 20 moves ( and no which need more). I used a new optimal solver for this purpose , which optimally solves a random cube in less than two minutes on my PC on average.

### Cubes that require 20f

Dr. Kociemba, would you be willing to share the information on the space that your huge (3GB) pruning table uses? I may write a Linux version of that so I can optimize these things faster.

### They are all the positions re

I need a better optimal solver; this one is taking forever to prove these positions.

### When Herbert asked me for opt

By the way does my depths for QTM agree with yours now?

### Very huge optimal solver

Ok, The idea of the very huge solver is quite simple. In addition to the standard optimal solver coordinates (see my homepage for details) I added a fourth coordinate which describes the positions of four corners (ignoring their order). This coordinates range is from 0..69.

Instead of building a huge pruning table of more than 2 GB (this actually would not work well because you hardly will find a continuous block of memory of this size) I use 70 tables of the size of the standard optimal solver. When generating the pruning table I need 2 bits/entry, so the standard optimal solver size is 64430*2187/4 byte, which is about 35 MB, so the total memory when generating the table is about 70*35 MB which is less than 2.5 GB. After generating the tables they are compressed to 1.6 bits/entry, so the table saved to and loaded from the hard disk is about 2 GB and they also only use about 2 GB of memory.

The additional coordinate must be "compatible" with the transformation done by the 16 symmetries (let's call this group M0 here) which preserve the UD-axis, so you cannot use any 4 corners for this purpose. I tried two different possibilities:

a) four corners on a tetraeder e.g. URF,UBL,DLF and DRB and

b) four corners of the U-face: URF, UFL, ULB and UBR

The number of positions wrt to M0 (not the number of internal states of the pruning table) and their distances in FTM are

in case a)

0 1

1 2

2 8

3 62

4 649

5 7829

6 96900

7 1201690

8 14742203

9 172627707

10 1640065078

11 6132445955

12 1739371520

13 316350

and for case b)

0 1

1 2

2 13

3 111

4 1268

5 15415

6 192929

7 2403941

8 29400724

9 335538985

10 2772495855

11 6049092242

12 511363027

13 2117

So in other words you could say that in 13 FT-moves you can fix the orientations of corners and edges, put the edges of the UD-slice into their slice and put the corners into their tetraeder (case a) or the UD-face corners into the UD-face (case b).

On first glance it seems, that case a) is superior to b), because pruning table has more entries with high distances. But when applying the optimal solver, it is applied in three directions, and then b) is faster. Because when you apply an arbitrary move on the ID-cube, for one of the directions the distance will stay 0 with this coordinates (for example an U-move applied on the ID-cube does not change the orientations of the corners and edges, the UD-slice edges stay in their slice and the U-face corners stay in that face).

And now, if your pruning table gives for example distance 12 in all three directions, you know that the true distance is at least 13, which improves speed considerably.

Another convenient property is, that if the U- face corners are in the U-Face, the R-face corners are in the R-face and the F-corners are in the F- face simultanously, all corners are in place.

I just today finished the optimal maneuvers for all cube positions which *exactly* have symmetry S_6 (three fold symmetry along a long diagonal + point symmetry to the cube center, 3870 cases unique wrt M) and found 88 positions that need 20 moves here. I will give the detailed results on my homepage when I have some time. Computation for this symmetry class took several days.

### The new solver is available o

### Re:

The solver will be available very soon. A friend of mine is almost finished writing a C++ version. I estimate 1 month maximum until it will be available.

### Re:FTM results for fixed edges

### Re.FTM results for fixed edges

### "Group that fixes edges" is c

### Re: "Group that fixes edges" is c

I'm pretty sure that by "Group that fixes cubies," Silviu means the group where the locations of all cubies are fixed, but their orientations may change (as long as the conservation of flips and conservation of twists are satisfied). There are 2048*2187 = 4,478,976 total positions in that group, in agreement with Silviu's data.

My analysis of the permutations of the cubies showed that the cubies can be placed in the correct positions (but not necessarily in the proper orientation) in 18 quarter turns or less. The cubies can then be oriented using no more than 24 additional quarter turns. Thus, this provides a way of solving the cube with no more than 42 quarter turns. (Of course, Silviu had already found that solving edges first, then solving the corners without any net effect on the edges, is another two-phase method that is superior in terms of the number of quarter turns required.)

- Bruce Norskog### Re: 42q

You can take each position that requires 24q and compute 12 different solutions, each of this 12 solutions ending with one of the 12 generators {U,L,F,B,R,D,U^-1,L^-1,F^-1,B^-1,R^-1,D^-1}. And when you want to solve an arbitrary element

**g**in the cube group you first multiply it by B^-1 from the right and take it to the "group that fixes cubies" and then multiply it by an element in that group to take it to the identity.

So

**g***B^-1*A^-1=id ->

**g**=A*B.

If A requires 22q or less then then the length of

**g**is 40 or less.

If A requires 24q then we write B as X*C where X is one of the twelve generators. And C is an element of length 17 or less.

We assumed that A can be written as D*X^-1 and D is of length 23. That is because we assumed we have a solution that ends with any generator. And when combining solutions we get that

**g**=AB=D*X^-1*X*C. We get cancellation which shows that any cube can be done in 40q max.

Thus the only thing we have to show is that the 24q positions are local maxima. For that we need to take each position g in the "group that fixes cubies" that requires 24q, multiply it by each generator from the right, and check if the new position requires 23q. The total number of positions are 4 and multiplied by each generator gives 48 positions needed to be solved optimally. One such position requires typically 10-20 hours on Michael Reids solver so it is not unreasonable.

The method above is just a special case of the method i used to show that any cube can be solved in 28f.

In case someone wants to do this analysis i give the 24q positions:

1.) F R' U B2 U R D F U' B R B2 D B R' U' F' B R U2 D' (24q*,21f)

2.) F R' F2 R' U F U L B2 R B D2 F R' B' D B L' D' R' U' (24q*, 21f)

3.) F R D2 B' R' F R' D2 B' D' L F L2 U B' U F L2 U' B' (24q*, 20f)

4.) superflip

The superflip is already known to be a local maxima so no investigation is needed for that one.

I have also computed optimal solutions in the face turn metric for this particular positions and two of them required 20f and one 19f.

### I've been using a slightly di

Given a sequence s that you believe is a local maxima, build a list of all sequences s.a where a is one of the moves (for q, that's a list of 12 sequences each one longer). Now start with length len=2. For each element in the list, find the optimal solution to the suffix of length len of that element, and solve that suffix optimally. If there is a shorter solution, then you can discard that element from the list; it is not optimal. After you are done, you have a new (hopefully shorter) list; increase len to 3, and continue.

BTW, in the face turn metric, is a local maxima "strict" (i.e., every position one move away is strictly closer to start than the original position), or "not strict" (some positions one move away may be at the same distance as the original position)?

### I've proved that the three se

It took 13 hours and 51 minutes on a 2.8GHz P4.

I used the technique above. The list started out with 36 entries. Three were eliminated at length 2, one at length 3, one at length 4, 9 at length 22, and the remaining 22 at length 23. So the longest solutions I had to find for this proof were of length 22, which are far easier to find than solutions at length 23. (It took my old optimal solver less than 12 minutes on average to find each solution of length 22; I'm sure Reid's or Kociemba's would have been much faster than that.)

## Ok, now i have corrected the