13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ A related question. Close to being duplicate, but leaving the decision to regular users. $\endgroup$ – Jyrki Lahtonen Jan 9 '15 at 6:00
  • $\begingroup$ A quick summary of my thinking. It's not group theory per se, but group theoretic thinking helps immensely. Mostly commutators and conjugation. Admittedly you don't need to be too well versed in group theory to apply that thinking. If you are not afraid of a bit of Finnish, here's is a page I wrote about 20 years ago. My aim was to explain group theoretic thinking in solving the cube to a (very) bright high schooler with bits and pieces about permutation groups behind links. I'm fairly sure that a minute of googling gives you language options. $\endgroup$ – Jyrki Lahtonen Jan 9 '15 at 6:04
  • $\begingroup$ @JyrkiLahtonen: Actually I thought of posting my answer there but decided that it was too narrow a question! That's one of the two questions I was referring to. And yes I forgot to mention about conjugates, which is immensely important. Well I think you've done a very detailed explanation on your webpage but it's not quite readable via Google translate haha.. $\endgroup$ – user21820 Jan 9 '15 at 15:41
14
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @peter: Did my added material help? As a very simple example you can try the commutator $(RT^kR^{-1})B^m(RT^{-k}R^{-1})B^{-m}$ for each $k,m \in \{1,2,3\}$. $\endgroup$ – user21820 Dec 31 '15 at 7:53
  • 1
    $\begingroup$ @Jake1234: It's best to draw a picture. If $A,B$ affect in common the position $x$, then consider the position $y$ that $A$ brings to $x$, and the position $z$ that $B$ brings to $x$. If $x,y,z$ are all different then you get a 3-cycle, because $A$ permutes some elements and brings the element $a$ from $x$ out of its original place, then $B$ brings the element $b$ from $z$ into that place, then undoing $A$ undoes what $A$ did except that now $b$ is pulled back to $y$ and $a$ is brought back to $x$, then undoing $B$ undoes whatever $B$ did except that $a$ is pulled to $z$. [cont] $\endgroup$ – user21820 Jul 9 '16 at 16:55
  • 1
    $\begingroup$ [cont] You can trace the third element that was originally at $y$ too. Now if $A$ does not move the element at $x$ (but perhaps changes its orientation), while $B$ does, then you'll affect only 2 elements. This one is easier to trace because undoing $A$ will undo everything that $A$ did, except that since $B$ changed the element at $x$ the original one will not have its orientation restored and the element now at $x$ will have its orientation changed. Those two are the only elements that will be affected. [cont] $\endgroup$ – user21820 Jul 9 '16 at 17:00
  • 1
    $\begingroup$ [cont] The case I forgot in my post is if both $A$ and $B$ do not move the element at $x$ to another position. If what they do to that single element commutes (order does not matter), then $ABA^{-1}B^{-1}$ will do nothing at all. If not, then only that element will be affected. So either 3,2 or 1 piece will be affected in the most general case. I missed the 1-piece case because all the puzzles I've seen don't have such commutators (you need the group of orientations of that element to be non-commutative). $\endgroup$ – user21820 Jul 9 '16 at 17:05
  • 1
    $\begingroup$ Thanks a lot. As you say, it's best to draw a picture, I see it now. $\endgroup$ – Jake1234 Jul 10 '16 at 5:03
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you mean by "12 3-cycles to solve every non-fixed center and wing edge orbit (one at a time)."? You mean all the pieces in the orbit of size 24, right? If so, you could state that any permutation in $A_n$ can be undone using at most $\lfloor \frac{n}{2} \rfloor$ 3-cycles. I think that this is in fact tight, which would imply that for a 3*3*3 cube with no parity we would really need 10 3-cycles if that is all we are allowed to use. $\endgroup$ – user21820 Jan 11 '15 at 5:57
  • $\begingroup$ "You mean all the pieces in the orbit of size 24, right?" That is correct. I could say at most n/2 3-cycles, but I did compute the exact average number of 3-cycles as well. "I think that this is in fact tight, which would imply that for a 3*3*3 cube with no parity we would really need 10 3-cycles if that is all we are allowed to use." Notice that I mentioned "ignoring corner and middle edge orientations", implying that my results are for permutations only. I can't seem to see that the superflip case, for example, can be solved using fewer than 12 3-cycles. $\endgroup$ – Christopher Mowla Jan 11 '15 at 11:25
  • $\begingroup$ Well, the superflip case technically can be solved using only 5 3-cycles, but we have to use a LONG one: [R2 D2 L2 U2 R' U' B' U' L' D2 R2 D' B D L U L2, u2] [M, U' R2 U] (U2 [M' ,U L2 U'] U2) (F' L' [ E',L D L' ] L F) (R [F, D' S D] R'). Regardless, my post was strictly for moving (not orienting correctly per se) corners and middle edges. Now that I'm thinking about it, I think I could prove the orientation aspect of corners and middle edges without brute force. I'll take a look at this tomorrow. $\endgroup$ – Christopher Mowla Jan 11 '15 at 12:11
  • $\begingroup$ I was indeed referring to position only and not orientation when I said I thought $\lfloor \frac{n}{2} \rfloor$ 3-cycles is tight for permutations in $A_n$. We can't do a 3-cycle on the individual cublet faces so this does not apply to the superflip state. So I don't know what you mean by using 3-cycles to solve the superflip state. If you meant a commutator then it is easy to create a single long one to do it. A flips the 4 top edges and 2 left middle edges, and B turns the whole cube half turn about the front-back axis. $\endgroup$ – user21820 Jan 12 '15 at 13:04
  • $\begingroup$ "We can't do a 3-cycle on the individual cublet faces so this does not apply to the superflip state." You can apply 3-cycles (which are inverses of each other) which each flip two of the three edges they cycle to the same three pieces to ultimately just flip two edges. For example, [M', U' R U][M, D R' D']. (I don't interchange the term "3-cycle" with "commutator".) However, if you were not considering piece orientations, then we have no misunderstanding. Bye the way, why are you mentioning $\left\lfloor {\frac{n}{2}} \right\rfloor$ 3-cycles when you can just say ${\frac{n}{2}}$ 3-cycles? $\endgroup$ – Christopher Mowla Jan 12 '15 at 19:14

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .