Independent proof of 26-move upper bound for half-turn metric

Starting over Thanksgiving break, I decided to let my H-coset solver
run on my personal machines on a bunch of the H cosets, starting with
the most symmetrical ones and moving down to the less symmetrical ones.
My H-coset solver uses the Kociemba two-phase algorithm, but for all
19B elements of an H-coset in parallel, rather than for a single cube
position. (It's just the Kociemba two-phase algorithm augmented with
a 19B-element bit table, roughly.)

As of today, I have completed 4,748 such cosets, using a depth of at
least 16 for phase 1 and proving that each element of most of these
cosets are solvable in 20 moves (some cosets had a worst-case element
of 21, some of 19, and exactly two so far had worst-case elements of
18.)

With this many cosets solved, it's a simple matter to show that every
H position can be solved in 26 or fewer moves simply by showing that
for every position in H, there is some solved coset such that the
distance to that solved coset, plus the distance of the worst-case
element of that coset, is 26 or less.

This does not yield a concise proof, because that list of cosets is
so long, but at least it is independent confirmation of 26. For
verification of the result, I can share the distributions of all the
cosets that can be independently verified by a completely separate
implementation of the parallel two-phase algorithm (I believe both
Herbert Kociemba and Silviu Radu have such solvers).

Solving these cosets took several CPU months (although most of my
CPUs are old 2.8GHz P4s, which are quite slow by today's Core 2
standards.) I remain optimistic that with some keen observations
of the form used in other distance proofs, and the solution of some
more H-cosets, we may be able to lower this bound down to 25.

Comment viewing options

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

Oops; typo

The second paragraph should say "it's a simple matter to show that
every cube position can be solved in 26 or fewer moves . . ."