# God's Algorithm

(Redirected from God's Number)

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 
QTM 14 U R U F' R' F R U F' R F U R' F 
3x3x3 HTM 20 U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2 
QTM 26 U2 F U2 R' L F2 U F' B' R L U2 R U D' R L' D R' L' D2 
STM 18 20 18 D' M B2 R' E2 R' S2 R U S U R2 D F2 D S' U' B' x' , 
ATM 16 20 16 R2 U' (F2 B') (U D') F' R' D B D' R' B U2 R' U2 F' R2 
4x4x4 OBTM 35 55 , 
SSTM 32 53 , 
BTM 29 53 , 
5x5x5 OBTM 52 130 , 
6x6x6 OBTM 75 
7x7x7 OBTM 99 
Clock 12 DDUU u d6 DUDU u5' d4 UDUD u2' d5 UUDD u d6 UDDU u d UUDU u2 DUUU u2 , 
Megaminx HTM 48 194 , 
QTM 70 
Pyraminx 11 (15 with tips) U R U R' U L' R' L' U' L B' u l r b 
Skewb 11 U L U' R' U B' U L R' U B 
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) 
FTM 31 

#### Big Cubes

Puzzle Metric Lower Bound Source
8x8x8 OBTM 128 
9x9x9 OBTM 158 
10x10x10 OBTM 193 
11x11x11 OBTM 229 
12x12x12 OBTM 270 
13x13x13 OBTM 312 
14x14x14 OBTM 359 
15x15x15 OBTM 406 
16x16x16 OBTM 458 
17x17x17 OBTM 511 
18x18x18 OBTM 568 
19x19x19 OBTM 626 
20x20x20 OBTM 690 
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) 

#### Subsets

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' 
<U,M> STM 20 U M U M U M U2 M' U2 M U M' U' M U' M' U' M U' M2
<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'
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' 
<U,r> OBTM 46

#### Minxes

Puzzle Metric Lower Bound Upper Bound Conjectured Value State Realizing Lower Bound Source
Kilominx HTM 18 31 
QTM 22 42 
Master Kilominx OBTM 94 
Gigaminx OBTM 152 
Elite Kilominx OBTM 217 
Teraminx OBTM 299 
Pyraminx Crystal HTM 41 
QTM 50 

#### 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 
2x2x3 HTM 14 U R2 U R2 U2 R2 F2 U F2 D2 R2 U R2 D 
QTM 15 U R2 U R2 U' R2 F2 U' R2 U' R2 U F2 U' R2 
2x3x3 HTM 18 U R2 U F2 U2 R2 U' B2 L2 U2 L2 U' L2 F2 U' L2 F2 L2 
QTM 19 U R2 U R2 U2 F2 U' F2 L2 B2 R2 D L2 U2 F2 U' R2 

#### Sliding Puzzles

Puzzle Metric Lower Bound Upper Bound Conjectured Value State Realizing Lower Bound Source
2x2 6 R D L U R D 
3x2 STM 21 R2 D L U L D R2 U L D L U R2 D L U L D 
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 
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 
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 
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 
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 
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 
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 
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 
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 
5x5 STM 152 182 
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 
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' 
Rashkey 1 HTM 12 
QTM 15 
Rashkey 2 HTM 19 
QTM 23 
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' 
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' 

#### Other

Puzzle Metric Lower Bound Upper Bound Conjectured Value State Realizing Lower Bound Source
Redi Cube 19 
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 
Gear Cube HTM 6 
QTM 12 
Gear Cube Extreme HTM 17 25 17 
Rubik's Ufo FTM 14 
6thTM 16 
Face-Turning Octahedron 21