Thomas09
Member
Faskinating.
Before you guys start on the 4x4x4 and 5x5x5 I'll guess... 30 and 42.
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.)
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
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.
But it is impossible to beat the optimal solution.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.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.
I don't know if this is old news for you guys, but it has now been proven that the rubiks cube can always be solved in 20 moves or less.
Sources:
Article
History of God's number
I don't know if this is old news for you guys, but it has now been proven that the rubiks cube can always be solved in 20 moves or less.
Sources:
Article
History of God's number
I don't know if this is old news for you guys, but it has now been proven that the rubiks cube can always be solved in 20 moves or less.
Sources:
Article
History of God's number
READ OP before you post reply!
I don't know if this is old news for you guys, but it has now been proven that the rubiks cube can always be solved in 20 moves or less.
Sources:
Article
History of God's number
READ OP before you post reply!
I think a mod merged the threads and this was origally a different thread.
it was in the new scientist
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.
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.