2
$\begingroup$

בס''ד

The Question

A Rubik's cube is a 3x3x3 game that illustrates easily certain group-theory and other mathematical concepts in its solution, as can be seen from this picture:

Picture of Rubik's Cube from Wikipedia

The usual idea of the game is to rotate various sides until the cube has each side with just one color (of six) and all sides are solved.

The cube can get mixed up to varying degrees. How can it be easily proved - what is the minimum number of moves needed to solve any cube configuration using any number of these cube side rotation moves to scramble it?

Sketch of the Answer

The first thing to notice is that the same scrambling and fixing rotations can be applied to the 2x2x2 version of the Rubik's cube called the Pocket Cube:

Pocket Cube Variation of the Rubik's

Then its solution is also the solution to the corner cubes of the full 3x3x3 Rubik's Cube.

Any solution of the full Rubik's Cube must solve the equivalent 2x2x2 Pocket Cube problem.

The 2x2x2 Pocket Cube only has $8*7*6*5*4*3*2*1$ solution states at most, so it is readily amenable to use computer code to find its "eigen-rotations", rotations that produce unique combinations.

Then the number of possibilities needing consideration for the full cube problem is very much restricted to only those also solving the 2x2x2 problem, making those also amenable to computer computation!

$\endgroup$

closed as unclear what you're asking by mercio, Namaste, Lord Shark the Unknown, mlc, hardmath Jun 21 '17 at 21:04

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ something is wrong with the links: only the first one is actually a link to somewhere $\endgroup$ – Vincent Jun 21 '17 at 9:32
  • $\begingroup$ Originally posted on physics (but closed b/c it's not a question about physics). $\endgroup$ – Kyle Kanos Jun 21 '17 at 10:06
  • $\begingroup$ Although your post, drawing upon Wikimedia images, is colorful, it is not clear what you are asking. Your reasoning that the $2\times 2\times 2$ "pocket cube" is easier/faster to solve than the $3\times 3\times 3$ "classic" Rubik's Cube is plausible if not terribly rigorous, but it seems you want an audience to admire your insight, rather than the answer to any particular Question. $\endgroup$ – hardmath Jun 21 '17 at 21:04
1
$\begingroup$

This website answers your question: http://www.cube20.org/

it is a non-trivial problem and i dont think there is a way to just easily prove it without doing a large amount of computations.

$\endgroup$
  • $\begingroup$ As I was typing up my response, I noticed that you posted yours. However, your response is actually not what he was asking for, because if you go to physics.stackexchange.com/questions/340178/…, he already acknowledged cube20.org with a hyperlink in his statement "Google reportedly solved the problem". Therefore, I posted my response. F.Y.I. $\endgroup$ – Christopher Mowla Jun 21 '17 at 15:48
1
$\begingroup$

Nice question.

My response was too long to be a comment, and thus I decided to make a response.

Being experienced with using a 3x3x3 Rubik's Cube solver to create "parity algorithms" for the 4x4x4 Rubik's Cube, I can relate to the notion that this approach can be used to find God's number for the 3x3x3 from solutions to the 2x2x2. However, we cannot generate all 3x3x3 positions with 2x2x2 move sequences of length 20 or less if that is what you are proposing. To further complicate things, I believe it's possible that move sequences which generate completely different 2x2x2 positions will generate the exact same 3x3x3 position. That is, even among the 2x2x2 move sequences we "enumerate" which are of length 20 or less may not be unique as far as the 3x3x3 is concerned.


Firstly, I will provide evidence of the previous statement with a concrete example.

Being experienced with using 3x3x3 solvers to create 4x4x4 "parity algorithms", one day I found something quite interesting. But first note that I can find 4x4x4 parity algorithms without solvers (e.g., most of the algorithms I attributed to my name on this wikipage, besides algorithms confined to the move set < U2,F2,B2,D2,l,r >, I found by hand), and one day I found the 4x4x4 move sequence by hand:

r2 B r' U R' U r U' R U' r B U2 r U2 r' B2 r2---(i)

Typically, these type of 4x4x4 algorithms (ones which "flip" a "single" edge and which consist of only of turns which are single slices, i.e., not move sequences like

r' 3u' 2U' l' 2R' u' 2R' u 3l 2R' u l' u' 2R' u l e' r ---(ii)

--another one of my hand-found algs),

one can literally convert all inner single slice turns to outer slice turns to "see" what the 4x4x4 algorithm looks like on the 3x3x3, and vice versa.

If we convert all inner slice turns of (i) to outer face turns as follows, we get the following move sequence. (Click on the move sequence to observe the 3x3x3 position it generates.)

R2 B R' U R' U R U' R U' R B U2 R U2 R' B2 R2---(iii)

Now, two well-known 4x4x4 "single edge flip" parity algorithm move sequences are the following.

r2 B2 U2 l U2 r' U2 r U2 F2 r F2 l' B2 r2---(iv)

r' U2 l F2 l' F2 r2 U2 r U2 r' U2 F2 r2 F2---(v)

If we convert (iv) to 3x3x3 turns, we get this position, and if we convert (v) to 3x3x3 turns, we get the same position generated by (iv).

Clearly 3x3x3 Rubik's Cube position (iii) is different than 3x3x3 Rubik's Cube position (iv) == Rubik's Cube position (v), but yet, if we convert 3x3x3 Rubik's Cube position (iii), (iv) and (v) to the 4x4x4, we get the same example "single edge flip" position (even on the super/picture 4x4x4 Rubik's Cube).


Now I believe I have made it clear of the possibility of two 2x2x2 move sequences which generate two different 2x2x2 positions can possibly generate the exact same 3x3x3 position. Let me now explain why using various 2x2x2 move sequences to generate all 3x3x3 positions is insufficient.

On August 30, 2013, I made this post on speedsolving.com regarding how to possibly find God's number for the 4x4x4 cube, using 2x2x2 pock cube moves as a basis of the "skeleton" solution of 4x4x4 positions. This was Herbert Kociemba's response to my proposal. He achieved the number, 2,578,606,199,622,633,886,542,987,264, from his generating function (programmed in Mathematica) by picking the coefficient of the x^35 term with his generating function (copy, paste, and run the following code in Mathematica),

gfh[n_, x_] := 3/(6 - 4 (3 x + 1)^(n - 1)) - 1/2

Series[gfh[2, x], {x, 0, 35}]

, where the 2 indicates the cube size (i.e., the 2x2x2), 35 is the length of the move sequence, and the coefficient in front of the x^35 term tells you how many move sequences of length 35 there are on the 2x2x2.

Using his generating function for our case, that is, to calculate how many move sequences are there on the 2x2x2 which are of length of 20 (since 20 is the upperbound/God's number for the 3x3x3 Rubik's Cube in htm = OBTM), we use the code:

gfh[n_, x_] := 3/(6 - 4 (3 x + 1)^(n - 1)) - 1/2

Series[gfh[2, x], {x, 0, 20}]

The coefficient of the x^20 term we get from Mathematica is 914,039,610,015,744 which could only possibly be a fraction of the 43,252,003,274,489,856,000 total 3x3x3 positions.


Lastly, how about some science fiction for comic relief. See this post of mine in another "god's number" thread on speedsolving.com in which I use the "pattern" of the number of digits of factorial to interestingly enough "approximate" what God's number could be close to on the nxnxn.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.