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

Submitted by rokicki on Thu, 12/06/2007 - 13:34.

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.

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.