15
$\begingroup$

If an algo X outputs the minimum "number of moves" (not the actual moves, just their count) to solve an input configuration, what's the maximum number X can output for any configuration?

$\endgroup$
12
$\begingroup$

The maximum number of positions a valid Rubik's cube configuration takes to solve is 20, and is called God's Number. No rigorous mathematical proof has been provided for the number; however, every configuration was tried. Cube20 gives an explanation of what they did, as well as provides source code for their project.

They achieved this through a few groups, discovered from other proofs of maximum move counts, which reduced the set of positions that actually needed to be tried significantly. They only needed to solve 55,882,296 positions as a result (they took quite a bit of advantage of symmetry).

However, without brute-force, this has only been mathematically proven for 22 moves.

$\endgroup$
  • $\begingroup$ "Every configuration" was tried? seriously? $\endgroup$ – kBisla May 14 '14 at 21:49
  • 4
    $\begingroup$ @Blue A lot of groups were discovered over the course of the project that significantly limited the number of positions that actually needed to be hard-solved. However, in essence, yes. $\endgroup$ – Aza May 14 '14 at 21:50
  • 3
    $\begingroup$ How is a proof with many cases not mathematical and rigorous? Compare the 1970s proof of the four-color theorem (Mathworld link). The formal write-up of the 20 move result was published in 2013 in the SIAM Journal of Discrete Mathematics (PDF here). $\endgroup$ – Brian Hopkins Jun 13 '14 at 17:39
4
$\begingroup$

It depends on what you count as a move. The "God's number is 20" result mentioned by earlier answerers is for the face turn metric, where a 180 rotation/half turn of a face counts as one move. (This blog entry by David Joyner gives a history of results toward this conclusion with a parallel human interest story on one of the primary researchers.)

In the quarter turn metric, a 180 rotation counts as two moves so that "God's number" is presumably higher. To date it is known to be at least 26 ("superflip plus fourspot", description here). Similar to the long-known examples requiring 20 turns in the FTM that were eventually shown (with lots of computer power) to be optimal, the suspicion is that 26 is God's number in the QTM.

$\endgroup$
  • $\begingroup$ Do you know of any metrics which count a quarter-turn or half-turn "slice" as a move? $\endgroup$ – supercat Jun 11 '14 at 23:20
  • $\begingroup$ The slice turn metric allows any quarter- or half-turn of a middle "slice" as one move. (There seems to be less interest in counting only slice quarter turns.) Since these allowed moves include the HTM moves, the upper bound here is 20. The conjecture is that God's number in this STM is 18 (see link). $\endgroup$ – Brian Hopkins Jun 13 '14 at 17:20
  • $\begingroup$ Interesting that it helps a tiny bit, but it's hard to tell how much. It makes sense that if a quarter-slice is one move a half-slice should also be one move, since a quarter-slice is less like a single-face quarter turn than would be a single-face half-turn it would seem illogical to count a quarter-slice as a one move but a single-face half turn as two, and even more illogical to count a single-face half-turn as one and quarter-slice as one, but a half-slice as two. $\endgroup$ – supercat Jun 13 '14 at 17:49
2
$\begingroup$

It's well known that the diameter of the Cayley graph for Rubik's cube positions is 20.

I think that's the question you were asking. If not, please edit your question to clarify.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.