Saturday, 1 August 2009

How to count the number of positions of Rubik's cube

Previously on this blog, we have been looking at the symmetries of graphs, which we defined as permutations of the vertices which leave the edges (collectively) in the same places. We think of permutations as active rearrangements of the vertices, rather than as static sequences. For example, we think of the static permutation [2,1,4,3] as the active rearrangement [[1,2],[3,4]], which swaps the 1 and 2 positions, and swaps the 3 and 4 positions. Given two permutations g and h, the active viewpoint enables us to ask what happens when you do g then h, which we think of as multiplication g*h; and how to undo g, which we think of as an inverse g^-1.

The symmetries of a graph form a group. This means, that if g and h are symmetries, then so are g*h, and g^-1. So a group is a set of permutations which is closed under multiplication and inverses.

We can use permutation groups to study all sorts of things besides graph symmetries. As an example, this week I'm going to look at Rubik's cube.

First, we need to work out a way to represent cube moves as permutations. That's easy - we just number the little squares as follows:

Then a clockwise rotation of the front face (the blue face, with an F in the centre), can be represented as the following permutation:

`f = [[1,3,9,7],[2,6,8,4],[17,41,33,29],[18,44,32,26],[19,47,31,23]]`
This says, that f sends the 1 square to the 3 position, 3 to 9, 9 to 7, 7 to 1 (the corners of the blue face); 2 to 6, 6 to 8, 8 to 4, 4 to 2 (the edges of the blue face); together with three other cycles (the corners and edges adjacent to the blue face).

It's then an easy matter to write down permutations corresponding to the clockwise rotations of the other faces:
`b = p [[51,53,59,57],[52,56,58,54],[11,27,39,43],[12,24,38,46],[13,21,37,49]]l = p [[21,23,29,27],[22,26,28,24],[ 1,31,59,11],[ 4,34,56,14],[ 7,37,53,17]]r = p [[41,43,49,47],[42,46,48,44],[ 3,13,57,33],[ 6,16,54,36],[ 9,19,51,39]]u = p [[11,13,19,17],[12,16,18,14],[ 1,21,51,41],[ 2,22,52,42],[ 3,23,53,43]]d = p [[31,33,39,37],[32,36,38,34],[ 7,47,57,27],[ 8,48,58,28],[ 9,49,59,29]]`
Note that I didn't bother to number the centre square in each face, or write down any permutations that move a middle slice. For example, we could have written down:
`x = [[4,44,54,24],[5,45,55,25],[6,46,56,26]]`
However, doing x is the same as doing u^-1 * d^-1 and then turning the whole cube round. What we're interested in is the possible positions of the 54 squares relative to one another, so we don't really want to count rotations of the whole cube. For this reason, we leave out rotations of the middle slices.

Okay, so we have written down six permutations, corresponding to clockwise rotations of the six faces. Hopefully it's clear that these six elements generate the Rubik's cube group. So we are now in a position to perform calculations within the Rubik's cube group.

Within a group, the order of an element g is defined as the least n>0 such that g^n = 1. In other words, the order of g is the number of times you have to do g to get back where you started. (Recall that the order of a group is the number of elements it contains. The order of an element is equal to the order of the group generated by the element, since this is {g, g^2, ... , g^n-1, g^n = 1}, having n elements.)

For permutations written in cycle notation, it is easy to see the order by inspection. For example:
• The order of g = [[1,2]] is 2 - you have to do g twice to get back where you started.
• The order of h = [[1,2,3]] is 3 - you have to do h three times to get back where you started.
• The order of k = [[1,2,3],[4,5]] is 6. At k^2, we have [[1,3,2]] - the 4 and 5 are in the correct positions, but the 1, 2, 3 are not. At k^3 we have [[4,5]] - now the 1, 2, 3 are in the correct positions, but the 4 and 5 are not. Only at k^6 does everything get back to the starting position.
Hopefully it's clear that the order of an element will always be the least common multiple of the lengths of the cycles:
`orderElt g = foldl lcm 1 \$ map length \$ toCycles g`

For example, in the Rubik's cube group we have:
`> f*l[[1,3,9,37,53,17,41,33,27,21,23,19,47,59,11],[2,6,8,34,56,14,4],[7,31,29],[18,44,32,28,24,22,26]]> orderElt it105`
That is, if you do a front turn followed by a left turn, you will have to repeat 105 times before you get back to the starting position.

When we were looking at graph symmetries, we found that it was particularly useful to have our generators in the form of a strong generating set, since it was then straightforward, for example, to calculate the order of the group.

Rubik's cube isn't a graph. Luckily, the HaskellForMaths library has a function to calculate a strong generating set from any set of generators:
`> mapM_ print \$ sgs [f,b,l,r,u,d][[1,3,9,7],[2,6,8,4],[17,41,33,29],[18,44,32,26],[19,47,31,23]][[1,21,51,41],[2,22,52,42],[3,23,53,43],[11,13,19,17],[12,16,18,14]][[1,31,59,11],[4,34,56,14],[7,37,53,17],[21,23,29,27],[22,26,28,24]][[2,34,22,26,32,44,16,12,46,38,24],[3,31,47,13,49,37,21],[4,8,6,42,52,54,58,56,18,28,14],[7,9,43,39,27,11,41],[19,29,33,51,57,59,53]][[3,13,57,33],[6,16,54,36],[9,19,51,39],[41,43,49,47],[42,46,48,44]][[4,38,32,46,16,44,34,24,36,14,12],[6,28,56,48,22,52,26,58,8,54,42],[7,31,29],[9,59,57,51,53,33,37,49,13,21,47,27,39,43,11]][[6,52,56,54],[9,53,57,51],[11,39,43,47],[12,24,46,44],[13,33,21,49]][[7,47,57,27],[8,48,58,28],[9,49,59,29],[31,33,39,37],[32,36,38,34]][[8,56,16,52,54],[9,33,47],[12,46,32,24,42],[13,51,43]][[9,59],[12,38],[13,49],[24,46],[27,47],[33,37],[39,43],[51,57],[52,58],[54,56]][[11,27,39,43],[12,24,38,46],[13,21,37,49],[51,53,59,57],[52,56,58,54]][[11,37,39,43],[13,21,59,49],[16,56,54,58],[24,46,38,42],[27,57,51,53]][[12,38,46,42,24],[16,56,52,58,54],[27,37,59],[39,57,49]][[12,56,58,36],[16,54],[24,38,48,52],[27,37,59],[39,57,49],[42,46]][[13,39,43,57,51,49],[16,24,46,38,42,56,54,58],[27,37,59],[36,48]][[13,43,51],[27,37,59]][[14,28,38,48,54,16,56],[22,34,58,36,46,42,24],[27,59,37],[39,49,57]][[16,56,58],[24,38,42],[27,37,59],[39,57,49]][[24,36,56,48],[27,37,59],[38,54,58,46],[39,57,49]][[24,46,38],[27,37,59],[39,57,49],[54,58,56]][[27,39],[36,48],[37,49],[38,46,58,54],[57,59]][[27,59,37],[39,49,57]][[28,54,58],[34,46,38]][[36,38,54],[46,48,58]][[36,58,54],[38,46,48]][[38,58],[46,54]]`
Okay, so strong generating sets aren't all that interesting in themselves - although the last few entries in this one are a little bit interesting, as they show that there are moves which just rotate a pair of corners, or a pair of edges.

Remember though, that SGS allow us to easily calculate the order of a group. In this case:
`> orderSGS \$ sgs [f,b,l,r,u,d]43252003274489856000`
That's about 4 * 10^19 different positions.

The sgs function, to calculate a strong generating set, uses the Schreier-Sims algorithm. I'll probably explain how it works some time, but not just yet.

1. So can you work out the moves that swap a pair of corners or a pair of edges? This is pretty cool!

2. Jeremy,

Yes, you could work out the moves. Roughly, it would go like this:
1. The Schreier-Sims algorithm, which is implemented in the library, but not yet explained in the blog, enables us to obtain what I've called a "tranversal generating set" for the Rubik's cube group.
2. Given a TGS, we can express any group element as a product of elements of the TGS.
3. So the only additional thing we need is to be able to express the elements of the TGS as products of the original generating set {f,b,l,r,u,d}.
To do this, we need a modified version of the Schreier-Sims algorithm which takes (String,Permutation a) pairs, so that it can track (in the String part), how it arrived at the TGS from the original generators.

So we might give it a Rubik cube position, and get told that this is "flffudrllbfrudlrf", for example. I don't currently have code to do this, but it's on my todo list, so watch this space.
(However, I know from the literature that the solutions you find this way tend to be quite long - longer than the optimal solutions - so this may not be a practical way to solve the cube.)