7.1. Rubik's cube

Let us suppose that we number from 1 to 48 the non-central coloured squares of a Rubik's cube. There are six basic rotations, corresponding to each of the six faces:

We introduce the following notation for quarter-turns, with clockwise rotations:

In[146]:=

It is customary to define the following face-turns (the initials stand for Front, Down, Left, Up, Right, Back for obvious reasons):

In[153]:=

In[154]:=

With a normal Linux box we can compute a strong generating set in a few seconds:

In[155]:=

We translate it to Cycles notation. We see that there are 18 points in the base and 99 generators (a SGS with only 19 generators is known for the Rubik's group):

In[156]:=

In[157]:=

Out[157]=

Reordering the base we can get this reduced SGS (this is taken from Butler's book):

In[158]:=

We check that it is a strong generating set indeed:

In[160]:=

In[161]:=

In[162]:=

Out[162]=

As we said, it is a huge group:

In[163]:=

Out[163]=

In[164]:=

Out[164]=

Orders of the chain of stabilizers:

In[165]:=

In[166]:=

Out[166]=

In[167]:=

Out[167]=

Now we can check potential configurations:

A rotation in a single corner or the exchange of two side-neighbours are not possible:

In[168]:=

Out[168]=

In[169]:=

Out[169]=

But pairs of them are allowed, in adequate directions:

In[170]:=

Out[170]=

In[171]:=

Out[171]=

In[172]:=

Out[172]=

A combination of both is impossible:

In[173]:=

Out[173]=

There is the famous question on the minimum number of moves which allows solving any configuration of the Rubik cube. Here it is very important to distinguish between face turns and quarter turns. An f-turn can be equal to one or two q-turns depending on the case. In what follows we only consider q-turns. There is a simple lower bound to the minimum number of q-turns required to solve any configuration, obtained by branching over 7 possibilities (the identity and the six rotations) that number of times: 24

24 is the first power of 7 which is larger than the order of the group:

In[174]:=

Out[174]=

The superflip position requires 24 moves (see wikipedia):

In[175]:=

In[176]:=

Out[176]=

Interestingly, this is the only nontrivial permutation which commutes with every other permutation in the Rubik group:

In[177]:=

Out[177]=

In[178]:=

Out[178]=

In[179]:=

Out[179]=

In[180]:=

Out[180]=

In[181]:=

Out[181]=

In[182]:=

Out[182]=

A position requiring 26 q-turns is known.

As of 2008, the best upper bounds known are 26 f-turns and 35 q-turns to solve arbitrary configurations of the cube.

Another frequent question whether a SGS can be used to actually solve an arbitrary configuration of the Rubik cube and the answer is of course positive. The algorithm PermWord can decompose any configuration in a product of 19 coset representatives, but then we need to decompose each of those 19 representatives in terms of the original 6 rotations. The final algorithm is, however, far from optimal, and actually very simple "human" algorithms perform better than this.

There are 239 possible nontrivial coset representatives:

In[183]:=

Out[183]=

Let us construct the canonical representatives:

In[184]:=

Those moves can be expressed in terms of face turns. For simplicity, we use an external solver to do it (we use kociemba.org). This function transforms a permutation into a chain of facelets that can be fed to that solver:

In[187]:=

For example:

In[188]:=

Out[188]=

and relate them with the collections of face-turns that we have previously stored in a file:

In[189]:=

Check that the relations are correct:

In[190]:=

Out[190]=

Created by Mathematica  (May 16, 2008)