On this page I will try to explain some mathematics that applies to the cube, mostly group theory. Along the way we will see how this theory can be used to find a solution to the Rubik's Cube or in fact nearly any other permutation puzzle.

Permutations

Suppose you have the list of numbers 1,2,3,4,5,6,7,8. A permutation of these numbers is simply another list of these numbers in any order, for example 4,2,6,1,3,5,8,7. Every number on the list must be used exactly once.

At first sight this is not related to the cube, but suppose you write down the corner pieces of the cube in a list. Any move on the cube then mixes the corner pieces, and therefore corresponds to a new list with the same corner pieces in a different order. Any move (or move sequence) is therefore a permutation of the corner pieces. Of course, the same can be said of the twelve edge pieces.

By examining what permutations can do, we can therefore examine how the pieces of the cube move. The numbers in our list which we permute are not really important. What is important is how they move. Usually a permutation uses numbers, but these number can represent any items, for example the moving pieces of the cube, or any other objects that can be rearranged. A permutation therefore embodies only the movement of the items.

There are many different ways to write down a permutation. A common way is to write the original list of numbers on one line, and the new list directly below it on another line. For the list of numbers above, we get

1 2 3 4 5 6 7 8
4 2 6 1 3 5 8 7

To make this more visual, we can make a line diagram by drawing straight lines between the lists to show exactly how each item on the list moves.

In this example the lines cross 8 times, so we can say that 8 is its crossing number.

An important aspect of permutations is that they can be combined. On the cube for example one sequence of moves can be followed by another. In other words, the pieces are rearranged in one way, and from that new position they are rearranged in another way. Suppose we combine the permutation above with the following permutation:

Only the movement is important, so even though this second permutation is also written using the numbers 1 to 8, when we combine them, we only look at the lines, i.e. at what movement the permutation indicates. To combine them, we draw the line diagrams one below the other and follow the lines:

By straightening the lines we get:

Lets look at the crossing numbers of these permutations. The first two have crossing numbers 8 and 15. The combined drawing therefore has 15+8=23 crosses but when the lines are straightened, we get a crossing number of 11. If you think of the lines as loose threads, and that you physically untangle them, you will see that each time you uncross two threads, the number of crossings always decreases by 2. When you untangle all the threads, the number of crossings then decreases by a multiple of 2. Therefore, although the final permutation's crossing number is not simply the sum, it will have the same parity as that sum (i.e. will also be even or also be odd). Lets call a permutation odd if its crossing number is odd, and even if its crossing number is even. This is the parity of the permutation.

It is now easy to see that when combining permutations, their parities follow the same rules as numbers: odd+odd=even, even+even=even, odd+even=odd and even+odd=odd.

On the Rubik's Cube, a single quarter turn of a face is an even permutation. To see this, number the corners of the face 1-4 and the edges 5-8. A quarter turn is then represented by the permutation 2,3,4,1,6,7,8,5 which has crossing number 6 if you draw it. Combining even permutations will always give another even permutation, so only even permutations of the pieces of the Rubik's Cube are possible. This shows that it is impossible to swap two pieces (edges or corners) without moving anything else.

Disjoint Cycle Notation

A different but very useful notation for permutations is disjoint cycle notation. In this notation, the first permutation we used becomes (14)(356)(78). This means that 1 moves to the position that 4 was in, and 4 moves to the position that 1 was in. Piece 3 moves to the position that 5 was in, 5 moves to where 6 was, and 6 moves to where 3 used to be. Pieces 7 and 8 swap places just like pieces 1 and 4. Piece 2 does not move because it is not mentioned, although you could state so explicitly by including the 2 like this (14)(2)(356)(78).

Each bracketed part of this is called a cycle. (14) and (78) are 2-cycles, and (356) is a 3-cycle. These cycles are called disjoint because they use different numbers, and so act on different pieces. It is easy to see that the parity of a 2-cycle is odd, and that of a 3-cycle is even. The combined permutation (14)(356)(78) is therefore odd+even+odd=even. In general the parity of an n-cycle will be the parity of n-1 for any number n.

Now that we know the parity of any cycle, there is a beautiful and easy way to prove there is a parity restriction in the classic sliding piece puzzle (i.e. the 14-15 puzzle). List the pieces of the puzzle in the order you visit them if you go in a zig-zag pattern over the board, and simply ignore the space. Thus the solved position in the 4×4 puzzle would have the pieces listed as 1,2,3,4,8,7,6,5,9,10,11,12,15,14,13. Some moves will not change the list at all (for example any horizontal move), while all others (most vertical moves) will be a cycle involving an odd number of pieces. Every move is therefore an even permutation, and so only even permutations of pieces can occur while playing with the puzzle.

The order of a permutation

The order of a permutation is the number of times it has to be performed before the pieces are back to their initial positions. This is where cycle notation is very useful. A 2-cycle is a single swap, so if this is performed twice then the pieces are back where they started. A 2-cycle therefore has order 2. Similarly, a 3-cycle will have order 3, and an n-cycle order n. Now lets consider a permutation like (14)(356)(78) which is composed of several cycles. If it is performed twice, or in fact any even number of times then the 2-cycles will disappear. If it is performed three times or any multiple of three, then the 3-cycle will disappear. If it is performed 6 times, which is a multiple of both 2 and 3 then all the cycles disappear and this permutation therefore has order 6. In general, the order of a permutation is the lowest common multiple of the lengths of the disjoint cycles.

Lets see how this applies to the cube. Consider the move sequence FR. If we look at how this moves the pieces, we see that the UFL corner moves to position RUB, piece RUB moves to position RBD, and so on. In cycle notation this permutation is as follows: (UFL,RUB,RBD,RDF,DLF)(UF,RU,RB,RD,RF,DF,LF) This is a 5-cycle of corners and a 7-cycle of edges. Its order is therefore 35, which means that if you constantly repeat the moves FR on the cube, you will have to do it 35 times before the pieces come back to their original positions. If you try this out on a solved cube you will see that although this is true, the cube is not restored because some corners are twisted. We have only looked at the location of the pieces, and not their orientation.

Groups

The collection of all possible permutations of n items form a group. A group is simply a collection of things (usually called elements of the group) which satisfy various conditions, which I will list below. We use these conditions implicitly whenever we use permutations, so it is best to state them explicitly now.

1. Any two elements of the group can be combined, and this results in another element of the group. As you have seen, two permutations can be combined by performing one after the other, and this will always result in a permutation. If P and Q are permutations, then PQ will mean the permutation resulting from performing first P and then Q. Combining two elements of a group is usually called multiplication of the two elements.
2. There is an identity, i.e. an element I in the group such that for any element P in the group we have PI=IP=P. In a permutation group the element I is simply that permutation that does not move anything.
3. Every element has an inverse, i.e. if P is an element of the group then there is an element Q in the group such that PQ=QP=I. If you mirror the line diagram of a permutation vertically, you get the line diagram of its inverse. A permutation in cycle notation can be inverted just by writing each cycle in reverse. The inverse of permutation P is denoted by P^-1, or by P'. On puzzles, you can do the inverse of a move sequence just by undoing the moves in reverse order, i.e. taking back the moves you did.
4. The multiplication is associative, i.e. if P, Q and R are elements of the group, then (PQ)R=P(QR). With permutations this is obviously true.

If a group is commutative, i.e. if we have PQ=QP for every P, Q in the group then it is called an Abelian group. This phenomenon occurs in the Lights Out puzzle and the Rubik's Clock, and makes these puzzles much simpler because the order in which the moves are performed does not matter. Generally permutation groups occurring in puzzles are not Abelian.

All possible movements of the pieces on the Rubik's cube also form a group, the Cube Group. At first sight this is not a simple permutation group because the orientation of the pieces matters, but you could consider it a permutation group of the 48 moving facelets instead of the 20 moving pieces. On a pedantic note, it is technically incorrect to say that the positions of the Rubik's cube form a group. A position is reached from the solved cube by moving the pieces in some way, and it is those movements that form the group because movements can be combined. On the standard Rubik's Cube this is not a very important distinction, but on other puzzles like the 4x4x4 Cube it is. That puzzle has centre pieces which look the same, and so there are positions which are indistinguishable from each other. Thus different permutations seem to correspond to the same position, or permutations which seem to do nothing in one position will change things in another. The permutations still form a group, but the positions do not (unless you mark the centre pieces so they can be distinguished).

Conjugation

If P and Q are elements of a group, then the conjugate of Q by P is the element PQP'. This is one of the most useful concepts for solving a puzzle like the cube. Lets illustrate this with an example on the Rubik's Cube. Suppose you know that the move sequence Q = R'LF2RL'U2 cycles three edges around, viz. (UB,UF,DF) but that you want to cycle 3 other edges of the cube, for example (UR,UF,UL). We would know how to cycle them if they where placed at UB, UF and DF, so we simply put them there, for example by doing the sequence P = F2U. This sequence moves other pieces as well, but that does not matter. So after we put them in position with P, cycle them with Q, we put everything back by doing P'. The relevant edges will have been cycled as we wanted them to, and any other pieces that were moved by P were put back by P'. Therefore PQP'= F2U R'LF2RL'UF2 cycles just the edges (UR,UF,UL).

As you can see from this example, if you have a sequence that performs a certain task on particular pieces of the puzzle, conjugation will allow you to perform the same task on any other similar pieces of the puzzle instead. So, if you can flip two edge pieces then you can flip any two of them, or if you can twist two corners then you can twist any two of them, and so on.

Commutation

Conjugation allowed you to apply a specific sequence more generally, but you still need to find that specific sequence to begin with. That is where commutation is useful. If P and Q are elements of a group, then PQP'Q' is called a commutator. If P and Q commute (for example they are disjoint, like the moves R and L on the cube) then PQP'Q'=QPP'Q'=QIQ'=QQ'=I. The commutator can be seen as an indication of whether P and Q commute, and by how much. If P and Q are nearly disjoint, then the commutator will move fairly little, and it therefore often performs a useful function when solving a puzzle.

The simplest commutator on the cube uses single face moves for P and Q, for example FR'F'R. This cycles three edges (FU,FR,UR), and two pairs of corners (UFL,BRU) and (URF,RDF). Note that corner UFL moves to BRU, which in turn moves to LUF. This is twisted anti-clockwise compared to the original position FLU, so if we perform this cycle twice, these two pieces will be back to their original positions but will both be twisted anti- clockwise. The other corner 2-cycle of FR'F'R twists clockwise. We could adapt cycle notation to show this as follows:
    FR'F'R = (UFL,BRU)- (URF,RDF)+ (FU,FR,UR)
Doing this twice, we get:
    (FR'F'R)² = (UFL)- (UBR)- (URF)+ (DFR)+ (FU,UR,FR)
Doing this three times, we get:
    (FR'F'R)³ = (UFL,UBR) (URF,DFR)

Theoretically these moves and their conjugates are enough to perform any even permutation on the corners, and any even permutation on the edges. Any single quarter turn of a face is an odd permutation on both corners and edges, so just using what we have so far we could position all the pieces of the Cube. What remains is just to orient them.

Commutation works best when P and Q are nearly disjoint. Therefore lets choose Q to be a turn of the U face, and P so that it affects only a single piece in the U face. An extremely useful choice is the monotwist P = R'DRFDF'. This twists one corner (URF)+ and does not affect anything else in the U layer. The bottom half of the cube is messed up but that does not matter. We now have the following very useful sequences:
  P U P' U' = R'DRFDF' U FD'F'R'D'R U' = (URF)+ (UBR)-
  P U2 P' U2 = R'DRFDF' U2 FD'F'R'D'R U2 = (URF)+ (ULB)-
  P U' P' U = R'DRFDF' U' FD'F'R'D'R U = (URF)+ (UFL)-
You can now twist any two corners on the cube.

Other good choices for P are the monoflip P = FUD'L2U2D2RU = (FU)+, which will allow you to flip any edges on the cube, and P = R'DR which gives you a simple 3-cycle of corners.

It is also productive to let Q be a move of a middle slice, for example R_m. (If you look squarely at the R face of the cube, R_m is a clockwise quarter turn of the middle slice just behind the R layer.) If we let P = F2, which is a monoswap of edges (DF,UF) in the R_m slice, then we get a 3-cycle of edges F2R_mF2R_m' = (DB,DF,UF) and the 4-H pattern F2R_m2F2R_m2 = (DF,UF)(DB,UB). If P = F_m we get the 6-spot pattern, P=F_m2 gives the 4-spot pattern. Another good choice is P = FU'RF'U, a neat monoflip (FU)+.

Size of the group

You may have noticed that when you use a commutator for twisting corners, you will always twist two corners in opposite directions. Commutators can also flip only pairs of edges. It turns out that this is enough to solve the cube because it is impossible for a single piece to be turned.

Every corner piece has one facelet that belongs in the U or the D face. For a corner which has been moved anywhere on the cube, lets define its twist as follows:

• Its twist is 0 if its U/D facelet is in the U or D face.
• Its twist is +1 if the piece has been turned clockwise from the 0 twist orientation.
• Its twist is -1 if the piece has been turned anti-clockwise from the 0 twist orientation.

Twisting a corner clockwise will increase its twist by one. We have to work modulo 3 however, because 3 twists is the same as no twist at all, and so a twist value of +2 is really only a twist of +2-3=-1. Similarly anti-clockwise twisting decreases the twist by one modulo 3 (i.e. a twist of -2 is just a twist of +1).

If you turn the U or the D face, the twist of the corner pieces do not change. If you turn any other face a quarter turn, then the twist of two of the corner pieces increases, and the twist of the other two corners decreases. In any case the total twist of all the corners does not change modulo 3. In the starting position the cube has total twist 0, and this therefore remains 0 however mixed up the cube gets. This shows that it is impossible to twist a single corner in isolation, and that if you twist only two corners then they must go in opposite directions.

A very similar method can be used on the edges; define the flip of an edge as 0 or 1 (modulo 2) and show that the total flip remains 0 whatever move is performed, which means that no edge can be flipped in isolation. Another way is by looking at the permutations of the edge facelets. A quarter turn of a face is an even permutation of the edge facelets (two 4-cycles) so any move sequence will give only even permutations of edge facelets. A single edge flip is an odd permutation of edge facelets and hence not possible without taking the cube apart.

In all we have now seen three restrictions on the possible arrangements of the pieces of the Rubik's Cube. The total corner twist must be zero modulo 3, the total flip of the edges must be zero modulo 2, and the parity of the piece permutation must be even. If you were to take the cube apart and randomly put it back together again, there would be a 1 in 3 chance of having the right corner twist (since all three possible twist values are equally likely). Similarly there is a 1 in 2 chance to get the total edge flip correct, and a 1 in 2 chance of getting the right permutation parity. Putting this together, we find there is a 1 in 12 chance that a randomly assembled cube is solvable.

In a later section on Counting we shall count how many randomly assembled cubes there are. The actual number of cube positions is then one twelfth of that.

Subgroups

The Rubik's cube group is generated by the moves {F, B, R, L, U, D}, because by definition any movement of the pieces is done by moving the faces one at a time. Suppose instead that from a solved cube you only do half turns, i.e. you only use the moves {F2, B2, R2, L2, U2, D2}. Clearly this does not generate the whole cube group; for a start each face of the cube never has more than two colours. Nevertheless, the permutations these moves generate do form a group because any two permutations made from half turns will combine to give another permutation made from half turns. This group is usually called the Square Group.

The Square group is called a subgroup of the Cube Group, because it is a subset of it and is a group in its own right. Of the four conditions listed earlier that define a group, we only need to check the first one - that combining two permutations of the square group also gives a position that can be solved using only square moves. The other three conditions are inherited automatically from the full cube group.

There are many pretty patterns in the square group, and no doubt you already know some of them. The 4-spot pattern for example can be made by R2L2U2R2B2R2L2F2L2U2, which is 10 half turns. It can be reached in fewer turns if you allow the cube to temporarily leave the square group by using quarter turns. The 4-spot can be reached in 8 turns by R2L2UD'F2B2UD'.

There are other interesting subgroups of the Cube Group, for example the slice group (generated by all slice moves: FB', RL', UD'), the antislice group (generated by all antislice moves: FB, RL, UD), and many others.

It is a strange fact that you only need 5 faces to solve the cube. In other words, {F, B, R, L, U} generates the whole Cube Group. If you know how to solve the cube layer by layer, it is fairly easy to do it without turning the first layer at all. It is therefore fairly obvious that you can solve the position with just the first layer rotated without using any turns of that layer. So one face can be turned by using only the other five. A simple way to prove it is by means of the sequence P = R2L2U2R2B2R2L2F2L2U2, which does the 4-spot. It moves all the pieces from the D layer to the U layer in the same relative positions without actually turning the D layer, so that PUP' has the same effect as D. The same reasoning shows that the whole square group is also generated by just 5 faces.

Not all subgroups are generated by a restricted set of cube moves. In fact most subgroups are better described by the effects of its permutations on the cube. For example, consider all permutations that do not move the UFR corner. It is fairly easy to show that these form a group - any combination of such permutations still doesn't move that corner. A much used subgroup is the U-group - the set of all permutations that only move pieces in the U layer, and leave the bottom two layers intact. A lot of research has been done to find short move sequences for these permutations so that solving the last layer can be done as fast as possible.

Centre

One particular subgroup that is fascinating is the centre of the Cube Group. The centre of a group consists of all elements which commute with everything, i.e. if C lies in the centre, then CP=PC for all elements P in the group. Since CP=PC means that PCP'=C, the element C does not change under any conjugation. The only way for this to be true is if it does not move any piece from its place. Also, if C twists one corner, then by conjugation it must twist all corners in the same direction which is not possible on the cube. Similarly, if it flips one edge then it must flip all of them, but this is possible on the cube. The only elements in the centre are therefore the identity I and the Superflip which flips all 12 edges.

The superflip can be done by the sequence: [(R_mU)⁴ R_cD_c]³. This rather cryptic sequence will need a little explanation. The notation R_m is used to denote a move of the middle slice adjacent to the R face in clockwise direction if you look at it from the R side. You have to do R_mU four times. Now you have to do R_cD_c which are rotations of the whole cube in the same directions as the moves R and D (these two cube rotations together are the equivalent of a rotation about the UFL corner). Now you have to repeat everything you have done so far twice more (3 times all together).

The fact that the Superflip commutes with everything can be used for some impressive tricks. Suppose you apparently mix the cube up, but actually perform the Superflip (S). You hand the cube to someone and ask them to do one or two random moves (P) and then hand it to you behind your back. You have not seen which moves he did, nor which way up the cube is handed to you, and yet you seem to solve it behind your back. Simply perform the Superflip again, and bring it out to the front while you say that you are nearly finished. The cube will only need one or two moves to be solved which can be done instantly by sight. This works because SPS = SSP = IP = P so you only need to undo the few random moves that the cube was given.

I explained the above trick to the wonderfully clever magician Jerry Sadowitz, and he very quickly came up with the following idea based on this. You show two Rubik's Cubes, both of which are mixed up differently. You ask someone to mix the cubes further, as long as every move that is performed on one is also performed on the other. You do not see these moves, and yet when you are handed either one of these cubes behind your back, then without even seeing the other cube you can mix yours so that it is the same as the other one. You should be able to figure out how this works now.

Supergroup

On the Rubik's Cube the centre pieces of each face do not change position, but they do rotate. On a normal cube this is not visible, but there are cubes with pictures or other designs on them where the orientation of the face centres does matter. Each quarter turn is an odd permutation on the corners of the cube (and also odd on the edges), so it is impossible for a face centre to move a quarter turn without any other pieces moving. It is possible however for a single centre to do a half turn in isolation, or for two centres to do a quarter turn without other pieces moving. The group of all permutations of a cube with visible centres is called the supergroup. It is 4⁶/2 = 2048 times as large as the normal cube group.

We already saw that (FR)³⁵ leaves the pieces in the same position, but twists some corners. Doing this three times, i.e. (FR)¹⁰⁵, will therefore not move any pieces. It does however turn the F and R face centres 105 times, so it leaves them both twisted by a quarter turn. Many other move sequences have an order (in the normal cube group) that is not a multiple of 4, and they will usually cause centres to be twisted when repeated. These methods are not really practical however.

By using commutators it is not very hard to find shorter move sequences for twisting the face centres. For example let P be the 6-spot pattern (e.g. R_mF_mR_m'F_m') and Q a face turn (e.g. U). The result is then a sequence which turns one face centre clockwise, and an adjacent face centre in the opposite direction. The sequence RL'FB'UD'R'U'DF'BR'LU which turns centres U and R' is derived that way. For opposite faces you could use the 4-spot instead, and this gives RL'F2B2RL'URL'F2B2RL'D' which turns U and D' centres. A short sequence for a half turn of a face centre is more difficult to find. Let P be the sequence RLU2R'L'U2. This swaps one pair of opposite corners and one pair of opposite edges in the U layer. Commuting it with U therefore gives you a sequence which has the same effect as U2 on the corners and edges, but which does not move the U centre. Follow it with U2 and you have only moved the U centre. Thus (RLU2R'L'U)² will move the centre U2.

Metrics

It would be nice if we could measure how far away a cube is from being solved. If we could do this perfectly, we would be able to solve the cube in the quickest possible way simply by doing any move that brings it closer to the solved position. This quickest way is usually called God's Algorithm. It is of course not so simple to measure distances on the cube. In mathematics, a measure of some kind of distance between two points is called a metric. A metric D is a function which should satisfy a few fairly obvious conditions:

1. D(a,b)>=0, or any distance is positive or 0.
2. D(a,b)=D(b,a), or the distance from a to b is the same as from b to a.
3. D(a,b)=0 if and only if b=a, or distances between differing points are always non-zero, and the distance from one point to itself is always zero.
4. D(a,b)+D(b,c)>=D(a,c), also called the triangle inequality, means that if you go from a to c, the distance can only get longer if you detour via b.

On a cube, a reasonable metric would be the minimal number of moves to get from one position to the other. You can check that the conditions above are true, provided that the inverse of a single move is also considered a single move.

There are however several different opinions as to what constitutes a single move. Some people prefer the Quarter Turn Metric (QTM), i.e. only a quarter turn (in either direction) of a face is considered a single move, while other people use the Half Turn Metric (HTM) in which half turns are also considered to be a single move (this is also called the Face Turn Metric, and is often denoted by q+h). For example the Pons Asinorum or the 6X pattern reached by the sequence U2D2F2B2R2L2 is 12 moves from start in QTM but 6 moves in HTM. Some people even consider a slice move as a single move, and in this Slice Move Metric (SMM) the Pons would be only 3 moves from start.

The example of the 6X pattern above works only because it is known that it cannot be reached by a shorter route in any of the metrics used here. To prove this for the QTM, consider that each of the 12 edges needs 4 quarter turns to get into position, each move only moves 4 edges, and so you need at least 12 moves to reach/solve the 6X position.

Generally if you look at a move sequence, counting the number of moves in the sequence will only give you an upper bound for its distance from start. There may well be a shorter, more direct sequence. You can even prove this obvious result by using the triangle inequality.

God's Algorithm

God's Algorithm of a puzzle is the solving algorithm that solves it in the fewest number of moves from any position. In other words, from any position of the puzzle the algorithm gives a move that brings it closer to the starting position. Note that closeness is measured by a metric, which depends on exactly what is considered to be a single move. At the moment this algorithm is not known for the Rubik's Cube, but for several smaller puzzles like the Skewb, the Pyraminx, the Diamond, and the 2x2x2 Cube it is known.

It is usually calculated by computer as follows:

1. Set up a large array with entries for every possible position of the puzzle.
2. Mark the solved position (or positions) as being at distance 0.
3. If all positions of distance <=L are known, then those at distance L+1 can be found like this: For each position at distance L, try all possible moves. If an unknown position is reached, then that must be at distance L+1.
4. Repeat step 3 until all positions have known distance.

This method requires a lot of memory, at least 2 bits for each possible position, so it is not practical for the Rubik's Cube and is not likely to be in the near future. See Computer Puzzling for more details on how to calculate this in general.

We can however find some simple lower bounds for God's Algorithm for the Rubik's Cube. Suppose we begin from a solved cube, and try to count how many positions that can be reached in a certain number of moves (HTM). There are 6·3=18 choices for the first move. We can assume we don't move the same face twice in succession, so there are 5·3=15 choices for the second move, and the same for each subsequent one. The total number of positions that can be reached in n moves is therefore at most
      1+18+18·15+18·15²+18·15³+....+18·15^n-1
This is of course an overestimate, because many positions can be reached in several ways. This number first exceeds the total number of positions the cube has when n=17, so there are positions which need at least 17 moves to solve. A better counting argument that takes into account that RL=LR etc., gives n=18.

If we use the QTM, then the same argument gives as an upper bound on the number of positions reachable after n moves:
      1+12+12·11+12·11²+12·11³+....+12·11^n-1
Here we get n=19, but this can be much improved because it does not take into account that no more than 2 consecutive quarter turns of the same face is ever done. The best calculations show that some positions require at least 21 quarter turns.

These lower bounds have been improved upon, mostly by computer searches, by showing that certain positions need more moves to be solved. The superflip for example has been shown to need at least 20 moves in HTM, or at least 24 moves in QTM. The position reached by combining the 4-spot pattern and the superflip needs at least 26 moves in QTM.

Every algorithm that can solve the cube will take longer than God's algorithm, and therefore we have upper bounds for God's algorithm too. It has been verified that it takes at most 20 moves in HTM and 26 moves in QTM. These methods involve large computer databases and are not practical for humans.

Thus God's algorithm has a maximum length of 20 in HTM and 26 in QTM.

Counting

It often happens that you want to find out how many positions a particular puzzle has. This can be tricky, but the difficulty mainly lies in determining the restrictions, such as parity restrictions or twist restrictions that we saw earlier. Apart from those, it is possible to count the number of positions is of a puzzle by imagining it taken apart, and counting the number of possible ways to put it together. To do this, we need to count the number of orientations, permutations, and combinations.

The number of orientations

Suppose you are assembling a Rubik's cube, and are inserting a corner piece. Wherever you put it, it has three possible orientations. You have this choice of three orientations for each of the eight pieces, and the total number of possibilities is multiplied by 3 for every corner you place. The total number of orientations for the corners is therefore 3⁸ = 6561. As we have seen before there is a constraint (the total twist should be zero), so for the resulting position to be solvable we need the orientation of the last corner to be consistent with that of the other seven. There are therefore really only 3⁷ = 2187 possible corner orientations.

The number of edge orientations is calculated in much the same way. There are twelve edges, each with 2 possible orientations, so at first sight there must be 2¹² = 4096 possibilities. Again there is a constraint so that the orientation of the last placed piece is dependent on that of the others in solvable cubes, so there are really only 2¹¹ = 2048 edge orientations.

Some puzzles do intrinsically have a constraint on the orientations, but also have some pieces of which the orientation is not visible. The best known example is the Pyramorphix. It is essentially a 2×2×2 cube, and half the pieces have no visible orientation. In this case you can still count the orientations of the normal pieces (giving 3⁴ orientations). The zero-twist constraint has no effect however, since you can simply imagine putting one of the monochrome pieces in last when you are assembling it so that it will automatically be solvable whichever way that piece is oriented. Generally, any puzzle where there is at least one piece without visible orientation will effectively have no constraint on the orientations of that type of piece.

The number of permutations

Again, let's suppose you are assembling a Rubik's cube, and are inserting all twelve edge pieces one by one. For the first edge there are 12 possible places to put it, for the next there are 11 possibilities left, for the third only 10, and so on until the last edge which goes into the last remaining empty spot. The total number of arrangements is therefore 12·11·10·...·2·1, also called 12 factorial, and which is usually written as 12!.

The corner permutations can be counted in the same way, so there are 8! of them. In general, there are n! ways of permuting of n items.

It is occasionally useful to know how many ways there are to place r pieces amongst n places where r<n. For example, how many ways are there for the U layer edges to be arranged on a mixed cube? This is calculated in the same way as before, except that you stop after the four pieces have been placed. In this case you get 12·11·10·9, which can also be written as 12!/8!. On scientific calculators this is denoted as nPr, which means n!/(n-r)!.

Once again on the Rubik's Cube there is a constraint, due to the permutation parity. The parity of the permutation of all 20 pieces (corners and edges) must be even for the cube position to be solvable. This means that the last two pieces you place (whether they are two edges or two corners) must be positioned in such a way as to make the permutation of even parity. This is possible because swapping them changes the parity from odd to even and vice versa. Therefore the actual number of solvable permutations is half the total number of permutations.

We can now get the number of solvable cube positions by multiplying together all these numbers: 3⁷·2¹¹·8!·12!/2 = 43,252,003,274,489,856,000. This is therefore also the size of the cube group. The total number of possible positions attainable by taking apart and re-assembling it is 12 times this number. From the discussion about conjugation and commutation you can prove that all of these positions can indeed be reached (and solved).

The number of combinations

There are some puzzles which have identical pieces, for example the centre pieces of the 4×4×4 cube. Swapping centre pieces of the same colour is possible, and this does not change what the puzzle looks like. Suppose you gave the four centres of one face markings to distinguish them. These four pieces can be rearranged amongst themselves in 4! distinct ways, but if you remove the markings, all of these positions are identical. The same can be done for each of the six faces. The total number of ways the 24 centre pieces can be arranged is therefore 24!/4!⁶.

We can come to the same conclusion in a different way too, by counting each colour separately. How many ways are there for the U face centres to be arranged on a mixed cube? If they were all distinct then there would be 24!/20! = 24·23·22·21 ways to arrange them. Since they look the same, we must divide by 4! to get 24!/(20!·4!). This is the number of ways to place 4 identical items amongst 24 locations, or alternatively the number of ways of choosing 4 locations out of 24. It is often called '24 choose 4'. The general formula for 'n choose r' is n!/(r!·(n-r)!), and on scientific calculators it is denoted nCr.

The total number of 4×4×4 centre piece arrangements can now be calculated by doing the centres one set at a time. The first four have 24!/(20!·4!) arrangements. The next four can be placed at any of the remaining 20 places in 20!/(16!·4!) ways, the four after that in 16!/(12!·4!), and so on. Multiplying all these together and simplifying gives the same answer as before, namely 24!/4!⁶.

If there are identical pieces, then any permutation parity constraints on those pieces have no effect, at least not on the number of positions. This is simply because swapping two identical pieces would change the parity without changing the position. It is in fact precisely this effect which can cause confusion when solving such a puzzle - to swap two distinct pieces you will have to swap two identical pieces as well if there is a parity constraint.

Burnside's Lemma

Burnside's Lemma is also called the Pólya-Burnside Lemma, the Cauchy-Frobenius Lemma, or even "the lemma that is not Burnside's". It can be used for counting the number of positions of a puzzle when some of them are considered to be equal due to the fact that the puzzle is symmetric in some way. I have hardly used this on my pages at all, though in some cases I could and should have. Let me first give a simple example where it can be used.

Suppose you have a square, and each of the sides is coloured either red or blue. How many of such distinct squares are there? Here it is easy to just count them; all sides the same colour (red or blue), 3 sides of one colour and 1 of the other (again two possibilities), 2 sides of one colour and 2 of the other (adjacent or opposing). There are therefore 6 such squares.

In more difficult cases there are too many to just count them like that. You could then calculate how many there might be (here we would get 16 because each of the 4 sides has 2 possibilities, red or blue), and then see which of these are symmetric and how many times too often they have been counted. Burnside's Lemma actually does something like this.

The lemma states in mathematical terms that if G is a finite group acting on a finite set X, then the number of orbits under this action is given by taking the average number of the fixed points. In our example, the set X is simply all possible squares ignoring symmetries (i.e. all 16), the group G is all different ways we can rotate/reflect the squares, and each orbit is a complete set of squares which are the same under rotation/reflection. The number of orbits, which is what the Lemma calculates, is therefore the number of distinct squares when rotation/reflection is taken into account.

Let's calculate it now. First we must find all the symmetries of the square, i.e. all ways of rotating or reflecting it. These are:

1. Rotation through 90 degrees.
2. Rotation through 180 degrees.
3. Rotation through 270 degrees.
4. Reflection through the horizontal midline.
5. Reflection through the vertical midline.
6. Reflection through one diagonal.
7. Reflection through the other diagonal.
8. The identity.

We must include the identity (rotation through 0 degrees if you like) because we need to use the whole group of symmetries, and groups always have an identity element. Note that the pairs A and C are similar, as are D and E, and also F and G.

Now we have to count the number of 'fixed points' that each symmetry has, in other words how many of the 16 possible squares remain unchanged by each symmetry. A square can only remain the same under a 90 degree rotation if all its sides have the same colour. Therefore symmetry A has exactly two 'fixed points', and so does symmetry C.

Symmetry B has 4 'fixed points', because we must have opposite sides of the square the same colour, and each pair of opposite sides can be either colour. Note that this also includes the squares of one colour that we had with symmetry A and C. Symmetries F and G each also have 4 'fixed points', D and E have 8, and finally H has 16 because all squares remain the same if you do nothing to it.

The average of these 8 numbers is therefore (2+4+2+8+8+4+4+16)/8 = 6, as we expected.

Let's now try to apply the Lemma to a real puzzle. It could be applied to count the number of shapes of the Pyramorphix, but they are much easier to count by hand. Instead, lets count the number of distinct patterns on an Orbix puzzle. This is much like the earlier example, but now we have a dodecahedron with coloured faces instead of a square with coloured sides.

To make things a bit easier we will only look at rotations, so patterns that are mirror images of each other will still be considered different. There are four types of rotational symmetries:

1. Rotations around a face by a multiple of 1/5 of a turn.
2. Rotations around a corner by a multiple of 1/3 of a turn.
3. Rotations around an edge by a 1/2 of a turn.
4. The identity.

There are 6 axes through the faces, so 6 axes about which rotation A can take place. Note that a 2/5 turn will keep the same patterns unchanged as a 1/5 turn, because doing it three times give a 3*2/5 = 6/5 turn which has the same effect. Therefore all 6*4 = 24 type A rotations keep the same positions fixed. Under such a rotation, the faces move in two 5-cycles, and two 1-cycles. Each cycle must be all the same colour, so there are 2⁴=16 fixed points for these rotations. Similarly the 20 B rotations have 2⁴ fixed points, the 15 C rotations have 2⁶, and finally the identity has 2¹² fixed points.

The average is therefore (24·2⁴ + 20·2⁴ + 15·2⁶ + 2¹²) / (24+20+15+1) = 96. There are 96 distinct Orbix positions (if mirror images are counted as well).

If you do the same thing for all mirror symmetries (easiest to use a point reflection through the centre of the dodecahedron followed by any normal rotation) then you get the result (24·2⁴ + 20·2⁴ + 15·2⁶ + 2¹² + 24·2² + 20·2² + 15·2⁸ + 2⁶) / 120 = 82.
This means there are 82 positions if mirror images are considered the same, and therefore there are 96-82 = 14 pairs of positions that are mirror images of each other.

Burnside's Lemma can also be applied to the Rubik's cube. Whereas normally there are 12 positions that are a quarter turn from being solved, these are essentially the same. By applying the lemma, we find that there are only 901,083,404,981,813,616 essentially different positions.