Difference between revisions of "God's Algorithm"

From Speedsolving.com Wiki
(+ link to Wikipedia)
(→‎Other: 3x3 supercube)
 
(33 intermediate revisions by 4 users not shown)
Line 1: Line 1:
'''God's Algorithm''' is the optimal [[solve|solution]] from a puzzle state to another [[cube state|state]], commonly the [[solved cube state|solved state]]. The term is sometimes used to refer to the [[algorithm]] itself, or an algorithmic procedure that finds such a solution efficiently.
+
<seo title="God's Algorithm - Optimal solutions of the Rubik's Cube"/>
 +
 
 +
'''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 ==
'''God's Number''' is either used to refer to the diameter of the [[Rubik's Cube Group|group]] of the puzzle (the furthest distance two states can be from each other) or to the furthest distance any position can be from solved. God's Number has long been known for smaller puzzles, such as [[2x2x2]] and [[Pyraminx]], but for [[3x3x3]] it was unknown until July 2010 and it is still unknown for bigger cubes (like the [[4x4x4]]).
+
'''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 [[wikipedia:group|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 ====
 +
 
 +
{| class=wikitable
 +
|-
 +
! Puzzle
 +
! Metric
 +
! style="width:10%;" | Lower Bound
 +
! style="width:10%;" | Upper Bound
 +
! style="width:10%;" | Conjectured Value
 +
! State Realizing Lower Bound
 +
! Source
 +
|-
 +
| rowspan=2 | 2x2x2
 +
| HTM
 +
| colspan=3 style="text-align: center;" | 11
 +
| R U' R2 U' F' R' U F2 R U' F
 +
| [https://www.jaapsch.net/puzzles/cube2.htm]
 +
|-
 +
| QTM
 +
| colspan=3 style="text-align: center;" | 14
 +
| U R U F' R' F R U F' R F U R' F
 +
| [https://www.jaapsch.net/puzzles/cube2.htm]
 +
|-
 +
| rowspan=4 | 3x3x3
 +
| HTM
 +
| colspan=3 style="text-align: center;" | 20
 +
| U R2 F B R B2 R U2 L B2 R U' D' R2 F R' L B2 U2 F2
 +
| [http://cube20.org/]
 +
|-
 +
| QTM
 +
| colspan=3 style="text-align: center;" | 26
 +
| U2 F U2 R' L F2 U F' B' R L U2 R U D' R L' D R' L' D2
 +
| [http://cube20.org/qtm]
 +
|-
 +
| STM
 +
| style="text-align: center;" | 18
 +
| style="text-align: center;" | 20
 +
| style="text-align: center;" | 18
 +
| D' M B2 R' E2 R' S2 R U S U R2 D F2 D S' U' B' x'
 +
| [http://forum.cubeman.org/?q=node/view/200#comment-1612], [https://gist.github.com/rokicki/5163b0bc85bcdd8210eb4b8707fa1e30]
 +
|-
 +
| ATM
 +
| style="text-align: center;" | 16
 +
| style="text-align: center;" | 20
 +
| style="text-align: center;" | 16
 +
| R2 U' (F2 B') (U D') F' R' D B D' R' B U2 R' U2 F' R2
 +
| [http://forum.cubeman.org/?q=node/view/200#comment-3081]
 +
|-
 +
| rowspan=3 | 4x4x4
 +
| OBTM
 +
| style="text-align: center;" | 35
 +
| style="text-align: center;" | 55
 +
|
 +
|
 +
| [http://forum.cubeman.org/?q=node/view/236], [http://forum.cubeman.org/?q=node/view/541#comment-3006]
 +
|-
 +
| SSTM
 +
| style="text-align: center;" | 32
 +
| style="text-align: center;" | 53
 +
|
 +
|
 +
| [http://forum.cubeman.org/?q=node/view/236], [http://forum.cubeman.org/?q=node/view/541#comment-3009]
 +
|-
 +
| BTM
 +
| style="text-align: center;" | 29
 +
| style="text-align: center;" | 53
 +
|
 +
|
 +
| [http://forum.cubeman.org/?q=node/view/236], [http://forum.cubeman.org/?q=node/view/541]
 +
|-
 +
| 5x5x5
 +
| OBTM
 +
| style="text-align: center;" | 52
 +
| style="text-align: center;" | 130
 +
|
 +
|
 +
| [http://forum.cubeman.org/?q=node/view/236], [https://www.speedsolving.com/threads/5x5x5-obtm-upper-bound.61270/]
 +
|-
 +
| 6x6x6
 +
| OBTM
 +
| style="text-align: center;" | 75
 +
|
 +
|
 +
|
 +
| [http://forum.cubeman.org/?q=node/view/236]
 +
|-
 +
| 7x7x7
 +
| OBTM
 +
| style="text-align: center;" | 99
 +
|
 +
|
 +
|
 +
| [http://forum.cubeman.org/?q=node/view/236]
 +
|-
 +
| Clock
 +
|
 +
| colspan=3 style="text-align: center;" | 12
 +
| DDUU u d6 DUDU u5' d4 UDUD u2' d5 UUDD u d6 UDDU u d UUDU u2 DUUU u2
 +
| [https://www.speedsolving.com/threads/gods-number-for-clock-found.47822/], [http://cube20.org/clock/]
 +
|-
 +
| rowspan=2 | Megaminx
 +
| HTM
 +
| style="text-align: center;" | 48
 +
| style="text-align: center;" | 194
 +
|
 +
|
 +
| [https://www.speedsolving.com/threads/lower-bound-for-megaminx-in-htm-and-qtm.35724/#post-1190421], [http://forum.cubeman.org/?q=node/view/328#comment-2657]
 +
|-
 +
| QTM
 +
| style="text-align: center;" | 70
 +
|
 +
|
 +
|
 +
| [http://forum.cubeman.org/?q=node/view/328#comment-2653]
 +
|-
 +
| Pyraminx
 +
|
 +
| colspan=3 style="text-align: center;" | 11 (15 with tips)
 +
| U R U R' U L' R' L' U' L B' u l r b
 +
| [https://www.jaapsch.net/puzzles/pyraminx.htm]
 +
|-
 +
| Skewb
 +
|
 +
| colspan=3 style="text-align: center;" | 11
 +
| U L U' R' U B' U L R' U B
 +
| [https://www.jaapsch.net/puzzles/skewb.htm]
 +
|-
 +
| rowspan=2 | Square-1
 +
| Twist Metric
 +
| colspan=3 style="text-align: center;" | 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)
 +
| [http://forum.cubeman.org/?q=node/view/35]
 +
|-
 +
| FTM
 +
| colspan=3 style="text-align: center;" | 31
 +
|
 +
| [https://www.speedsolving.com/threads/square-one-can-be-solved-in-31-moves-in-face-turn-metric.67363/]
 +
|}
 +
 
 +
==== Big Cubes ====
 +
 
 +
{| class=wikitable style="width:100%;"
 +
|-
 +
! Puzzle
 +
! Metric
 +
! Lower Bound
 +
! Source
 +
|-
 +
| 8x8x8
 +
| OBTM
 +
| style="text-align: center;" | 128
 +
| [http://forum.cubeman.org/?q=node/view/236]
 +
|-
 +
| 9x9x9
 +
| OBTM
 +
| style="text-align: center;" | 158
 +
| [http://forum.cubeman.org/?q=node/view/236]
 +
|-
 +
| 10x10x10
 +
| OBTM
 +
| style="text-align: center;" | 193
 +
| [http://forum.cubeman.org/?q=node/view/236]
 +
|-
 +
| 11x11x11
 +
| OBTM
 +
| style="text-align: center;" | 229
 +
| [http://forum.cubeman.org/?q=node/view/236]
 +
|-
 +
| 12x12x12
 +
| OBTM
 +
| style="text-align: center;" | 270
 +
| [http://forum.cubeman.org/?q=node/view/236]
 +
|-
 +
| 13x13x13
 +
| OBTM
 +
| style="text-align: center;" | 312
 +
| [http://forum.cubeman.org/?q=node/view/236]
 +
|-
 +
| 14x14x14
 +
| OBTM
 +
| style="text-align: center;" | 359
 +
| [http://forum.cubeman.org/?q=node/view/236]
 +
|-
 +
| 15x15x15
 +
| OBTM
 +
| style="text-align: center;" | 406
 +
| [http://forum.cubeman.org/?q=node/view/236]
 +
|-
 +
| 16x16x16
 +
| OBTM
 +
| style="text-align: center;" | 458
 +
| [http://forum.cubeman.org/?q=node/view/236]
 +
|-
 +
| 17x17x17
 +
| OBTM
 +
| style="text-align: center;" | 511
 +
| [http://forum.cubeman.org/?q=node/view/236]
 +
|-
 +
| 18x18x18
 +
| OBTM
 +
| style="text-align: center;" | 568
 +
| [http://forum.cubeman.org/?q=node/view/236]
 +
|-
 +
| 19x19x19
 +
| OBTM
 +
| style="text-align: center;" | 626
 +
| [http://forum.cubeman.org/?q=node/view/236]
 +
|-
 +
| 20x20x20
 +
| OBTM
 +
| style="text-align: center;" | 690
 +
| [http://forum.cubeman.org/?q=node/view/236]
 +
|-
 +
| 21x21x21
 +
| OBTM
 +
| style="text-align: center;" | 753
 +
|
 +
|-
 +
| 22x22x22
 +
| OBTM
 +
| style="text-align: center;" | 821
 +
|
 +
|-
 +
| 30x30x30
 +
| OBTM
 +
| style="text-align: center;" | 1452
 +
|
 +
|-
 +
| 33x33x33
 +
| OBTM
 +
| style="text-align: center;" | 1729
 +
|
 +
|-
 +
| 40x40x40
 +
| OBTM
 +
| style="text-align: center;" | 2465
 +
|
 +
|-
 +
| 50x50x50
 +
| OBTM
 +
| style="text-align: center;" | 3720
 +
|
 +
|-
 +
| 60x60x60
 +
| OBTM
 +
| style="text-align: center;" | 5209
 +
|
 +
|-
 +
| 70x70x70
 +
| OBTM
 +
| style="text-align: center;" | 6926
 +
|
 +
|-
 +
| 80x80x80
 +
| OBTM
 +
| style="text-align: center;" | 8869
 +
|
 +
|-
 +
| 90x90x90
 +
| OBTM
 +
| style="text-align: center;" | 11033
 +
|
 +
|-
 +
| 100x100x100
 +
| OBTM
 +
| style="text-align: center;" | 13414
 +
|
 +
|-
 +
| 111x111x111
 +
| OBTM
 +
| style="text-align: center;" | 16281
 +
|
 +
|-
 +
| 121x121x121
 +
| OBTM
 +
| style="text-align: center;" | 19112
 +
|
 +
|-
 +
| 128x128x128
 +
| OBTM
 +
| style="text-align: center;" | 21220
 +
|
 +
|-
 +
| 150x150x150
 +
| OBTM
 +
| style="text-align: center;" | 28506
 +
|
 +
|-
 +
| 200x200x200
 +
| OBTM
 +
| style="text-align: center;" | 48741
 +
|
 +
|-
 +
| 256x256x256
 +
| OBTM
 +
| style="text-align: center;" | 77309
 +
|
 +
|-
 +
| 500x500x500
 +
| OBTM
 +
| style="text-align: center;" | 271273
 +
|
 +
|-
 +
| 1000x1000x1000
 +
| OBTM
 +
| style="text-align: center;" | 1001447
 +
|
 +
|-
 +
| 10000x10000x10000
 +
| OBTM
 +
| style="text-align: center;" | 79634546
 +
|
 +
|}
 +
 
 +
{| class=wikitable
 +
|-
 +
! Puzzle
 +
! Metric
 +
! Lower Bound
 +
! Upper Bound
 +
! Conjectured Value
 +
! Source
 +
|-
 +
| NxNxN, N<=1000
 +
| OBTM
 +
| style="text-align: center;" | N^2
 +
|
 +
|
 +
|
 +
|-
 +
| NxNxN
 +
| OBTM
 +
| style="text-align: center;" | (1/4 log(24!/4!^6) + o(1)) N^2/log(N)
 +
| style="text-align: center;" | (c + o(1)) N^2/log(N)
 +
| style="text-align: center;" | (1/4 log(24!/4!^6) + o(1)) N^2/log(N)
 +
| [https://arxiv.org/abs/1106.5736]
 +
|}
 +
 
 +
==== Subsets/alternate generating sets ====
 +
 
 +
{| class=wikitable
 +
|-
 +
! Puzzle
 +
! Subset
 +
! Metric
 +
! style="width:10%;" | Lower Bound
 +
! style="width:10%;" | Upper Bound
 +
! style="width:10%;" | Conjectured Value
 +
! State Realizing Lower Bound
 +
! Source
 +
|-
 +
| rowspan=2 | 2x2x2
 +
| rowspan=2 | <U,R>
 +
| HTM
 +
| colspan=3 style="text-align: center;" | 14
 +
| U R U' R' U R' U R' U2 R U2 R' U2 R2
 +
|
 +
|-
 +
| QTM
 +
| colspan=3 style="text-align: center;" | 17
 +
| U R U R' U' R U' R2 U R' U R' U2 R U'
 +
|
 +
|-
 +
| rowspan=7 | 3x3x3
 +
| rowspan=2 | <U,R>
 +
| HTM
 +
| colspan=3 style="text-align: center;" | 20
 +
| U R U R U R2 U2 R2 U2 R2 U' R U R U' R2 U2 R2 U2 R2
 +
|
 +
|-
 +
| QTM
 +
| colspan=3 style="text-align: center;" | 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
 +
| style="text-align: center;" | 21
 +
|
 +
| style="text-align: center;" | 21
 +
| U R F2 R U2 F2 U' F' R U F U R' F R2 U F R U2 R F'
 +
| [http://forum.cubeman.org/?q=node/view/566]
 +
|-
 +
| <U,L,F,R,B>
 +
| HTM
 +
| style="text-align: center;" | 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,M>
 +
| STM
 +
| colspan=3 style="text-align: center;" | 20
 +
| U M U M U M U2 M' U2 M U M' U' M U' M' U' M U' M2
 +
|
 +
|-
 +
| <u,r>
 +
| HTM
 +
| style="text-align: center;" | 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
 +
| style="text-align: center;" | 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'
 +
|
 +
|-
 +
| rowspan=2 | 4x4x4
 +
| <U,2R>
 +
| STM
 +
| colspan=3 style="text-align: center;" | 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'
 +
| [http://forum.cubeman.org/?q=node/view/558]
 +
|-
 +
| <U,r>
 +
| OBTM
 +
| style="text-align: center;" | 49
 +
|
 +
|
 +
| 7 edge flip
 +
|
 +
|}
 +
 
 +
==== Minxes ====
 +
 
 +
{| class=wikitable
 +
|-
 +
! Puzzle
 +
! Metric
 +
! style="width:10%;" | Lower Bound
 +
! style="width:10%;" | Upper Bound
 +
! style="width:10%;" | Conjectured Value
 +
! State Realizing Lower Bound
 +
! Source
 +
|-
 +
| rowspan=2 | Kilominx
 +
| HTM
 +
| style="text-align: center;" | 18
 +
| style="text-align: center;" | 31
 +
|
 +
|
 +
| [https://www.speedsolving.com/threads/kilominx-gods-number-bounds.67278/#post-1441983]
 +
|-
 +
| QTM
 +
| style="text-align: center;" | 22
 +
| style="text-align: center;" | 42
 +
|
 +
|
 +
| [https://www.speedsolving.com/threads/kilominx-gods-number-bounds.67278/#post-1441983]
 +
|-
 +
| Master Kilominx
 +
| OBTM
 +
| style="text-align: center;" | 94
 +
|
 +
|
 +
|
 +
| [https://www.speedsolving.com/threads/dodecahedron-gods-numbers.87369/]
 +
|-
 +
| Gigaminx
 +
| OBTM
 +
| style="text-align: center;" | 152
 +
|
 +
|
 +
|
 +
| [https://www.speedsolving.com/threads/dodecahedron-gods-numbers.87369/]
 +
|-
 +
| Elite Kilominx
 +
| OBTM
 +
| style="text-align: center;" | 217
 +
|
 +
|
 +
|
 +
| [https://www.speedsolving.com/threads/dodecahedron-gods-numbers.87369/]
 +
|-
 +
| Teraminx
 +
| OBTM
 +
| style="text-align: center;" | 299
 +
|
 +
|
 +
|
 +
| [https://www.speedsolving.com/threads/dodecahedron-gods-numbers.87369/]
 +
|-
 +
| rowspan=2 | Pyraminx Crystal
 +
| HTM
 +
| style="text-align: center;" | 41
 +
|
 +
|
 +
|
 +
| [https://www.speedsolving.com/threads/dodecahedron-gods-numbers.87369/]
 +
|-
 +
| QTM
 +
| style="text-align: center;" | 50
 +
|
 +
|
 +
|
 +
| [https://www.speedsolving.com/threads/dodecahedron-gods-numbers.87369/]
 +
|}
 +
 
 +
==== Cuboids ====
 +
 
 +
{| class=wikitable
 +
|-
 +
! Puzzle
 +
! Metric
 +
! style="width:10%;" | Lower Bound
 +
! style="width:10%;" | Upper Bound
 +
! style="width:10%;" | Conjectured Value
 +
! State Realizing Lower Bound
 +
! Source
 +
|-
 +
| 1x2x2
 +
|
 +
| colspan=3 style="text-align: center;" | 3
 +
| R U R
 +
|
 +
|-
 +
| 1x2x3
 +
|
 +
| colspan=3 style="text-align: center;" | 6
 +
| R U R U R U
 +
|
 +
|-
 +
| 1x3x3
 +
| HTM
 +
| colspan=3 style="text-align: center;" | 8
 +
| U L U R L U L D
 +
| [https://www.jaapsch.net/puzzles/floppy.htm]
 +
|-
 +
| rowspan=2 | 2x2x3
 +
| HTM
 +
| colspan=3 style="text-align: center;" | 14
 +
| U R2 U R2 U2 R2 F2 U F2 D2 R2 U R2 D
 +
| [https://www.jaapsch.net/puzzles/cube223.htm]
 +
|-
 +
| QTM
 +
| colspan=3 style="text-align: center;" | 15
 +
| U R2 U R2 U' R2 F2 U' R2 U' R2 U F2 U' R2
 +
| [https://www.jaapsch.net/puzzles/cube223.htm]
 +
|-
 +
| rowspan=2 | 2x3x3
 +
| HTM
 +
| colspan=3 style="text-align: center;" | 18
 +
| U R2 U F2 U2 R2 U' B2 L2 U2 L2 U' L2 F2 U' L2 F2 L2
 +
| [https://www.jaapsch.net/puzzles/domino.htm]
 +
|-
 +
| QTM
 +
| colspan=3 style="text-align: center;" | 19
 +
| U R2 U R2 U2 F2 U' F2 L2 B2 R2 D L2 U2 F2 U' R2
 +
| [https://www.jaapsch.net/puzzles/domino.htm]
 +
|}
 +
 
 +
==== Sliding Puzzles ====
 +
 
 +
{| class=wikitable
 +
|-
 +
! Puzzle
 +
! Metric
 +
! style="width:10%;" | Lower Bound
 +
! style="width:10%;" | Upper Bound
 +
! style="width:10%;" | Conjectured Value
 +
! State Realizing Lower Bound
 +
! Source
 +
|-
 +
| 2x2
 +
|
 +
| colspan=3 style="text-align: center;" | 6
 +
| R D L U R D
 +
| [https://web.archive.org/web/20140326092006/http://juropollo.xe0.ru/stp_results_mxn_a123_en.htm]
 +
|-
 +
| 3x2
 +
| STM
 +
| colspan=3 style="text-align: center;" | 21
 +
| R2 D L U L D R2 U L D L U R2 D L U L D
 +
| [https://web.archive.org/web/20140326092006/http://juropollo.xe0.ru/stp_results_mxn_a123_en.htm]
 +
|-
 +
| 4x2
 +
| STM
 +
| colspan=3 style="text-align: center;" | 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
 +
| [https://web.archive.org/web/20140326092006/http://juropollo.xe0.ru/stp_results_mxn_a123_en.htm]
 +
|-
 +
| 5x2
 +
| STM
 +
| colspan=3 style="text-align: center;" | 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
 +
| [https://web.archive.org/web/20140326092006/http://juropollo.xe0.ru/stp_results_mxn_a123_en.htm]
 +
|-
 +
| 6x2
 +
| STM
 +
| colspan=3 style="text-align: center;" | 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
 +
| [https://web.archive.org/web/20140326092006/http://juropollo.xe0.ru/stp_results_mxn_a123_en.htm]
 +
|-
 +
| 7x2
 +
| STM
 +
| colspan=3 style="text-align: center;" | 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
 +
| [https://web.archive.org/web/20140326092006/http://juropollo.xe0.ru/stp_results_mxn_a123_en.htm]
 +
|-
 +
| 8x2
 +
| STM
 +
| colspan=3 style="text-align: center;" | 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
 +
| [https://web.archive.org/web/20140326092006/http://juropollo.xe0.ru/stp_results_mxn_a123_en.htm]
 +
|-
 +
| 3x3
 +
| STM
 +
| colspan=3 style="text-align: center;" | 31
 +
| D2 R2 U2 L2 D R U L D2 R U R D L U R U L2 D2 R U2 L D
 +
| [https://web.archive.org/web/20140326092006/http://juropollo.xe0.ru/stp_results_mxn_a123_en.htm]
 +
|-
 +
| 4x3
 +
| STM
 +
| colspan=3 style="text-align: center;" | 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
 +
| [https://web.archive.org/web/20140326092006/http://juropollo.xe0.ru/stp_results_mxn_a123_en.htm]
 +
|-
 +
| 5x3
 +
| STM
 +
| colspan=3 style="text-align: center;" | 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
 +
| [https://web.archive.org/web/20140326092006/http://juropollo.xe0.ru/stp_results_mxn_a123_en.htm]
 +
|-
 +
| 4x4
 +
| STM
 +
| colspan=3 style="text-align: center;" | 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
 +
| [https://web.archive.org/web/20140326092006/http://juropollo.xe0.ru/stp_results_mxn_a123_en.htm]
 +
|-
 +
| 5x5
 +
| STM
 +
| style="text-align: center;" | 152
 +
| style="text-align: center;" | 182
 +
|
 +
|
 +
| [http://forum.cubeman.org/?q=node/view/559#comment-3116]
 +
|-
 +
| 6x6
 +
| STM
 +
| style="text-align: center;" | 230
 +
| style="text-align: center;" | 382
 +
|
 +
|
 +
|
 +
|-
 +
| 7x7
 +
| STM
 +
| style="text-align: center;" | 352
 +
| style="text-align: center;" | 693
 +
|
 +
|
 +
|
 +
|}
 +
 
 +
{| class=wikitable
 +
|-
 +
! Puzzle
 +
! Metric
 +
! style="width:10%;" | Lower Bound
 +
! style="width:10%;" | Upper Bound
 +
! style="width:10%;" | Conjectured Value
 +
! State Realizing Lower Bound
 +
! Source
 +
|-
 +
| Nx2
 +
| STM
 +
| style="text-align: center;" | 2N^2 - N
 +
| style="text-align: center;" | 2N^2 + O(N log(N))
 +
|
 +
| 180 degree rotation
 +
|
 +
|-
 +
| NxN
 +
| STM
 +
| style="text-align: center;" | N^3 - 2N + 2 - (N if N is odd, 0 otherwise)
 +
| style="text-align: center;" | 5N^3
 +
| style="text-align: center;" | (4/3 + o(1))N^3
 +
| 180 degree rotation
 +
|
 +
|}
  
=== [[3x3x3]] ===
+
==== Circle Puzzles ====
* In July 2010, [[Morley Davidson]], [[John Dethridge]], [[Herbert Kociemba]], and [[Tomas Rokicki]] proved God's Number for [[3x3x3]] to equal 20 in [[HTM]]. The [[superflip]] is the best-known example of a position which requires 20 moves or moves to solve in [[HTM]].
 
* In August 2014, [[Morley Davidson]], [[John Dethridge]], and [[Tomas Rokicki]] proved God's Number for [[3x3x3]] to equal 26 in [[QTM]]. The [[superflip plus fourspot]] is the first proved example of a position which requires 26 moves or moves to solve in [[QTM]].
 
* The God's number in [[slice turn metric]] (STM) is still unknown; there is a lower bound of 18s and an upper bound of 20s. [http://cubezzz.dyndns.org/drupal/?q=node/view/200]
 
  
=== [[4x4x4]] ===
+
{| class=wikitable
* In the outer block turn metric (OBTM), the God's number for 4x4x4 is known to be between [http://cubezzz.dyndns.org/drupal/?q=node/view/236 35] and [http://cubezzz.dyndns.org/drupal/?q=node/view/541 55] moves.
+
|-
* In the single-slice turn metric (SSTM), the God's number is known to be between [http://cubezzz.dyndns.org/drupal/?q=node/view/236 32] and [http://cubezzz.dyndns.org/drupal/?q=node/view/541 53] moves.
+
! Puzzle
* In the block turn metric (BTM), the God's number is known to be between [http://cubezzz.dyndns.org/drupal/?q=node/view/236 29] and [http://cubezzz.dyndns.org/drupal/?q=node/view/541 53] moves.
+
! Metric
 +
! style="width:10%;" | Lower Bound
 +
! style="width:10%;" | Upper Bound
 +
! style="width:10%;" | Conjectured Value
 +
! State Realizing Lower Bound
 +
! Source
 +
|-
 +
| rowspan=2 | Eliac
 +
| HTM
 +
| style="text-align: center;" | 71
 +
|
 +
| style="text-align: center;" | 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
 +
| [http://forum.cubeman.org/?q=node/view/570]
 +
|-
 +
| QTM
 +
| style="text-align: center;" | 80
 +
|
 +
| style="text-align: center;" | 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'
 +
| [http://forum.cubeman.org/?q=node/view/570]
 +
|-
 +
| rowspan=2 | Rashkey 1
 +
| HTM
 +
| colspan=3 style="text-align: center;" | 12
 +
|
 +
| [https://www.jaapsch.net/puzzles/rashkey.htm]
 +
|-
 +
| QTM
 +
| colspan=3 style="text-align: center;" | 15
 +
|
 +
| [https://www.jaapsch.net/puzzles/rashkey.htm]
 +
|-
 +
| rowspan=2 | Rashkey 2
 +
| HTM
 +
| colspan=3 style="text-align: center;" | 19
 +
|
 +
| [https://www.jaapsch.net/puzzles/rashkey.htm]
 +
|-
 +
| QTM
 +
| colspan=3 style="text-align: center;" | 23
 +
|
 +
| [https://www.jaapsch.net/puzzles/rashkey.htm]
 +
|-
 +
| rowspan=2 | Rashkey 3
 +
| HTM
 +
| colspan=3 style="text-align: center;" | 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'
 +
| [https://benwh1.github.io/web/circle_puzzles/rashkey_3/index.html]
 +
|-
 +
| QTM
 +
| colspan=3 style="text-align: center;" | 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'
 +
| [https://benwh1.github.io/web/circle_puzzles/rashkey_3/index.html]
 +
|}
  
=== [[5x5x5]] ===
+
==== Other ====
* In OBTM, the God's number for 5x5x5 is known to be between [http://cubezzz.dyndns.org/drupal/?q=node/view/236 52] and [//www.speedsolving.com/forum/threads/5x5x5-obtm-upper-bound.61270/ 141] moves.
 
  
=== [[Megaminx]] ===
+
{| class=wikitable
* The God's number for the Megaminx is known to be between 48 and 194 [[FTM|face turns]]. [//www.speedsolving.com/forum/threads/approximating-dodecahedron-upper-bound.65036/]
+
|-
 +
! Puzzle
 +
! Metric
 +
! style="width:10%;" | Lower Bound
 +
! style="width:10%;" | Upper Bound
 +
! style="width:10%;" | Conjectured Value
 +
! State Realizing Lower Bound
 +
! Source
 +
|-
 +
| 3x3x3 Supercube
 +
| HTM
 +
| style="text-align: center;" | 24
 +
| style="text-align: center;" |
 +
| style="text-align: center;" |
 +
| U F U L D B2 R2 D2 L D2 L D2 B2 F U2 R' B U' R2 B L' D' U' R'
 +
|
 +
|-
 +
| Redi Cube
 +
|
 +
| colspan=3 style="text-align: center;" | 19
 +
|
 +
| [https://www.speedsolving.com/threads/redi-cube-discussion-help-thread.65452/page-7#post-1263980]
 +
|-
 +
| Master Pyraminx
 +
| OBTM
 +
| style="text-align: center;" | 20
 +
| style="text-align: center;" | 26
 +
| style="text-align: center;" | 20
 +
| Uw Rw Lw Bw' L R' Rw Bw U' Rw Uw' B' L' Uw' R' U' Rw' B' L' Bw
 +
| [https://www.speedsolving.com/threads/master-pyraminx-gods-number-bounds.74056/]
 +
|-
 +
| rowspan=2 | Gear Cube
 +
| HTM
 +
| colspan=3 style="text-align: center;" | 6
 +
|
 +
| [https://www.jaapsch.net/puzzles/gearcube.htm]
 +
|-
 +
| QTM
 +
| colspan=3 style="text-align: center;" | 12
 +
|
 +
| [https://www.jaapsch.net/puzzles/gearcube.htm]
 +
|-
 +
| Gear Cube Extreme
 +
| HTM
 +
| style="text-align: center;" | 17
 +
| style="text-align: center;" | 25
 +
| style="text-align: center;" | 17
 +
|
 +
| [http://forum.cubeman.org/?q=node/view/561]
 +
|-
 +
| rowspan=2 | Rubik's Ufo
 +
| FTM
 +
| colspan=3 style="text-align: center;" | 14
 +
|
 +
| [https://www.jaapsch.net/puzzles/rubufo.htm]
 +
|-
 +
| 6thTM
 +
| colspan=3 style="text-align: center;" | 16
 +
|
 +
| [https://www.jaapsch.net/puzzles/rubufo.htm]
 +
|-
 +
| Face-Turning Octahedron
 +
|
 +
| style="text-align: center;" | 21
 +
| style="text-align: center;" |
 +
| style="text-align: center;" |
 +
|
 +
| [https://www.youtube.com/watch?v=YKrwFoKw5O8]
 +
|}
  
 
== External links ==
 
== External links ==

Latest revision as of 22:23, 28 March 2024

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 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/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,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,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 49 7 edge flip

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
3x3x3 Supercube HTM 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'
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]

External links