Difference between revisions of "God's Algorithm"
(+ link to Wikipedia) |
Ben Whitmore (talk | contribs) (→Other: 3x3 supercube) |
||
(33 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
− | '''God's Algorithm''' is the | + | <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 | + | '''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 | ||
+ | | | ||
+ | |} | ||
− | === | + | ==== Circle 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 | 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] | ||
+ | |} | ||
− | === | + | ==== Other ==== |
− | |||
− | === [[ | + | {| class=wikitable |
− | + | |- | |
+ | ! 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.
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/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] |