User:Breadonastick/sandbox

Rubik's Cube Variations' Optimal Moves

A photo showing the traditional 3x3 Rubik's cube along with the 2x2, 4x4, 5x5, 6x6, and 7x7 variants.

The optimal number of moves to solve a puzzle toy (also known as the God's Number) is the maximum amount of moves you may need to solve any variation of the puzzle. In reference to the famous Rubik's cube it is 20 in the outer block turn metric which (OBTM) which is the official turn metric used for the cube. A similar measurement can be taken with the numerous variations of the Rubik's cube such as the 2x2 Cube (Pocket Cube), 4x4 cube (Rubik's Revenge), Megaminx (dodecagon), Pyraminx, Skewb, etc.

2x2 Cube (Pocket Cube)

Move Notation

The 2x2 variation of the Rubik's cube reffered to as the Pocket Cube

The move notation for the 2x2x2 cube follows that of the 3x3x3 cube with the only difference being that it lacks the M, S, and E turn because it lacks that middle layer.

God's Number

The maximum number of possible moves required to solve any configuration of a 2x2x2 cube is 11. This number was able to be calculated in a much more simple manner than the 3x3x3, since it has significantly less possible permutations. The total number of different 2x2x2 configurations is 8!(3^8)/3=88,179,840 if the whole orientation of the cube is accounted for. Most often for configurations it is not resulting in the total configurations being 1/24th of this number because a single cube can be rotated to 24 different positions in three dimensions. This results in the total configurations being (7!)(3^7)/3=3,674,160. This number is considerably smaller than that for a 3x3x3 cube which sits at 43,252,003,274,489,856,000. The three million number is small enough that a computer is able to be used to calculate the number of moves to solve each individual orientation. Doing this results in the chart seen below with n being the number of turns and p being the number of possible cube positions that require that many turns to be solved. The f represents the face-turn metric data and the q represents the quarter-turn metric data. As seen from the computer generated data, the most number of moves required to solve a cube in any orientation is 11 moves with the half turn metric and 14 using the quarter turn metric.

n	p-f	p-q
0	1	1
1	9	6
2	54	27
3	321	120
4	1847	534
5	9992	2256
6	50136	8969
7	227536	33058
8	870072	114149
9	1887748	360508
10	623800	930588
11	2644	1350852
12	0	782536
13	0	90280
14	0	276

4x4 Cube (Rubik's Revenge)

Move Notation

The 4x4 variation of the Rubik's cube reffered to as the Rubik's Revenge

The 4x4 cube has the same rotation of the R, L, U, D, F, and B for the outer most layers of the cube just like for the 3x3 cube. The inner layers of the cube that make up the middle are referred to using the same letters, but in lower case according to what side of the shape it is closest to. So the layer directly behind the outermost front lay (F) would be denoted by f. The other distinct difference with the move notation of the 4x4 comes with its ability to turn 2 layers at once. The official denotation for moving the two corresponding layers to one side is the side's normal letter denotation followed by a lower case w. The unofficial method is denoted by adding the upper and lower case letter of the two sides you're rotating together. So the official way to describe rotating the first two front sides clockwise together would be Fw, but the unofficial method would be Ff.

God's Number

In the outer block turn metric (OBTM), which is the official metric used by the World Cube Association (WCA), the God's Number is known to be between 35 and 55 moves. The 4x4 cube has approximately 7 401 196 841 564 901 869 874 093 974 498 574 336 000 000 000 different possible combinations which is a number much too big for a computer to deal with.

Upper Bound

To get past the problem of the large number of combinations, the solving of the cube was broken up into four parts for OBTM (with parts three and four sometimes being merged together) which allowed for the total number of permutations the computer deals with, as well as the number of moves to be reduced. The total number of permutations in the calculation is reduced by using symmetry classes, which are the different permutations of the cube that are the same depending on how you rotate the whole cube. They are dependent upon what step you are looking at, so if the step is only looking at one single piece, it would 24 different symmetries because you can hold the cube in 24 different orientations (6 sides with 4 sides each because square so six times four is 24). This number gets much larger with the more pieces you include. This technique was used to achieve the upper bound of 57 originally which has since been pushed to 55 in .

In the first step the computer will move the right and left center pieces to the corresponding side that they need to be on. This takes a maximum of 7 moves for 735,471 different orientations (not including symmetries). In the second step the computer has to move the up, down, front, and back center pieces to their corresponding sides, and then line up the right and left center pieces from the first step in a way that makes them easier to solve in the next step. This step needs a maximum of 12 moves for 38,760,321,600 different orientations. In the third and fourth step the cubes remaining centers are lines up and then all of the edge pieces are paired to their respective centers with the corners being paired after. This step needs a maximum of 16 moves for the third part and 20 moves for the fourth part for 7,041,323,520,000 different orientations. At this point the cube is solved so then the calculate move totals are added up which gives 7+12+16+20=55 so 55 is the upper bound.

Lower Bound

The lower bound was solved in a completely different manner than the upper bound. This is because the lowest possible number of turns to solve each section would be 1 so then 1+1+1+1=4 and that is a very broad estimation of the lower bound. Even though it is much different than the upper bound method, the lower bound calculations involve much less complex math. To solve for the lower bound a more counting based approach is taken. First the total different number of combinations of the cube is calculated, and this is known to be 7 401 196 841 564 901 869 874 093 974 498 574 336 000 000 000. This is used a max limit for comparison to the next calculation. Then the total different combinations is calculated per every additional move on the cube. Once that number surpasses the total different possible combinations, the moves used to obtain it is then used as the minimum. In the case of the 4x4x4 in OBTM, that number is 35 turns, making it the lower bound for the time being.

Estimation of God's Number

Although, it is not known how to reasonably calculate the God's Number using current computer processing power, some people have still managed to develop formulas that allow them to approximate what they believe it to be. One formula was developed that can be applied to any cube that follows the n x n x n format and has the side number n being less than or equal to 20. This approximation is made in asymptotic notation with the formula O(n^2/log(n)) which comes out to be 45 in OBTM. This number does fall in-between the upper and lower bound range of 35 to 55 which means it is a valid approximation. In the future the bounds will be specified more to either kick 45 out of the range or to close in around it and prove it to be the true God's Number.

Megaminx (Dodecagon)

Move Notation

A 12 sided, Rubik's cube style toy called the Megaminx

The official move notation recognized by the World Cube Association (WCA) for the Megaminx is called Pochmann's notation. Each side of the 12 faced cube has 5 sides, so all turns of these faces are categorized into up (U & U'), right (R++ & R--), and down (D++ & D--) (which is sometimes referred to as left (L++ & L--)). The U indicates one one-fifth turn of the top face in the clockwise direction with the U' being the same but in the counter-clockwise direction. The R++ indicates turning the right portion of the Megaminx, which is everything but the left face, two-fifths of a whole turn in the clockwise direction, while R-- indicates turning that same portion two-fifths in the counter-clockwise direction. The D++ indicates turning the bottom portion of the Megaminx, which is everything but the top face, two-fifths of a whole turn in the clockwise direction, while D-- indicates turning the same portion two-fifths in the counter-clockwise direction. The right and down turns are in two-fifths of a whole rotation instead of one-fifth because they improve the scramble quality of the Megaminx, so the WCA favors them for official use.

God's Number

The Megaminx has 100 669 616 553 523 347 122 516 032 313 645 505 168 688 116 411 019 768 627 200 000 000 000 different permutations. This is significantly larger than a computer can handle to just produce the God's Number, so different techniques were used to find the lower and upper bounds, which currently sits at 48 and 194 respectively.

Upper Bound

The upper bound for the Megaminx is reported by some to be 194, but the explanation of how this was calculated is not apparent.

Lower Bound

The same counting based method used for creating a lower bound of the 4x4 can be used to create the lower bound of the Megaminx. First the total number of different possible combinations of the cube is calculated which ends up being 100 669 616 553 523 347 122 516 032 313 645 505 168 688 116 411 019 768 627 200 000 000 000 or 1.01*10^68 for simplicity. Then the total different possible combinations is calculated for every turn of the cube. So after no turns it has 1 possible orientation, after 1 turn it has 48 possible orientations (because of 12 faces that can be moved to 4 different new spots), after 2 turns it has 1920 different orientations and so on until you get to 45 moves. After 45 moves there are 3.64745*10^68 different possible orientations, which is the first time the number of possible orientations exceeds the total possible moves for the cube of 1.01*10^68. Since 45 moves of the Megaminx produces more possible orientations than possible, it is known that all possible orientations of the cube can be solved within 45 moves. This broad calculation does not account for duplicate orientations as the number increase so by using more complex mathematics the lower bound can be continuously raised higher. As this technique has become more reformed the lower bound has shifted from 45 to 48, where it currently resides.

Pyraminx

God's Number

A pyraminx puzzle showing an incomplete turn

The God's Number for the Pyraminx is 11 turns (with 4 possible additional tip turns). Ignoring the tip pieces of the Pyraminx (because they don't interact with any other pieces of the puzzle), it only has one way to turn the puzzle, so the number of turns is uniform throughout all discussion.

The cube is much simpler than most others, only having a total of 75,582,720 different possible combinations and 933,120 without the tips. This means that it is simple enough for a computer to go through each different combination, solve it, and count the number of moves. Doing so shows that the max number of turns necessary to solve the cube is 11 for the main puzzle and then 14 if you count the twists of the tips. The table below details the data provided by the computer with t being the number of turns needed to solve the Pyraminx and p being the total number of different permutations that require that many moves to be solved.

n	p
0	1
1	8
2	48
3	288
4	1,728
5	9,896
6	51,808
7	220,111
8	480,467
9	166,276
10	2,457
11	32
Total	933,120

Skewb

A skewb (skewed cube)

The Skewb's God Number was solved in the same manner as the Pyraminx because it is also a very simple puzzle. It only has 3,149,280 different permutations which is enough for a computer to handle the calculations. So by using this method the solution comes out to be 11 turns. The chart below provides the number of turns (t) needed for however many positions of the cube (p). Since 11 is the maximum number of turns needed it is then the God's Number.

n	p
1	8
2	48
3	288
4	1,728
5	10,248
6	59,304
7	315,198
8	1,225,483
9	1,455,856
10	81,028
11	90
Total	3,149,280