God's Algorithm
God's Algorithm is the name given to any algorithm which brings a puzzle from a scrambled state to the solved state in as few moves as possible. Such algorithms are more commonly referred to as optimal solutions. The term "God's Algorithm" may also be used to refer to a procedure for finding optimal solutions.
God's Number
God's Number for a puzzle is the greatest number of moves that a state can be from the solved state. Equivalently, it is the maximum length of an optimal solution, and the minimum number of moves such that every state can be solved in at most that number of moves.
If the puzzle has the structure of a group, then God's Number is also the largest number of moves required to move between any two states. In this case, God's Number may also be referred to as the diameter of the group. If the puzzle does not have a group structure, there may be pairs of states that are more than God's Number of moves apart.
God's Number has been known for small puzzles such as the 2x2x2 cube since the 1980s, and for the 3x3x3 cube since 2010, but remains unknown for most other puzzles.
Table of God's Numbers
| Puzzle | Metric | Lower Bound | Upper Bound | Conjectured Value | State Realizing Lower Bound | Source |
|---|---|---|---|---|---|---|
| 2x2x2 | HTM | 11 | R U' R2 U' F' R' U F2 R U' F | [1] | ||
| QTM | 14 | U R U F' R' F R U F' R F U R' F | [2] | |||
| 3x3x3 | HTM | 20 | U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2 | [3] | ||
| QTM | 26 | U2 F U2 R' L F2 U F' B' R L U2 R U D' R L' D R' L' D2 | [4] | |||
| STM | 18 | 20 | 18 | D' M B2 R' E2 R' S2 R U S U R2 D F2 D S' U' B' x' | [5], [6] | |
| ATM | 16 | 20 | 16 | R2 U' (F2 B') (U D') F' R' D B D' R' B U2 R' U2 F' R2 | [7] | |
| 4x4x4 | OBTM | 35 | 55 | [8], [9] | ||
| SSTM | 32 | 53 | [10], [11] | |||
| BTM | 29 | 53 | [12], [13] | |||
| 5x5x5 | OBTM | 52 | 130 | [14], [15] | ||
| NxNxN | OBTM | (1/4 log(24!/4!^6) + o(1)) N^2/log(N) | (c + o(1)) N^2/log(N) | (1/4 log(24!/4!^6) + o(1)) N^2/log(N) | [16] | |
| Clock | 12 | DDUU u d6 DUDU u5' d4 UDUD u2' d5 UUDD u d6 UDDU u d UUDU u2 DUUU u2 | [17], [18] | |||
| Megaminx | HTM | 48 | 194 | [19], [20] | ||
| QTM | 70 | [21] | ||||
| Pyraminx | 11 (15 with tips) | U R U R' U L' R' L' U' L B' u l r b | [22] | |||
| Skewb | 11 | U L U' R' U B' U L R' U B | [23] | |||
| Square-1 | Twist Metric | 13 | / (0,-3) / (0,-1) / (1,0) / (-4,-4) / (0,-5) / (0,-4) / (-5,2) / (-4,0) / (-5,-2) / (0,1) / (5,0) / (0,3) / (3,0) | [24] | ||
| FTM | 31 | [25] | ||||
