27 QTM Moves Suffice

Every position of the Rubik's Cube can be solved in at most
27 quarter turns.

This work was supported in part by an allocation of computing time
from the Ohio Supercomputer Center. It was also supported by
computer time from Kent State University's College of Arts and
Sciences. In order to obtain this new result, 25,000 cosets of
the subgroup U,F2,R2,D,B2,L2 were solved to completion, and
34,000,000 cosets were solved to show a bound of 26. No new
positions at a distance of 26 or 25 were found in the solution
of all of these cosets.

Comment viewing options

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



Can we anticipate a determination of the diameter of the QTM before too long?

We have high hopes and excell

We have high hopes and excellent progress. I would expect a final
result by the end of the summer.

God's Number announced for QTM

On Aug. 3, Morley Davidson announced at the U.S. Nationals Rubik's Cube competition (at Liberty Science Center, Jersey City, New Jersey) that 26 has now been proven to be God's number for the quarter turn metric. Tom Rokicki appears to be on vacation, but I assume he will be posting a new thread about this soon.

Only 29 cpu-years for qtm 26

On http://www.cube20.org/qtm/, one can see that 26 is indeed the maximum number of quarter face turn. Note that http://www.cube20.org/ is about the number 20 for the face turn metric. Both web pages are more or less similar in structure.

But where the face turn metric required 35 years of computation, the quarter face turn metric only required 29 such years. This seems very strange to me, because the two phase algorithm with the indicated subgroup performs significantly less for the quarter turn metric. How can that be?

I thought Morley told me that

I thought Morley told me that they had found a more efficient set covering that used fewer cosets. That could possibly have allowed the the amount of time to be reduced. The 20f and 26q web pages indicate the same number of cosets were used, though. I am pretty sure they created the 26q page by editing a copy of the other page, so it's possible they may have forgotten to correct the number of cosets on the new page. Hopefully Tom or Morley will confirm if this was the case, or what other factors may have contributed to the reduction.

I'm also not sure if what they were calling a CPU year in 2010 is the same as what they are calling a CPU year in 2014.

Not better set covering I think

With set covering, they can improve the symmetry reduction factor of almost 16 to about 40. I think 48 is the theoretical maximum, so there is not much to win here.

No, the quarter face turn coset solver takes 17 seconds, and by careful reading, we see that the face turn coset solver takes 19.5 seconds. That does it.

But how on earth can the quarter face turn coset solver be faster than the face turn coset solver? Can the face turn coset solver of a few years ago be improved?

Ahh, I've missed these commen

Ahh, I've missed these comments; sorry!

The coset solver was almost exactly the same code, but the QTM behaves quite
differently than the HTM. For the HTM, the prepasses dominated performance;
for the QTM, the search phase dominated. We did make some improvements to
the search phase to make it faster and we will describe this soon (essentially we
stored paths to leaves directly in the pruning table to reduce lookup counts).

The "CPU years" *are* different; we used faster CPUs for the QTM baseline and
we will be sharing this information as well. The QTM actually took more net
CPU than the HTM (but overall it was comparable).

We did find a better set covering---but it was better by only the tiniest amount
(well under 1%) so we decided to minimize risk and use the existing proven set
covering (the new one was proven of course too but we still more comfortable
not changing it). In theory this gives us additional information on cross-checking
HTM vs QTM, potentially, if we wanted to go there.

We also did some work on finding distance-24+'s and I'll be writing that up soon

Feel free to ask any questions of course.