Further reflections on the Rubik's Cube

 

Visual metaphor and pun

Since my previous  post I've been thinking a bit more about Rubik's Cubes.  I have been wondering what is the simplest way to represent their state mathematically, and by extension programatically.

Configurations of the cube clearly form a group, so I set myself the goal of creating objects in python which would represent individual configurations and which could be multiplied together to form new objects.  For example, $I$ would represent an unscrambled cube, $L$ a cube obtained from $I$ by moving the left face clockwise, $U$ a cube obtained from $I$ by moving the upper face clockwise and $L*U$ the cube obtained by rotating the left face first and then the upper face.

The question is: what is the most elegant representation for each of these objects?  I was initially drawn by the idea of labelling the stickers (other than the centre face ones) 1 to 48 and representing each object as a different permutation.  This makes multiplication very easy but has the drawback that you are forced to make some arbitrary decisions about how to label the stickers, and each generator object $\{L,R,U,D,F,B\}$ is a bespoke permutation that must be worked out by hand, with a lot of squinting while attempting to visualise.

Then I realised that we can instead simply store how each sub-cube is rotated relative to its original position.  If we treat the (fictitious) centre cube as occupying the origin then each sub-cube in the scrambled cube is simply rotated from its original position around a vector passing through the origin.  This means that all we need to represent the scrambled cube is a 3x3x3 array.  This actually gives us more information than a permutation of stickers since it also tells us how the centre-face cubes have been rotated.

The cherry on the top is that rotations can be represented by unitary quarternions.  So scrambled cubes can be represented by 3x3x3 arrays of quarternions, and once this representation is chosen the operations of multiplication and inverses are straightforward to implement.

The files are rubik.py and quarternion.py and you can experiment with them using the widget below.

NOTES:

There's a strange feature of this implementation which I've left in deliberately. If you have a unit quarternion
$$
q = cos\theta + sin\theta\mathbf{\hat{u}}
$$
Then $q v q^{-1}$ is $v$ rotated about $\mathbf{\hat{u}}$ clockwise (looking in the same direction as $\mathbf{\hat{u}}$). But the amount of rotation isn't $\theta$, it's $2\theta$. This means that there are two aliases for rotation of $v$ by $\theta$ namely
$$
\begin{align}
cos\left(\frac{\theta}{2}\right) + sin\left(\frac{\theta}{2}\right)\mathbf{\hat{u}} &= q \\
cos\left(\frac{\theta+2\pi}{2}\right) + sin\left(\frac{\theta+2\pi}{2}\right)\mathbf{\hat{u}} &= -q \\
\end{align}
$$
So if you see a $-1$ that means that a sub-cube has been fully rotated an odd number of times. This could be seen as a bug, but since it's useful information it seems a shame to strip it out.