• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

God's number proven at 20

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
Before you guys start on the 4x4x4 and 5x5x5 I'll guess... 30 and 42.

Without using slice moves on the 4x4, and allowing only Rw/Uw/Fw (since Lw/Dw/Bw are equivalent), at least 34 moves are required to be able to get to every position (that is, to have at least as many possible scrambles as there are positions ignoring cube rotation).

Similarly, but allowing all six double-layer turns, at least 50 moves on a 5x5 are required to be able to get to every position.

(If you're interested, you need at least 73 moves for 6x6 and 95 for 7x7, by the same technique.)
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
Before you guys start on the 4x4x4 and 5x5x5 I'll guess... 30 and 42.

Without using slice moves on the 4x4, and allowing only Rw/Uw/Fw (since Lw/Dw/Bw are equivalent), at least 34 moves are required to be able to get to every position (that is, to have at least as many possible scrambles as there are positions ignoring cube rotation).

Similarly, but allowing all six double-layer turns, at least 50 moves on a 5x5 are required to be able to get to every position.

(If you're interested, you need at least 73 moves for 6x6 and 95 for 7x7, by the same technique.)

Well, first you need to define what you mean by a "move."

Dan Hoey proved that some 4x4x4 positions require at least 37 single-layer quarter-turns, or at least 41 quarter-twists (which some people now call face quarter-turn metric). I think simple lower bounds for half-turn metrics are 29 for block turns (moving any contiguous set of parallel layers with respect to the rest of the cube), and 32 for single-layer turns. qqwref indicated 34 twists (face turns) is a lower bound.

For upper bounds (4x4x4 half-turn metrics), I have proven 67 block turns, 77 single-layer turns, or 82 twists. (The nested subgroups I chose for my analysis wasn't particularly suited for getting a good twist metric upper bound, so that's why the twist turn number is rather high.)

As with the 3x3x3, the actual God's numbers are expected to be much closer to the known lower bounds.
 

brunson

Member
Joined
Feb 17, 2008
Messages
1,119
Location
Westminster, CO
WCA
2008BRUN01
New FMC goal for everyone... get a sub 20 official solution :p
Cool... 20 moves for any case...
"Distance-20 positions are both rare and plentiful; they are rarer than one in a billion positions, yet there are probably more than one hundred million such positions."
Haha, loved this sentence.
And what is the average required amount of moves? I realise 18 moves is the most common, but is 15-16 about average?
Coool :D

We should start scoring FMC like par in golf, you don't get a 23, you get a 3 over. :)

Edit: How confident are we that Thistlewait/Kociemba generates the optimal solution? If we're certain then we would score plus/minus away from optimal.
 
Last edited:

Lars Petrus

Member
Joined
Mar 22, 2009
Messages
67
WCA
1982PETR01
I really don't mean to be a party pooper, but to be precise:

Unless I've missed something this is so far only a claim of a proof, right? I certainly haven't seen an actual proof that I can verify or falsify.

I don't for a second believe that the authors are making this up, though that does occasionally happen even among very reputable scientists.

A more realistic concern is that there could be a subtle bug in the code, or that something flaky happened in one of the 55 million separate runs.

Proofs like these are tricky since it's very hard to prove that a non trivial piece of code does what it's intended to do. I don't know how science in general handles this issue.
 

uberCuber

Member
Joined
Jun 24, 2010
Messages
3,921
Location
Tucson, Arizona, USA
WCA
2011THOM01
I really don't mean to be a party pooper, but to be precise:

Unless I've missed something this is so far only a claim of a proof, right? I certainly haven't seen an actual proof that I can verify or falsify.

I don't for a second believe that the authors are making this up, though that does occasionally happen even among very reputable scientists.

A more realistic concern is that there could be a subtle bug in the code, or that something flaky happened in one of the 55 million separate runs.

Proofs like these are tricky since it's very hard to prove that a non trivial piece of code does what it's intended to do. I don't know how science in general handles this issue.

this is a big reason why i am disappointed that it was proved (possibly?) by brute force rather than mathematically
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
We should start scoring FMC like par in golf, you don't get a 23, you get a 3 over. :)

Edit: How confident are we that Thistlewait/Kociemba generates the optimal solution? If we're certain then we would score plus/minus away from optimal.
But it is impossible to beat the optimal solution.

Unless I've missed something this is so far only a claim of a proof, right? I certainly haven't seen an actual proof that I can verify or falsify.

[...]

A more realistic concern is that there could be a subtle bug in the code, or that something flaky happened in one of the 55 million separate runs.
Good point. This is not a mathematically rigorous proof but rather a series of computations that - *if* the code and assumptions are all correct - solves the problem. In this way it is similar to the 4-color theorem proof. I would be interested in seeing a proof-like analysis that the code is correct.
 
T

Tord

Guest
Excellent!

I, too, would like an uniformly mathematical proof. Nevertheless, I embrace progress. Huzzah for google!

On a side note; A small notice in Aftenposten (norwegian newspaper), dated 11/8-10, reported this discovery. The 75 words of the "article" said little, but the online article said more.
If interested, one might google translate it, only to discover that the article contains a small amount of content regarding the actual solution.
 
Joined
May 9, 2010
Messages
382
Location
Michigan

rokicki

Member
Joined
Oct 31, 2008
Messages
301
Computer proof

Yes, this is a computer proof. We will be releasing code, but not for a while.

We too were concerned about things like hardware reliability and bugs. We did as much as we could to not be tripped up by this. In particular:

1. Almost every single position was actually solved *twice*, not just once. Thus, an error in a single run would almost certainly not affect the overall result. The subset of positions not checked twice is small (but, alas, not small enough to easily check in full). I may yet attempt to check that subset exhaustively, at which point we can say for certain that every position has been checked twice.

2. Along the way we generated numbers that reproduced earlier results by other researchers, including the count of positions at distances 0 through 14, and also generated a *new* result, the count of positions at 15, which we hope to have verified soon by another researcher running code in Germany. Generation of these numbers required every single one of the 55,882,296 runs to be correct (at least up to that point).

3. We used a single program to do the bulk of the calculations; this is a much faster version of the earlier programs used for 22 and 23 and the other bounds. We have compared the output of this program with the output of the earlier versions, and with the output of an independent implementation (sharing no code), and with the output of a much simpler version that is also much slower, and found no disagreements.

4. It turns out, every single position has a distance-20 solution that can be found reasonably easily, except about 100K positions. We solved this set of positions numerous times. (We *wanted* there to be a 21).

5. The code embeds distinct methods for computing the same result (to a certain extent); we compared results with and without the "fast" code for a large set of cosets.

6. We include all sorts of checksumming of the output files, verification of the pruning tables after each run (to make sure no bits flipped), and many other defensive programming techniques to guard against errors.

7. The technique and results from it have been published over the past five years on Cubelovers, and we have had independent confirmation of many of the results by separate implementations. The code originated back in 2005, and every version of the program has been extensively checked against prior versions and against the results generated by the prior versions over this time period.

We would not be publishing this result if we were not certain of it.

I would love for there to be a nice concise mathematical proof. But so far no one has been able to come up with it. The technique we use is straightforward, the optimizations are straightforward, and we have checked the result extensively.
 

cmhardw

Premium Member
Joined
Apr 5, 2006
Messages
4,115
Location
Orlando, Florida
WCA
2003HARD01
YouTube
Visit Channel

It has taken 15 years to get to this point, but it is now clear that every possible scrambled arrangement of the Rubik's cube can be solved in a maximum of 20 moves – and you don't even have to take the stickers off.

I literally groaned out loud. Why?! In an article written for a scientific audience? :fp

Chris
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
Because appealing to people's stupidity is still cool?

I'd like to see someone find a way to solve in less than 20 remove-and-replace-a-sticker moves... don't people realize it's actually more difficult to deal with the stickers?
 

Lars Petrus

Member
Joined
Mar 22, 2009
Messages
67
WCA
1982PETR01
Yes, this is a computer proof. We will be releasing code, but not for a while.

We too were concerned about things like hardware reliability and bugs. We did as much as we could to not be tripped up by this. In particular:

1. Almost every single position was actually solved *twice*, not just once. Thus, an error in a single run would almost certainly not affect the overall result. The subset of positions not checked twice is small (but, alas, not small enough to easily check in full). I may yet attempt to check that subset exhaustively, at which point we can say for certain that every position has been checked twice.

2. Along the way we generated numbers that reproduced earlier results by other researchers, including the count of positions at distances 0 through 14, and also generated a *new* result, the count of positions at 15, which we hope to have verified soon by another researcher running code in Germany. Generation of these numbers required every single one of the 55,882,296 runs to be correct (at least up to that point).

3. We used a single program to do the bulk of the calculations; this is a much faster version of the earlier programs used for 22 and 23 and the other bounds. We have compared the output of this program with the output of the earlier versions, and with the output of an independent implementation (sharing no code), and with the output of a much simpler version that is also much slower, and found no disagreements.

4. It turns out, every single position has a distance-20 solution that can be found reasonably easily, except about 100K positions. We solved this set of positions numerous times. (We *wanted* there to be a 21).

5. The code embeds distinct methods for computing the same result (to a certain extent); we compared results with and without the "fast" code for a large set of cosets.

6. We include all sorts of checksumming of the output files, verification of the pruning tables after each run (to make sure no bits flipped), and many other defensive programming techniques to guard against errors.

7. The technique and results from it have been published over the past five years on Cubelovers, and we have had independent confirmation of many of the results by separate implementations. The code originated back in 2005, and every version of the program has been extensively checked against prior versions and against the results generated by the prior versions over this time period.

We would not be publishing this result if we were not certain of it.

I would love for there to be a nice concise mathematical proof. But so far no one has been able to come up with it. The technique we use is straightforward, the optimizations are straightforward, and we have checked the result extensively.

Sounds good. I don't doubt it's correct.

If you're a science proof nerd, check out the Wikipedia article on computer assisted proofs. Perhaps this proof should be added to the example section?
 
Top