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.

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.)

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.

New FMC goal for everyone... get a sub 20 official solution
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

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.

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.

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.

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.

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.

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.

Spoiler

If interested, one might google translate it, only to discover that the article contains a small amount of content regarding the actual solution.

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.

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.

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?

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.