# Optimal solver for QTM

I have written an optimal solver console program for the quarter turn metric in C which compiles under Linux and Windows. The target subgroup for the pruning table is the permutations of <U,D,R2,F2,L2,B2> which have an even corner parity, lets call it H'. I experimented with another type of pruning table which does not store the distance to H' for each coset element but the moves which reduce the distance to H'. Because there are 12 possible moves in QTM, a 16bit word is enough for each coset element - a move reduces the distance to H' by one or increases it by one. The table fits in about 583 MB of RAM.

I tested the solver on the only known 26q* maneuver of QTM, the combination of 4-spot and superflip U2 D2 L F2 U' D R2 B U' D' R L F2 R U D' R' L U F' B' (26f*) (maneuver from Mike Reid), lets call it X. I verified with my solver that there indeed are no shorter solutions for this cube. Because of the symmetry of this position without loss of generality the first move is U or R.

So I ran two different instances of the program on my PC in parallel, one for XU and one for XR. Within a week of CPU-time I found the following solutions(I aborted the program after this time, there definitely are many more solutions)

```U U R U U F B' R R U R' L' F B U U B U D' F' B D F' B' D D  (26q*)
U U R U U D D F' B' D F' B U D' B U U F B R' L' U L L F B'  (26q*)
U U R U R' B' D F R U L L F' U R' B D' L B U' D' L F' B' D' R'  (26q*)
U U R U F U D' R' U L F R' L L F' L' B' L' F' U B' R' F D' R' D'  (26q*)
U U R U D R' L' D' B R' U L' B U L' U' F' D R' B L D R' U' D F'  (26q*)
U U R U D F B U U D D R R F R' L F B' R F B D R R F' B  (26q*)
U U R U D F B U D F' B' D' F' B U' D F' D D R' L' U L L F B'  (26q*)
U U R U D' R L' D R' L' U U D D B U U R L' B B U F' B' R L  (26q*)
U U R U D' R L' D R' L' U' D' R' L' U D B' D D R L' F F U' F B  (26q*)
U U R U D' F R U' D' L' F B' U' R L U' L L U U L F B' D F' B'  (26q*)
U U R U D' B U B' D' B D' R U B' L' U D B' D' R F' U B L' U' R'  (26q*)
U U R U D' B R L F B' R L D' R L U' F' U' L' U U D B' L' B' R  (26q*)
U U R U D' B R' B U' D R B' U R' F' D' B' R' L F D' B' R B' D D  (26q*)
U U R U D' B D' R' L F' R F R' F' U' F B R' U' R' B R U' D' F B  (26q*)
U U R U D' B D' F' L' B D' R U F U' L' F U' B L' D F B U' D' B'  (26q*)
U U R U L U R U' R' U' B' D R' U R' D D B' U B' R' F D' R' B' D  (26q*)
U U R U L U D' B' U' B U R' B' R' L' B U' R B' R L B U L F B  (26q*)
U U R U L F R L' D' R L' B R L' F' L' U' F' L' F B' U' D R L' D'  (26q*)
U U R U L B' U' F R' D B U' D' L B U' R' D B' D B U' B' U' D R'  (26q*)
U U R U L' F U F B' D' R' U' R U' L B D R' L D L B' D B' R' L'  (26q*)
U U R U L' D D R' F R' B R' D L L U L' U' F B R R B U' D R  (26q*)
U U R U B U R' L' D R' L' F B' R' L' F' U' D L' U U R' B L B D'  (26q*)
...

R U U R U D' R L' D R' L' U U D D B U U R L' B B U F' B' R  (26q*)
R U U R U' R U' F L' D R' B R' F' L D R B D L B' R' B' R D' R'  (26q*)
R U U R U' D' R' L' F B L' F B U' B B R L D D R L' U F' B' R  (26q*)
R U U R U' D' R' L' F B L' F B D' R R F B D D F B' D F' B' R  (26q*)
R U U R U' L' U L U' B' L' D F R' U B' L D B' R F' R' F' B' D' R'  (26q*)
...
```

## Comment viewing options

### Random sample of cube space: q* and h*

I've let my quarter-turn optimal solver run now for a few weeks and this is the distribution of optimal solution lengths I've seen so far for random cubes:
```      1 16
13 17
137 18
1126 19
5589 20
7186 21
2623 22
7 23
```
For the half-turn metric, some old results I have show
```      1 14
37 15
579 16
6064 17
15266 18
811 19
```

### Amusing Failure

While investigating pattern sub-groups of the Rubik group I set your ultimate cube solver to finding minimum solutions for the cube patterns. One member of the groups is of course the identity element which I gave the placeholder turn sequence, R' R. I was amused to find that your solver, which vastly out-performs my solution algorithm, gave the following results.

```.
.
.
enter cube (x to exit): enter cube (x to exit):
solving optimal: U D' R D R' D' R L' U L' U L' B' B' L L U' L' U' U' L' U' U' L' U U L U' L U' U' L' U' U'
Cube has 4 symmetries.
Computing optimal solution.
depth 10 completed,            254 nodes,             24 tests
depth 12 completed,           5769 nodes,            576 tests
depth 14 completed,         102015 nodes,          10488 tests
U R L U U R R U D F F U D R L' U'  (16q*)

enter cube (x to exit): enter cube (x to exit):
solving optimal: R' R
Cube has 48 symmetries.
Computing optimal solution.
depth  2 completed,              1 nodes,              1 tests
depth  4 completed,             12 nodes,              3 tests
depth  6 completed,            100 nodes,             17 tests
depth  8 completed,           1159 nodes,            176 tests
depth 10 completed,          14240 nodes,           1960 tests
U U R U R' F' U U L' U' L F  (12q*)
.
.
.
```

Boundary conditions will trip you up every time.

### Failure?

Not at all! -- it found a non-trivial identity for you; i.e., one that doesn't depend simply on the commutativity of turns on the same axis.
Can be useful.

### Quibbling

It failed to find the minimum length solution, which is no turns.

### The no turn solution is quite

The no turn solution is quite easy to find even without a PC, so whoever takes the trouble to feed the identity cube into the optimal solver should be rewarded with an interesting solution ;-)

### Some Random Results Using Herbert's Program

I think the face turn metric has been researched a good bit more than the quarter turn metric, and I don't know what random results there are that are already available for the quarter turn metric.  So I did a quick and dirty run to put 50 random positions through Herbert's quarter turn metric program.  Here are the results.  (I used Cube Explorer to generate the random positions, by the way.)

```Distance   Number
from        of
Start      Positions

19          4
20         21
21         21
22          4
```

50 random positions is a pretty small sample, but clearly the distribution in the quarter turn metric is bimodal.  This seems obvious because half the positions in the quarter turn metric have to be an even distance from Start and half the positions have to be an odd distance from Start.  But quarter turn distributions are not always bimodal.

To a certain extent for quarter turn distributions, we may think of the distribution of the even positions separately from the distribution of the odd positions.  The distribution of the even positions may have a single mode or may be bimodal, and similarly for the odd positions.

What sometimes happens is that the distribution of the even positions has a single mode and the distribution of the odd positions is bimodal (or vice versa).  If so, then the overall result is what might be called "tri-modal".  Which is to say that either the odd positions or the even positions have a mode which is the peak for the whole problem.  Then, the other parity has two modes, one on each side of the big peak, where the two modes for the other parity are each about half the size of the big peak for the first parity.

But that doesn't seem to be the case for the quarter turn metric for the entire 3x3x3 cube.  For this problem, both parities seem to have a very distinct mode, yielding a bimodal rather than a "tri-modal" distribution for the overall problem.

### I ran a few more this weekend

I ran a few more this weekend, and this is the distribution I have so far:
```      7 18
52 19
227 20
278 21
107 22
```
The quarter-turn distribution appears to be fairly long-tailed, if positions 23+ are all <1% (extrapolating from this) and yet we have a known position at 26.

(This distribution is not from independent, random positions; rather, it is from optimal solutions from a random walk, so the samples are not independent. Yet it's probably still a pretty good sample of the distribution.)

### Some more Random Results

This is a slightly larger sample size than my original sample, again with random positions being created with Cube Explorer.  It's not as large a sample size as Tom Rokiki's.

Both this sample and Tom's sample suggest what I was calling a "tri-modal" distribution overall rather than a bimodal one, with the overall mode at 21q, with 21q also serving as the one and only mode for the odd positions, and with the even positions being more or less bimodal at 20q and 22q.  Well, I suppose one could quibble with calling the even positions bimodal because the number of positions at 20q and at 22q aren't really the same.  But comparing the number of even positions at 20q and 22q (which are somewhat close) is a very different thing than comparing (for example) the number of odd positions at 19q and 21q (which are not even remotely close).

``` 9  19q*
29  20q*
44  21q*
18  22q*
```

I'm not sure what algorithm Cube Explorer uses for random positions.  Tom used a random walk.  The speed cubists seem to have spent a lot of time studying the creation of random positions for competitions, but I'm not sure what conclusions they have come to.  Because they are working with physical cubes, they are inevitably led to random walk solutions.

I agree with Tom that the quarter turn distribution seems very long tailed.  In general, increasing the sample size by an order of magnitude should cause a new, shorter distance to appear in the distribution.  For example, Tom's larger sample size has positions of length 18q and my smaller sample size does not.  But it is not at all clear how large the sample size would have to be in order for positions of length 23q to appear on a regular basis.  The sample size might have to be rather large indeed in order for this to happen.

### I changed my program to do 10

I changed my program to do 1000 random moves for each position solved (so it's not *absolutely* random, but it's probably very very close), and let it run for a while, and this is what it looks like so far:
```      1 17
13 18
66 19
399 20
489 21
184 22
1 23
```
So not only did I get (a) 23, but I also got (a) 17! Wow. I'll probably let it run a bit longer. I wouldn't be at all surprised if there are additional 26's. Using a coset solver would probably be the best way to find them. I'm very interested in Herbert's results; I hope he lets them continue.

### Even/Odd positions

If you did exactly 1000 random moves for each position, wouldn't you end up with all even positions?  Did you maybe randomize 1000 moves vs. 1001 random moves for each position (or something like that) in order to get both even and odd positions?

### Actually, I did 1000 random m

Actually, I did 1000 random moves in the FTM (even though the solver works in the QTM). This means for every move there is a 1/3 probability of getting an even move and a 2/3 probability of getting an odd move. Since I'm here, these are the latest numbers:
```      2 17
20 18
102 19
621 20
772 21
294 22
1 23
```
No particular reason not to let this one keep churning for a while.

### It just passed 6400 cubes, an

It just passed 6400 cubes, and the distribution looks like this:
```      6 17
42 18
435 19
2207 20
2744 21
967 22
1 23
```

### Continuing Computation

Yes, I have some more results now.
```depth 12          11,152
depth 14         762,312
depth 16      23,104,558
depth 18     665,649,794
depth 20   7,677,782,428
depth 22   1,386,903,800
depth 24 or more     356
```
What is quite interesting compared to the even depths of the random distribution is that the relative number of depth 22 elements in this coset which contains the known 26q* is smaller than in the random distribution. It took about 90 hours to complete depth 22. I let the program continue with depth 24 (which was not very wise after all because now it is hard to identify the bits set for elements <=22q* any more and I cannot make a "linear scan" for the 24q* elements).
Within 35 additional hours I got the following 24q* solutions up to symmetry and inversion. I post then here because there are not too many 24q* known yet - as far as I know at least:
```U U R U U R D' B U' D' B U F' U B D' B R' U' L' U' B' D R  ( 24q*)
U U R U U R L F' U' D' R' F B' L' U D' F' D B D B D' L F'  ( 24q*)
U U R U U F R' L' U R' L U R D D R' L F D L' B' U' D' L  ( 24q*)
U U R U U F B' R R U R' L' F B U U F U D' F B' D F' B'  ( 24q*)
U U R U U F B' R R U R' L' F B U U B U D' F' B D F' B'  ( 24q*)
U U R U U L D B L' B R' D F' L D' R' B' U F B' U' R' B D'  ( 24q*)
U U R U U B U' L U F F U U L' D' F L B B U' F' L' B R  ( 24q*)
U U R U R U' L' U' L' F R' U' B D' L F' L D' R L' D F' U F  ( 24q*)
U U R U R R L' U F' B R F' B' U U D F' B U' F' D' F D' B  ( 24q*)
U U R U R D' R D' B' U' B R' D F' R B' U L' U D' F' D D R'  ( 24q*)
U U R U R L F' L D B L D F' D' F' L D' R' D' L F L' D L'  ( 24q*)
U U R U R L' U' F U' R L D' B D' R' L D R' F B' R L D D  ( 24q*)
U U R U R' L' B' D L F' R D' L' B' L D' F' R U B R' B' U F'  ( 24q*)
U U R U F U B B L' D B R' B' R' U D R' D' B' L D F' B R  ( 24q*)
U U R U F U B' U R' D' B' R D L' B' U L U' R L U B' L B'  ( 24q*)
U U R U F U' F' B' U F R' D B' U' F D' F R' F' D F L F' L  ( 24q*)
U U R U F R R D' B U L' F U' R L U R' U' R' D L L B L  ( 24q*)
U U R U F D' B' U' B R' D L' U' D L' U B U B L' F' B' L' F'  ( 24q*)
U U R U F L' D F' B U D' B B L U' D L' D F F D R U B'  ( 24q*)
U U R U F B D L U' L U' F D' B' U L F' B' L U L' D' F R'  ( 24q*)
U U R U F' L D' L' F' U D F' D L F' U F' U B L L U L F  ( 24q*)
U U R U F' B R U' D' F B' D D F D' R' L L B D R D L' B  ( 24q*)
U U R U F' B D' R U' B U' D' B R F U' F L D L U' F L B'  ( 24q*)
U U R U D R' F B R' U' D' R' F B R' U D L' F B U D F B  ( 24q*)
U U R U D R' F' U' D R' L U D B' R R U' F' R' B L' D' F U  ( 24q*)
U U R U D' F R D R' U R U' F' D' R U' R B D' F' R B D' L'  ( 24q*)
U U R U D' B R U' B' L U R U' B L' F U' D F' D B D' F R  ( 24q*)
U U R U D' B D B U D F' D B' L F R B U D L U' F R' F'  ( 24q*)
U U R U L U R' F L D L F' R' U' B' L B R' L D B' L F' D'  ( 24q*)
U U R U L' U R F' B R' L' F D' F B R L D' B B L U R' F'  ( 24q*)
U U R U L' U F D L L F R' F R L F' B D L' F' U F' U' L'  ( 24q*)
U U R U L' U D' R' B' D R' B' L' F D B D' R' U' F R' F D' R'  ( 24q*)
U U R U L' U B' L' D' B D F U D B U F U' R' F' D R' D L  ( 24q*)
U U R U L' U' F B' L' D B U B' R' D' F' D R U' B' U L L D  ( 24q*)
U U R U L' F' R U' B D' F U' B D' R B U' L B U' B' U R' U'  ( 24q*)
U U R U B' R D F R' U' R L F B R L D' L B' D' L' F U' L'  ( 24q*)
U U R U' R L U' B R' F' B' R' L' U' F' U B D' L' F' U F B R  ( 24q*)
U U R U' R' U R U' R' L' B' D B' R F' U L' F R F' L' D L B'  ( 24q*)
U U R U' F D D R' D' L' B U' R B' R B U U F' B B D F D'  ( 24q*)
U U R U' F D' L U' B U' F' B R B' R F B L' D R L F D B'  ( 24q*)
U U R U' F' D D R L U L B' L U D' B D R' B' R' F' D B R  ( 24q*)
U U R U' D' R' L' D B D' R' D' L' D' L D' F R D' R' U B U R'  ( 24q*)
U U R U' D' L' D' F U F L' D R D' L' D' B L F' L U D B' R'  ( 24q*)
U U R U' L F' R' D B' L F' L D F' L D R' F' L L D' R B B  ( 24q*)
U U R U' L' U B L D' R B U D L F B' U L B' D L' U' R' B  ( 24q*)
U U R R U B' U L B' R' U D' B R B R D R R U R F' B' R'  ( 24q*)
U U R R F U L' D' B B R' B' U' R L B' D B U R D' L' F' L'  ( 24q*)
U U R R D R' F' U R' B D D L' U L D' F' U' F F U' R' L D  ( 24q*)
U U R F U' R F' U D R' D F U R F B' D F R U D L B' R  ( 24q*)
U U R F D' R B' L L B B R' U U R' U' L' D' L D' B D' R L'  ( 24q*)
U U R F L U L U' F B D' F' R' L F' U' F B D' L D L F R  ( 24q*)
U U R F L D L F R L' D' F R D L' F' B U R D F D L D'  ( 24q*)
U U R F' U F B' L' F R U' D' R' B' D' R B L' U' F' U R F' R  ( 24q*)
U U R F' U' D' B U' R D B' U B' U' R' D' L L F D' R L D B  ( 24q*)
```
The now still remaining 33 cubes reduce to 9 cubes up to symmetry and inversion, including the 26q* case. The remaining 8 cubes I try to solve with my optimal solver, which takes quite some time.
I solved 3 positions with 24q* up to now, so 5 cubes are remaining.
I will change my coset explorer in a way that it automatically appends UD, UD', U'D, U'D' and all half-turn moves when depth 22 is finished to reduce the number of positions which have to be examined for >=24q*.

### Computation finished

I now have finished the computation for the 26q* coset. The eigth remainig positions also are solvable in 24 moves. Just for completeness:
```U U R F' D F' U B' D' R' L' U L U' B' L B' D F' L L D D L' ( 24q*)
R U U R' L L U U D' L' F U' B L U' B' U B' R U' F U D' F  ( 24q*)
U R U U F B' R R U R' L' F B U U B U D' F' B D F' B' D  ( 24q*)
R' U U F B L' D L' U R' L' U' B D' L B' R D' B' U' D' F D R  ( 24q*)
U R U F D' F B' R F D F F B' U' B' L U' R' F L' D' R' D' L'  ( 24q*)
U R R U R' L F' D D F B U D' L F B' D B B U F F B B  ( 24q*)
U U F R' F D' R' U' D R L U' R U B' U' D F' D' B' R' B R' D'  ( 24q*)
U R U R D' L L D' F' D R U' D B L B' U' R' F' U' B' L' U R'  ( 24q*)

So we have

depth 24             355
depth 26               1
```
Up to symmetry there are 62 24q* cubes, including antisymmetry does not reduce this number because all 62 cubes are antisymmetric(!). Only three cubes of these 62 have no symmetry:
```
U U R U' F' D D R L U L B' L U D' B D R' B' R' F' D B R  ( 24q*)   //C1{C2(a)}
U U R U U L D B L' B R' D F' L D' R' B' U F B' U' R' B D'  ( 24q*)   //C1{Cs(a)}
U U R U L U R' F L D L F' R' U' B' L B R' L D B' L F' D'  ( 24q*)   //C1{Cs(b)}
```
So it seems to be really difficult to find another 26q*.

### Random positions in Cube Explorer

The random generator of Cube Explorer generates every possible cube with the same probability using the Rnd() function. Concerning the distribution it might be better to run a coset-explorer on some random cosets. I finished writing a coset-explorer for the <U,D,R2,F2,L2,B2> subgroup (only the even permutations of corners/edges) which has 9,754,214,400 elements two days ago and ran it for the coset which contains the known 26q* position.
I do not know if Tom already did this computation (maybe even for the twice as large coset without the even-permutation-restriction). It is still running in depth 22, the results so far:
```depth 12          11,152
depth 14         762,312
depth 16      23,104,558
depth 18     665,649,794
depth 20   7,677,782,428
```
Of the remaining elements all but about 800 already are solved in 22 moves. I wonder how many elements are left if depth 22 has completed in a few days.

### Compiles on Mac OS

I downloaded the source code and was able to compile it under the Macintosh Xcode environment with no problems. It works great, good job.

### Speed?

Have you compared this on random positions with my solver?
Maybe we should do a bake-off. :-)

Mine does require a bit more memory (646M) but it's pretty old.

http://tomas.rokicki.com/rubsolv163.c

-tom

### Speed?

Would be interesting to compare. But I cannot compile your source with gcc, seems to need some more includes maybe, because gcc does not understand memcpy, memset, strlen. Nor do I know your input format. Seems easier if *you* run both programs with a few random instances...

### comparison with Reid's solver

I thought I would compare with Mike Reid's optimal solver program (compiled for QTM). I compiled using Visual C++.NET (2003). I used a random scramble that turned out to be 21q*. Both programs reported the same 13 optimal solutions. Note, I did not compile Herbert's program, but used the Windows executable he provided. Computer: 2.4GHz P4, 533MHz FSB. I also compare stats for the search at depth 19. Herbert's program needed to generate less than 10% the number of nodes than Mike Reid's program.

```Mike Reid's optimal solver program (compiled for QTM):
31h 0m
depth 19q completed  (  1,954,922,425 nodes,         266,692 tests)

Herbert Kociemba's QTM optimal solver program:
4h 52m
depth 19 completed,      148129725 nodes,         269352 tests
```

I think I have Tom's program successfully built and figured out how to run it. I'll try the same position with it.

### Speed of Tom's vs. Herbert's programs

I've now run Tom's program. I measured a time of 1h 57m for the same position I used for the other programs. However, the program reported it took only 4999 seconds (1h 23m 19s). Excellent work!

The reason my measured time was longer is that it included the time to generate the pruning table. I needed to regenerate the pruning table instead of reading it from a file, because the program was using "w" instead of "wb" for the fopen call to create the file. On UNIX, that may work fine, but it does not work on a Windows computer for creating a binary file. (Similarly, fopen for reading the file should use "rb".)

So Tom's program took 1h 23m while Herbert's took 4h 52m to search for all optimal solutions to the test case I used (about 3.5 times faster). Tom's program reported 7,664,266,323 evals, while Herbert's program reported 13,321,016,290 nodes and 26,051,386 tests for the depth 21 search.

### Cool beans! Some notes abo

Cool beans!

1. It works for halfturn or quarter turn; modify the first macro definition (#define HALFTURN or #undef HALFTURN).

2. I really should write up some documentation, a makefile, and perhaps fix the -Wall output.

3. The -a option says give me all solutions; the -s option means analyze the position for symmetry before solving and then only print out representative solutions.

4. You can either give the "position" on the command line, or through stdin; if through stdin, you can give many positions.

5. The input syntax is a sequence of [UFRDBL][+-123']? *moves*. I do not read positions yet. [Although I do have a small program that takes a position and returns a "stupid" long sequence; I should integrate that.]

6. The program has some novel features; I should write them up some time. I solve based on a pruning table that's constructed from the group of cubies on one *face* (four corners and four edges), and I apply this up to six times.

### Nice work! I'm really not sur

Nice work! I'm really not surprised that Tom's solver is faster because he always pulls some clever idea out of his hat. It would be nice if we could get some more detailed description on the algorithm.