# 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.

## Contents

## 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 | 70 | [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

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,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' | [42] | ||

<U,r> | OBTM | 46 |

#### Minxes

Puzzle | Metric | Lower Bound | Upper Bound | Conjectured Value | State Realizing Lower Bound | Source |
---|---|---|---|---|---|---|

Kilominx | HTM | 18 | 31 | [43] | ||

QTM | 22 | 42 | [44] | |||

Master Kilominx | OBTM | 94 | [45] | |||

Gigaminx | OBTM | 152 | [46] | |||

Elite Kilominx | OBTM | 217 | [47] | |||

Teraminx | OBTM | 299 | [48] | |||

Pyraminx Crystal | HTM | 41 | [49] | |||

QTM | 50 | [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 | [51] | ||

2x2x3 | HTM | 14 | U R2 U R2 U2 R2 F2 U F2 D2 R2 U R2 D | [52] | ||

QTM | 15 | U R2 U R2 U' R2 F2 U' R2 U' R2 U F2 U' R2 | [53] | |||

2x3x3 | HTM | 18 | U R2 U F2 U2 R2 U' B2 L2 U2 L2 U' L2 F2 U' L2 F2 L2 | [54] | ||

QTM | 19 | U R2 U R2 U2 F2 U' F2 L2 B2 R2 D L2 U2 F2 U' R2 | [55] |

#### Sliding Puzzles

Puzzle | Metric | Lower Bound | Upper Bound | Conjectured Value | State Realizing Lower Bound | Source |
---|---|---|---|---|---|---|

2x2 | 6 | R D L U R D | [56] | |||

3x2 | STM | 21 | R2 D L U L D R2 U L D L U R2 D L U L D | [57] | ||

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 | [58] | ||

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 | [59] | ||

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 | [60] | ||

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 | [61] | ||

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 | [62] | ||

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 | [63] | ||

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 | [64] | ||

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 | [65] | ||

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 | [66] | ||

5x5 | STM | 152 | 182 | [67] | ||

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 | [68] | |

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' | [69] | ||

Rashkey 1 | HTM | 12 | [70] | |||

QTM | 15 | [71] | ||||

Rashkey 2 | HTM | 19 | [72] | |||

QTM | 23 | [73] | ||||

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' | [74] | ||

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' | [75] |

#### Other

Puzzle | Metric | Lower Bound | Upper Bound | Conjectured Value | State Realizing Lower Bound | Source |
---|---|---|---|---|---|---|

Redi Cube | 19 | [76] | ||||

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 | [77] |

Gear Cube | HTM | 6 | [78] | |||

QTM | 12 | [79] | ||||

Gear Cube Extreme | HTM | 17 | 25 | 17 | [80] | |

Rubik's Ufo | FTM | 14 | [81] | |||

6thTM | 16 | [82] | ||||

Face-Turning Octahedron | 21 | [83] |