Solving Rubik's cube and other permutation puzzles

Question

I've seen two questions on solving the Rubik's cube but none of the answers have given a complete solution using mainly mathematical techniques. Furthermore, I've not seen a good explanation of general techniques for solving permutation puzzles in general, including those of the Rubik's cube family, without involving any memorized move sequences. So I've decided to write up my method below as an example of how group theory can be applied to solving such puzzles.

Answer 1

Here is a practical solution based on elementary group theory that can be used to solve many permutation puzzles.

In many puzzles, there are two properties for each piece. It has a position and it has an orientation. A piece may be in the right position but wrong orientation. Later when I refer to permutations such as cycles, it refers to the permutations of positions. It is usually the case that the same permutation of pieces can be achieved with different resulting orientations.

The first ingredient is called a commutator. A commutator is any sequence of moves of the form $ABA^{-1}B^{-1}$ where $A,B$ are some sequence of moves. $X^{-1}$ denotes the inverse of $X$ as usual. Most commutators are useless for practical solutions of a puzzle. But if you find $A,B$ such that there is only one position at which both of them will affect the piece there if executed, then $ABA^{-1}B^{-1}$ will affect the pieces at exactly 2 or 3 positions only, regardless of how complicated each of $A,B$ is. If it affects 2 positions, only the orientations of those pieces will change. If it affects 3 positions, those pieces will be permuted in a 3-cycle. You can easily prove this fact by analyzing what happens to all the pieces. It is up to you to figure out how to construct and utilize such commutators to create useful sequences. For most puzzles, enough 3-cycles can be constructed to enable all alternating permutations to be performed.

The second ingredient is called a conjugate. A conjugate is a sequence of moves of the form $ABA^{-1}$ for some move sequences $A,B$. $ABA^{-1}$ will do exactly what $B$ does but on a different set of positions. A conjugate is useful when we can use some moves $A$ to 'set up' 3 pieces in some positions where a 3-cycle commutator can be used to permute them in the desired way so that when the 'set up' is undone via $A^{-1}$ the 3 pieces will go back to their original positions but permuted among those positions.

The third ingredient is called parity. Using commutators cannot solve all possible states of permutation puzzles. This is because every commutator is an even permutation, and so it is impossible to swap only two pieces using only commutators. Also, since most puzzles have pieces of different types, and each piece can only be moved to a position that is of the same type, it means that for each type there may be a parity issue, meaning that it is impossible to put all the pieces of that type in their correct positions using only 3-cycles. The number of parity issues will of course be at most the number of piece types, and it is easy to determine quickly whether there is a parity issue for any given type by counting the number of even cycles in those pieces (equivalent to finding the sign of the permutation).

So the general recipe for a mathematical solution to permutation puzzles is:

1. Identify and fix all the parity issues. Usually this can be done one piece type at a time, each of which usually takes very few moves. For example for the $5 \times 5 \times 5$ Rubik's cube there are 2 parities (1 for corner pieces and middle edges, 1 for the side edges) and each takes only 1 move to fix (face quarter turn for the first, slice quarter turn for the second, because each of these do a 4-cycle on the pieces of the corresponding types).

2. Once all the parity issues are fixed, it is usually easy to put all the pieces in the right positions using 3-cycle commutators with the help of conjugates, and then correct the pieces' orientations using 2-position commutators (with conjugates). To speed up the solution, one should try to perform 3-cycles such that the pieces end up not only in the desired locations but with the correct orientations. So in general one does each 3-cycle to move 2 pieces to the correct position and orientation, while the third is ignored. Sometimes only 1 piece can be settled (when there are only swaps). Either way the number of pieces in the wrong position will decrease with each 3-cycle until all are in the correct positions. This fact about alternating groups can be proven very easily. For a Rubik's cube, it takes 8 to 10 moves (counting slice turn as 1 move) to do most 3-cycles, including getting the desired orientations for 2 pieces.

In case of puzzles where some moves can be physically blocked depending on the state of the puzzle (such as the Square-1), it may be a good idea to get the puzzle into a nice state (meaning an element of some nice subgroup) and develop a solution based on the above only for nice states. I don't have a Square-1 so I don't know how easy it is to solve it this way.

The above method works very well for a Rubik's cube of any size, as well as permutation puzzles that are closely related to the Rubik's cube. Basically puzzles where 3-cycle commutators are easy to construct are completely not a challenge. There are some nasty puzzles like Tatham's Twiddle (rotating 4x4 blocks) where it is difficult to find 3-cycle commutators. Generally my strategy to tackle such puzzles would be to find commutators that affect few pieces and compose them so as to affect fewer and fewer pieces. Eventually I would find a 3-cycle commutator (unless there are none), and then I can solve the puzzle by using conjugates to bring other pieces to the positions on which the commutator works so that they can be permuted. It is possible that parity issues make a single commutator insufficient, so some ad-hoc analysis is still necessary.

Specific method for the $\boldsymbol{n \times n \times n}$ Rubik's cube and close relatives

The first step is to find 3-cycle commutators. For the Rubik's cube the easiest commutators $ABA^{-1}B^{-1}$ are where $B$ is a single face/slice turn and $A$ is some sequence of moves that shifts only one piece in that face/slice. $A,B$ can be chosen easily for many desired 3-cycles as follows. Given a piece $x$ which can be shifted into place including orientation in only one face/slice turn, choose any $A$ that shifts $x$ out of that face/slice $S$. It is easy to see that, after doing $A$ you can make a single face/slice turn $B$ such that, when you undo $A$, $x$ would go into the correct place with respect to $S$, and then after undoing $B$, $x$ would be in the correct place with respect to the whole cube. Since the original position of $x$ would now be occupied by some piece that was shifted there by $A$, it means that if you choose $A$ carefully you can pull in the correct piece (the one belonging to the original position of $x$) with the correct orientation while pushing $x$ out of $S$, as long as that correct piece was originally not in $S$. If not, then just pull in some unsolved piece.

If there are no pieces that can be shifted into place by a single face/slice turn, this is where conjugates come in. If we want to shift a piece $x$ into position $p$, find some sequence of moves $C$ that does not shift the piece currently at $p$ but shifts $x$ into a position from which it can be shifted into $p$ with correct orientation in one face/slice. Then one can now perform 3-cycle commutators that shift $x$ into $p$ as described earlier. Finally we undo $C$. It is not hard to see that $C$ is just a perspective change, and so the whole sequence $CABA^{-1}B^{-1}C^{-1}$ is also a 3-cycle. With a little bit of practice it becomes easy to mentally track the perspective change so that we can choose the appropriate $A$ to pull in the correct piece that would go into the right place with respect to the changed perspective, so that it would be in the right place after undoing $C$.

With these 3-cycles you can solve 2 pieces (including orientation) at a time, unless every unsolved piece is in a 2-cycle or is in the right position but is in the wrong orientation. If there are still 2-cycles you just solve 1 piece at a time. If every unsolved piece is wrongly oriented, you can either mess them up and putting them back correctly using 3-cycles, or you can use the 2-cycle commutators.

A 2-cycle commutator $ABA^{-1}B^{-1}$ that orients pieces $x,y$ that are both in the same face/slice $S$ can be found as follows. Choose $A$ to be a sequence of moves that orients $x$ correctly but does not shift any other piece in $S$. Then it is clear that if you do $A$ and then a single face/slice turn $B$ to bring $y$ to the position of $x$, then undoing $A$ would perform the opposite orientation to $y$ which would be brought back to its original position after undoing $B$. Together with a conjugate, this allows us to twist any two pieces of the same type at the same time 'in opposite directions'.

Once you are comfortable with the above commutators, you can easily extend the idea to 3-cycles of groups of pieces, such as pairs or larger blocks. These are not useful in solving a Rubik's cube from a random state, but are very useful when creating patterns from the solved state.

Efficient method for the $\boldsymbol{3 \times 3 \times 3}$ Rubik's cube

The above method works for Rubik's cubes of any size as well as closely related puzzles, but of course the cube structure yields more efficient methods. Here is a simple one that is still partly based on group theory but quite ad-hoc, even though everything makes sense and so does not require any memory work.

First solve the bottom edges. Then solve 3 of the bottom corners (without messing up the bottom edges). Now solve 3 of the side edges; for each of them turn the bottom face so that the unsolved bottom corner is below the desired side edge position, and then it is easy to pull the edge piece in with the correct orientation without messing up the bottom face except for the unsolved corner. Of course it may sometimes be necessary to push side edge pieces to the top face before pulling them into the right place. Now we have 5 edges and 5 corners left.

Next we shall orient the 5 edges. Turn the bottom face to align the unsolved bottom corner and side edge, and turn the cube so that you can see the faces on their left and right as well as the top face. Let $L,R,T$ be clockwise quarter turns of those faces. Using only move sequences of the form $T^kL^{-1}T^mL$ and $T^kRT^mR^{-1}$ you will be able to orient all top edges, meaning that any top edge that is on the top face is oriented with top colour facing up. Note that either $L^{-1}$ or $R$ will not make any top edge have wrong orientation. Say it is $R$. We now temporarily restrict ourselves to moves using only $R,T$; by staying in this subgroup, the edges will keep their correct orientations.

Then we shall fix the parity issues so that we can finish with commutators of some kind. Since the edge parity is linked to the corner parity, we just have to determine the parity of the edge pieces. If it is an even permutation (even number of cycles) then we do nothing, otherwise we just perform a $T$ to make it even.

Based on the orientation of the edge piece in the side edge position, restrict yourself to move sequences of the form $T^kRT^{-k+m}R^{-1}T^{-m}$ only. Each of them is actually a 3-cycle commutator (conjugated) on the 5 edges (pretending that there are no corner pieces at all). Since orientation is automatic, you need at most 2 commutators to solve all 5. Also, using these sequences ensures that the pieces solved earlier are not disturbed. In practice of course the $T$s in-between the commutators will cancel out.

Finally we can turn the bottom face again to put the pieces in their proper places and we will have only 5 corners left, so we simply use commutators without any restriction on the type of moves. This usually takes 2 or 3 commutators. There are ways to optimize this part but that is left for the reader to discover.

Notice that throughout this method, the underlying principle is that we leave enough unsolved pieces around so that we can solve other pieces efficiently. It turns out that on average this method takes 60 to 70 moves, which is almost as efficient as conventional memorization-based methods that usually involve more than 50 black-box algorithms, yet providing intuitive understanding for every single move, and with a bit of practice (and finger tricks) anyone using this method should be able to reach below 35 seconds consistently.

Answer 2

May I add that if anyone wondered about the maximum number of 3-cycles required to solve/generate any even permutation of any $n\times n\times n$ Rubik's cube orbit of pieces (ignoring corner and middle edge orientations), I get that it takes a maximum of:

• 12 3-cycles to solve every non-fixed center and wing edge orbit (one at a time).
  • The exact average number of 3-cycles needed to solve all $24!/2$ even permutation cases of 24 objects is $7272437897/669278610$ (about 10.87).
• For middle edges (12 objects), a maximum of 6 3-cycles is required.
  • The exact average number of 3-cycles to handle all $12!/2$ even permutations is 34757/6930 which is about 5.02.
• For corners (8 objects), a maximum 4 3-cycles is required.
  • The exact average number of 3-cycles to handle all 8!/2 even permutations is 649/210 which is about 3.09.

All of these calculations include the solved case (which obviously is an even permutation and is included in the k!/2 quantities).

For everyone's possible curiosity, this means that it takes a maximum of this number or an average of this number of 3-cycles to solve the $n\times n\times x\times n$ cube. (Just substitute an integer which corresponds to the cube size for k at the right of the input in Wolfram Alpha.)

That is, the maximum number of 3-cycles function to solve the $n\times n\times n$ supercube (where we ignore the twists of fixed centers on the odd $n\times n\times n$ supercube, and non-fixed centers are unique) is simply $3n^2 - 6n + \frac{{3\cos \left( {n\pi } \right) + 5}}{2}$.

Suppose that we use 3-cycles which are 10 moves in length. This means that it should take about (8)(10) = 80 moves to solve the 3x3x3 on average using this approach (where the "solved" state will be one in which corners and middle edges will most likely be unoriented), and about (10)(26635) = 266,350 moves on average to solve the 100x100x100. We of course apply at most Floor[n/2] slice quarter turns to get the nxnxn supercube into the nxnxn supercube commutator subgroup, and thus we add this term to our total number of estimated moves.

Clearly since these calculations are for the $n\times n\times n$ supercube, the actual maximum number of required 3-cycles to solve the regular 6 colored $n\times n\times n$ cube is most likely less, although doing such a calculation would require a much more involved brute force search than the one I did for these supercube calculations.