God's Algorithm

From Speedsolving.com Wiki

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

WCA Puzzles

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]
6x6x6 OBTM 75 [16]
7x7x7 OBTM 99 [17]
Clock 12 DDUU u d6 DUDU u5' d4 UDUD u2' d5 UUDD u d6 UDDU u d UUDU u2 DUUU u2 [18], [19]
Megaminx HTM 48 194 [20], [21]
QTM 59 twsearch -q -C megaminx.tws, [22]
Pyraminx 11 (15 with tips) U R U R' U L' R' L' U' L B' u l r b [23]
Skewb 11 U L U' R' U B' U L R' U B [24]
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) [25]
FTM 31 [26]

Big Cubes

Puzzle Metric Lower Bound Source
8x8x8 OBTM 128 [27]
9x9x9 OBTM 158 [28]
10x10x10 OBTM 193 [29]
11x11x11 OBTM 229 [30]
12x12x12 OBTM 270 [31]
13x13x13 OBTM 312 [32]
14x14x14 OBTM 359 [33]
15x15x15 OBTM 406 [34]
16x16x16 OBTM 458 [35]
17x17x17 OBTM 511 [36]
18x18x18 OBTM 568 [37]
19x19x19 OBTM 626 [38]
20x20x20 OBTM 690 [39]
21x21x21 OBTM 753
22x22x22 OBTM 821
30x30x30 OBTM 1452
33x33x33 OBTM 1729
40x40x40 OBTM 2465
50x50x50 OBTM 3720
60x60x60 OBTM 5209
70x70x70 OBTM 6926
80x80x80 OBTM 8869
90x90x90 OBTM 11033
100x100x100 OBTM 13414
111x111x111 OBTM 16281
121x121x121 OBTM 19112
128x128x128 OBTM 21220
150x150x150 OBTM 28506
200x200x200 OBTM 48741
256x256x256 OBTM 77309
500x500x500 OBTM 271273
1000x1000x1000 OBTM 1001447
10000x10000x10000 OBTM 79634546
Puzzle Metric Lower Bound Upper Bound Conjectured Value Source
NxNxN, N<=1000 OBTM N^2
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) [40]

Subsets/alternate generating sets

Puzzle Subset Metric Lower Bound Upper Bound Conjectured Value State Realizing Lower Bound Source
2x2x2 <U,R> HTM 14 U R U' R' U R' U R' U2 R U2 R' U2 R2
QTM 17 U R U R' U' R U' R2 U R' U R' U2 R U'
3x3x3 <U,R> HTM 20 U R U R U R2 U2 R2 U2 R2 U' R U R U' R2 U2 R2 U2 R2
QTM 25 U R U R' U R' U' R U R' U' R2 U R' U' R2 U R U' R U' R U
<U,F,R> HTM 21 21 U R F2 R U2 F2 U' F' R U F U R' F R2 U F R U2 R F' [41]
<U,F2,R> HTM 21 U R U2 R U R' U2 R2 F2 R2 U R F2 R U2 R F2 R' U F2 R' [42]
<U,L,R> HTM 24 U L U' L2 R' U R U R2 U2 L' U2 L U R U' R2 U R2 U2 L R2 U' L'
<U2,L,R2> HTM 34 U2 L U2 L U2 L U2 L2 U2 L' R2 U2 L U2 L U2 L' R2 U2 L2 U2 L U2 L U2 L U2 L U2 L2 R2 U2 L R2
<U,L,F,R,B> HTM 23 F U F' L B2 F2 R2 B' U' R2 L' B2 R B' F2 U' R' F R' B2 L2 F2 R
<U,L,F2,R,B2,D> HTM 20 D2 L D2 F2 D R' D' R' L2 B2 R2 U2 D R2 L D' L' D F2 B2
<U,M> STM 20 U M U M U M U2 M' U2 M U M' U' M U' M' U' M U' M2
SQTM 23 U M U M U M U M U' M U M' U M U M' U M U' M' U2 M
<U,r> HTM 30 U r U r U' r2 U' r2 U2 r U r U r U2 r U2 r U2 r2 U2 r2 U2 r U2 r U2 r' U2 r2 [43]
QTM 38 r2 U' r U r' U' r' U r2 U r U r U r U r' U r U2 r U' r2 U2 r U2 r' U2 r' U2 [44]
<U,R,r> HTM 22 U2 R2 U R2 U r' U' r U' r' U2 R2 U r U R U2 r U R' U r2
<u,r> HTM 36 u r u r u2 r u' r u' r2 u' r u r2 u r u r u' r2 u2 r' u' r' u' r2 u' r u r2 u2 r u2 r u2 r2
<u,f,r> HTM 27 u2 f u r f' u2 r u2 f' r2 u r f u' r2 f r2 u' f2 r f u r' f2 u f2 r'
<U,L,F,R,B,D>, EO solved on all axes HTM 20 U F R2 D' F' L2 U F' B' U F' B' U L2 B' D' F R2 U F' [45]
4x4x4 <U,2R> STM 28 2R2 U2 2R U2 2R2 U 2R' U2 2R' U2 2R U 2R' U' 2R2 U' 2R' U2 2R U' 2R U2 2R U 2R U' 2R' U' [46]
SQTM 35 U' 2R' U2 2R U' 2R' U2 2R U2 2R' U' 2R' U 2R' U' 2R' U 2R U 2R' U 2R U' 2R U 2R' U2 2R' U' 2R' U' [47]
<U,r> OBTM 49 r U2 r U r' U' r2 U' r' U2 r2 U2 r U' r' U' r' U2 r' U r U' r' U r U2 r U r' U r' U r2 U2 r U' r2 U2 r U r U r' U2 r U' r U2 r'
OBQTM 62 r U2 r U r' U' r2 U' r' U2 r2 U2 r U' r' U' r' U2 r' U r U' r' U r U2 r U r' U r' U r2 U2 r U' r2 U2 r U r U r' U2 r U' r U2 r'
Megaminx <U,R> HTM 26 U R U' R2' U R U2' R2' U2' R' U' R U' R2 U R' U2' R' U2' R' U R2' U R2 U2 R' [48]

Steps/generation reduction

Puzzle Subset Metric Lower Bound Upper Bound Conjectured Value State Realizing Lower Bound Source
2x2x2 Face HTM 5 [49]
Guimond Step 1 HTM 3 [50]
Guimond Step 1 & 2 (Reducing to <U, R2, F2>) HTM 6 [51]
3x3x3 Cross HTM 8 [52]
First Block (fixed) HTM 9 [53]
EO HTM 7 F D L U B R' F
EOLine HTM 9 B' R F' D' L' U' B' R' D' [54]
EOCross HTM 10 B D2 R F U B D2 R F D [55]

Minxes

Puzzle Metric Lower Bound Upper Bound Conjectured Value State Realizing Lower Bound Source
Kilominx HTM 18 31 [56]
QTM 22 42 [57]
Master Kilominx OBTM 94 [58]
Gigaminx OBTM 152 [59]
Elite Kilominx OBTM 217 [60]
Teraminx OBTM 299 [61]
Pyraminx Crystal HTM 41 [62]
QTM 50 [63]

Cuboids

Puzzle Metric Lower Bound Upper Bound Conjectured Value State Realizing Lower Bound Source
1x2x2 3 R U R
1x2x3 6 R U R U R U
1x3x3 HTM 8 U L U R L U L D [64]
2x2x3 HTM 14 U R2 U R2 U2 R2 F2 U F2 D2 R2 U R2 D [65]
QTM 15 U R2 U R2 U' R2 F2 U' R2 U' R2 U F2 U' R2 [66]
2x3x3 HTM 18 U R2 U F2 U2 R2 U' B2 L2 U2 L2 U' L2 F2 U' L2 F2 L2 [67]
QTM 19 U R2 U R2 U2 F2 U' F2 L2 B2 R2 D L2 U2 F2 U' R2 [68]

Sliding Puzzles

Puzzle Metric Lower Bound Upper Bound Conjectured Value State Realizing Lower Bound Source
2x2 6 R D L U R D [69]
3x2 STM 21 R2 D L U L D R2 U L D L U R2 D L U L D [70]
4x2 STM 36 R D R U R D L U L D R U R D L3 U R2 D L2 U R3 D L3 U R3 D [71]
5x2 STM 55 R2 D L U R2 D L3 U R3 D R U L D L3 U R3 D R U L D L2 U R3 D L4 U R2 D L2 U R4 D [72]
6x2 STM 80 R2 D L U R D R2 U L2 D L2 U R2 D R3 U L3 D R3 U L2 D L3 U R3 D R2 U L2 D L3 U R4 D L4 U R5 D L5 U R5 D [73]
7x2 STM 108 D R U R2 D R U R2 D L5 U L D R U R5 D L5 U L D R U R4 D L5 U R6 D L6 U R6 D L5 U R5 D L6 U R2 D L U R3 D L4 U R6 [74]
8x2 STM 140 D R3 U L2 D L U R D R5 U L5 D R5 U L4 D L2 U R2 D R5 U L5 D R5 U L4 D R4 U L3 D L4 U R4 D R3 U L3 D L4 U R4 D L4 U R5 D L5 U R6 D L6 U R7 D [75]
3x3 STM 31 D2 R2 U2 L2 D R U L D2 R U R D L U R U L2 D2 R U2 L D [76]
4x3 STM 53 D R D R U2 L2 D R D L U R2 D L2 U R3 D L2 U R2 U L3 D R3 U L3 D R2 U L D2 L U2 R3 [77]
5x3 STM 84 D R4 U L4 D R2 U L D2 R U L D L U R3 D L2 U R3 D L4 U R U L D R4 D L4 U R3 U L2 D R2 U R D L2 U R D L D L2 U R D L U2 R4 [78]
4x4 STM 80 D R2 D2 L U L U R U R2 D L2 D R U2 R D2 L D R U L U L D R D L2 U R D L U3 R D L U R3 D L D L U2 R D3 L U3 R2 D L D2 L U L U2 R3 D3 [79]
5x5 STM 152 182 [80]
6x6 STM 230 382
7x7 STM 352 693
Puzzle Metric Lower Bound Upper Bound Conjectured Value State Realizing Lower Bound Source
Nx2 STM 2N^2 - N 2N^2 + O(N log(N)) 180 degree rotation
NxN STM N^3 - 2N + 2 - (N if N is odd, 0 otherwise) 5N^3 (4/3 + o(1))N^3 180 degree rotation

Circle Puzzles

Puzzle Metric Lower Bound Upper Bound Conjectured Value State Realizing Lower Bound Source
Eliac HTM 71 71 R2 L2 R2 L R2 L R2 L' R2 L2 R2 L R2 L' R2 L' R2 L' R2 L2 R2 L R2 L2 R2 L' R2 L R2 L' R2 L2 R2 L2 R2 L R2 L' R2 L2 R2 L R2 L2 R2 L R2 L' R2 L2 R2 L R2 L' R2 L2 R2 L' R2 L2 R2 L2 R2 L' R2 L2 R2 L R2 L' R2 [81]
QTM 80 80 R2 L R2 L' R2 L' R2 L R2 L2 R2 L' R2 L R2 L' R2 L R2 L2 R2 L2 R2 L2 R2 L2 R2 L' R2 L' R2 L2 R2 L R2 L2 R2 L' R2 L R2 L2 R2 L2 R2 L' R2 L2 R2 L' R2 L2 R2 L' R2 L2 R2 L R2 L R2 L' R2 L' R2 L' R2 L' [82]
Rashkey 1 HTM 12 [83]
QTM 15 [84]
Rashkey 2 HTM 19 [85]
QTM 23 [86]
Rashkey 3 HTM 26 L' R2 L2 R' L2 R2 L R L R' L' R' L2 R L' R' L R' L R' L' R L' R' L' R' [87]
QTM 31 L' R2 L2 R' L2 R2 L R L R' L' R' L2 R L' R' L R' L R' L' R L' R' L' R' [88]

Other

Puzzle Metric Lower Bound Upper Bound Conjectured Value State Realizing Lower Bound Source
3x3x3 Supercube HTM 24 24 U F U L D B2 R2 D2 L D2 L D2 B2 F U2 R' B U' R2 B L' D' U' R' [89]
QTM 28 28 R B' U2 R B D L B' R D' L F R2 D' F U R' B' U R' U D' R' F' U' F [90]
3x3x3 2 color cube (U,F,B / L,R,D faces) HTM 13 F' D2 R F2 U D' B' R' F' D F2 U' L' [91]
3x3x3 2 color cube (U,F,R / L,B,D faces) HTM 13 U L2 U2 B F R' D2 B2 L U2 R2 B2 L' [92]
3x3x3 3 color cube (opposite faces the same color) HTM 15 U F R2 B U' R F U2 D F R2 F D' B R [93]
QTM 17 U F2 B R B U' F B L U' F' L' B R' F D [94]
STM 14 U B L S R' U D2 R B' F2 M' F' U' R' [95]
Redi Cube 19 [96]
Master Pyraminx OBTM 20 26 20 Uw Rw Lw Bw' L R' Rw Bw U' Rw Uw' B' L' Uw' R' U' Rw' B' L' Bw [97]
Gear Cube HTM 6 [98]
QTM 12 [99]
Gear Cube Extreme HTM 17 25 17 [100]
Rubik's Ufo FTM 14 [101]
6thTM 16 [102]
Face-Turning Octahedron 21 [103]

External links

Retrieved from "https://www.speedsolving.com/wiki/index.php?title=God%27s_Algorithm&oldid=55075"