
cube files
Indexed Cube Lovers Archive
![]() |
cube archivesGAP filesBlogs
Forum topicsActive forum topics:New forum topics:User loginNavigation |
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. |
Browse archives
Pollwww.olympicube.com need cube lovers opinion on which cube to produce first olympic cube 6a 83% olympic cube 6b 17% Total votes: 23 Syndicate |