# What is the maximum "minimum number of steps" needed to solve a rubiks cube?

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?

• Side note: This is often referred to as God's Number. May 14, 2014 at 21:46
• May 14, 2014 at 21:52

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.

• "Every configuration" was tried? seriously? May 14, 2014 at 21:49
• @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.
– user20
May 14, 2014 at 21:50
• 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). Jun 13, 2014 at 17:39

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.

• Do you know of any metrics which count a quarter-turn or half-turn "slice" as a move? Jun 11, 2014 at 23:20
• 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). Jun 13, 2014 at 17:20
• 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. Jun 13, 2014 at 17:49

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