Home »

Twenty-Five Moves Suffice

Submitted by rokicki on Thu, 03/20/2008 - 14:26.
On March the 3rd I finally finished the last coset required to prove that 25 moves suffice.

I have finally finished a draft version of a paper detailing the technique and result:

http://tomas.rokicki.com/rubik25.pdf

The technique uses the coset solver I have described previously here (over the past two years)
but I have also made it faster, and also gotten a new machine that is faster and has more memory to run these cosets more quickly.

In the end, it required about 4,000 cosets to be solved to prove a bound of 25.
By solved, I mean an upper bound on the largest distance in that coset was found;
this can be done much more quickly than actually computing the exact distance for a
coset.

I think proving a bound of 24 is well within reach.
» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

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

Congratulations

Submitted by mdlazreg on Mon, 03/31/2008 - 17:49.
Congratulations Tom.

Two questions:

1) This H-cosets approach, does it work for QTM? I believe the current proven upper bound for QTM is 34. Any chance to lower this limit using your approach?

2) Is there a worst case analysis for how long it would take for an H-coset calcucation to complete?

If I understood well your approach, you simply calculate a new position and look it up in a big table if this is the first time it appears. The H-coset calculation is then complete when all positions appeared at least once... My fear is that they are certain H-cosets for which this approach will take forever...
» login or register to post comments

QTM

Submitted by rokicki on Mon, 03/31/2008 - 23:30.
I haven't given it too much thought. The general approach should work for QTM, but I'm not sure if it will be as effective as it is for HTM. One of the reasons it works fairly well for HTM is that so many of the moves (10 of the 18) are in the subgroup; for QTM, only 4 of 12 moves are in the subgroup, so you don't gain as much.

An upper bound on how long a coset would take to complete is, in the end, pretty bad; right now it's on the order of 13.3^24 give or take a few orders of magnitude. Well, it's not that bad if you stopped the search at depth 16, as I am, but then you're not guaranteed to prove a bound of 20 like you need to. So the overall approach definitely depends at least to a certain extent on just empirical extrapolations.

The approach is guaranteed to terminate (I'm not sure if you mean forever *literally* or *pragmatically*) since every position within H is reachable from every other in at most 18 moves, so as long as your initial search depth is at least as long as the distance to solved in R, it will *terminate*. It just might (possibly, but highly doubtfully) terminate out at 24 or something.

There are H cosets for which using a search termination of 16 will take a while, but not forever; for these, using a smaller search termination will almost certainly suffice to prove 20.

Mostly I'm interested in two things: lowering the upper bound on the diameter, and finding distance-20 positions (and a 21 if one exists, which is looking increasingly unlikely). So I'll probably be spending some time on these things.
» login or register to post comments

Congratulations

Submitted by Jerry Bryan on Mon, 03/24/2008 - 08:52.
I would like to offer congratulations in two respects. First, what you have accomplished is a marvelous piece of work. Second, I love the clarity and readability of your paper.
» login or register to post comments

(Blush)

Submitted by rokicki on Mon, 03/24/2008 - 11:58.
That is high praise indeed; thank you! This forum really helped inspire me, by the way; I am very happy it has been around these past few years.
» login or register to post comments