solvethecube.co.uk

What are commutators?

In this context, commutators are special algorithms. They are algorithms that are built up in a special way. And because of the way commutators are built, they have some nice properties. If you understand how they work, you can often find your own commutators that will enable you to solve a lot of different puzzles. Before I give the defenition of a commutator, first you have to know something else...

The inverse of an algorithm

As you probably know by now, an algorithm is a sequence of moves. The inverse of an algorithm is the same sequence of moves, but in reverse order, and every move is negated. For example: the inverse of R U D' is D U' R'. We can give these algorithms names. If we define P = R U D', we can write down the inverse of P as: P^-1 = D U' R'. Notice that executing PP^-1 on a solved cube will result in a solved cube: P^-1 will undo the moves of P.

In mathmatics, the rule for calculating inverses this way is sometimes called the sock-and-shoe rule. This is because we put our socks on before our shoes, and we take them off in the reverse order.

Definition of a commutator

If P and Q are algorithms, the commutator of P and Q is: PQP^-1Q^-1. So first execute P, then execute Q, then 'undo' P and 'undo' Q. This means that you can make an unlimited amount of commutators. Of course, most of these commutators will not be very usefull for solving your puzzle. To find useful commutators, I think it's usefull to know something about permutations first.

Permutations

Ok, the next two parts are somewhat mathematical. I recommend reading it because it will give you a deeper understanding of how commutators work, but you can also skip it and progress to: Cycling three pieces on the cube.

In the applet above, you can see an algorithm P = RBLF U F'L'B'R' U' that results in a three cycle. If we label the positions of the pieces with numbers, we can write this as: P = (123), which means: the piece in position 1 goes to position 2. The piece in position 2 goes to position 3. And last but not least: The piece in position 3 goes to position 1. Notice that (123) means exactly the same as (231) or (312). At this point, it's not important how the pieces are labeled. Just try to understand the theory here. Suppose we have another algorithm Q = (345), that results in another three cycle. Now, what would PQ result in? We can write this as PQ = (123)(345) = (12453). The result will be a five cycle.

The way to calculate this result is as follows: We start with the first number in the first cycle: 1. So we write: (1. Then we see 1 --> 2. But before writing 2, first check in the second cycle what happens to 2! In this case noting, so we can write: (12. Now we see 2 --> 3 in the first cycle, but before writing 3, we see 3 --> 4 in the second cycle! So we can write (124. Nothing happens to 4 in the first cycle, but in the second cycle 4 --> 5. So we can write: (1245. Nothing happens to 5 in the first cycle, but in the second cycle 5 --> 3. So we can write: (12453. Then we see 3 --> 1, so this must be the end of the cycle. Thus, the result is: (12453).

Notice that (123)(345) means the same as (12453), but in the second notation, all the cycles (in this case just 1) are disjoint: they don't have any numbers in common. We call this notation the disjoint cycle notation of a permutation.

A few more examples of calculations with permutations:

(12)(23) = (132) = (321)
(123)(325)(613) = (156)
(12345)(54321) = (12345)(12345)^-1 = (1) = id

In the last example, id means 'the identity'.

Back to commutators

Suppose we have two algorithms P and Q, and their results are: P = (123) and Q = (456). In this case, the cycles of P and Q are disjoint. Because of this, PQ will have the same result as QP in this special case. And if PQ = QP, then we can show that the commutator of P and Q is the identity (id):

PQP^-1Q^-1 = QPP^-1Q^-1 (we can replace PQ by QP, because PQ = QP)

And QPP^-1Q^-1 = QQ^-1 = id (P and P^-1 cancel out, Q and Q^-1 cancel out too)

If the commutator of P and Q is the identity, we say that P and Q commute, which is equivalent with saying that PQ = QP.

If you recall the socks-and-shoe-rule, imagine that P = 'take off shoe' and Q = 'take off sock'. In that case, P and Q do not commute, because if you would do the following: "shoe off, sock off, shoe on, sock on" you will not end up in the situation you started with. However, if we would take Q = 'take golve off' instead, then P and Q commute.

On a puzzle, this means that executing PQP^-1Q^-1 on the solved puzzle, will result in the solved puzzle again. You can probably see that this also works for P = (123456789) and Q = (10 11 12 13 14 15 16 17 18). Because again, these cycles are completely disjoint. However... What will happen if P and Q have only 1 nummer in common? For example: P = (123456789), Q = (9 10 11 12 13 14 15 16 17)? In this case:

PQP^-1Q^-1 = (123456789)(9 10 11 12 13 14 15 16 17)(987654321)(17 16 15 14 13 12 11 10 9)

It's easy to check that nothing will happen to most numbers. PQP^-1Q^-1 will 'almost' commute, and will 'almost' be the identity, but not quite: A small number of pieces, exactly 3 of them, will not fall back in place. In this case PQP^-1Q^-1 = (9 17 8). In general, if the cycles of P and Q have only 1 number in common, the commutator of P and Q will be a 3-cycle. I won't give a formal proof of this here, but it should become clear after seeing it on a puzzle a few times.

Cycling three pieces on the cube

So now it's time to use the theory described above to make commutators that are useful for solving puzzles. Remember, I am telling you how to cycle pieces on the cube, but these ideas can also be applied to other puzzles. As you know, the move RUR' inserts a corner piece from the U layer into the D layer. If we expres the result of one of these moves in cycle notation, the DRF piece will be one of the pieces. Another thing you should notice, is that the DRF piece is the only piece in the D layer that is changed by RUR'. This means that we could take P = RUR' and Q = D. Now, if we look at the cycles of P and Q, they will only have 1 piece in common: the DRF piece. This means that if we build a commutator with P and Q, the result must be a three-cycle of corners:

And, as shown by the applet, the result is indeed a three-cycle. Notice that we can also take P = RU2R' or RU'R', and Q = D2 or D' to create different three cycles. Using these basic three-cycles in combination with some setup-moves (I will discuss those later), one can often solve any three-cycle of corners in 10 moves or less (the maximum is 12 moves). In order to do this, it can be usefull to learn how to recognise situations like this from other angles, and also execute the algorithms from other angles. For example, to take P = FDF', Q = U.

The message so far is: If you look at the positions of the pieces that two algorithms, P and Q, permute, and they have only one position in common, then PQP^-1Q^-1 will be a three cycle. The next two parts will explain more about cycling three pieces, and seeing which pieces are cycled, and in which direction. However, if you first wish to see what else you can do with commutators, you can skip the next two parts and progress to: More easy-to-understand commutators.

The basic 8 move corner three-cycles

For three cycles, I will use the following notation: RFU -> DFR - > DLF, means a three cycle where the R sticker of the RFU piece ends up being the D sticker of the DFR face. In other words, the order of the letters matters, and you should think of this being 3 three-cycles of stickers, rather than 1 three-cycle of corners. This means I can also highlight three stickers on the cube to show the basic 'shape' of a three cycle. The basic 8 move corner three-cycles look like this: Two stickers of the cycle are on the same face, and another sticker is in the opposite layer (but NOT on the opposite face). Two examples:

Example 2: Two stickers in the cycle are on the U face, one sticker is in the D layer (but NOT on the D face). In this case we would have to take P = R'D'R and Q = U'. A way to think of this is: R'D'R replaces the URF sticker by the sticker from the D layer. U' will then replace the current URF sticker with the other U face sticker that needs to be cycled. R'DR will then replace the current URF sticker with the 'old' URF sticker.

You might wonder why I choose P = R'D'R in this case. In the first example, the moves RUR' inserted a corner into the D layer, without changing the rest of that layer. However, in this example, there are two highlighted stickers in the U face (stickers that are part of the cycle), and that's why we choose a move that inserts a corner into the U layer, without changing the rest of that layer.

Example 3: Two stickers in the cycle are on the R face, one sticker is in the L layer (but NOT on the L face). So, we have to find a move that iserts the corner in the L layer into the R layer, without changing the rest of the R layer (and the green sticker ends up in the green face). If you have trouble finding this move, you should hold the cube with the green side (the side with two highlighted stickers) on the bottom, and work with moves like RUR' RU2R' and RU'R' (as in example 1). In this case we would have to take P = ULU' and Q = R2. A way to think of this is: ULU' replaces the RUF sticker by the sticker from the L layer. R2 will then replace the current RUF sticker with the other R face sticker that needs to be cycled. UL'U' will then replace the current RUF sticker with the 'old' RUF sticker.

Notice that in both of these examples, P is esentially the same as a RUR', RU2R' or RU'R' move, only executed from a different angle and/or mirrored.

Setup moves

The next part explains how to use the basic 8-move three-cycles to solve any random three-cycle of corners on the cube. Some three cycles can't be solved in 8 moves. In those cases, we will need a few 'setup moves'. If you know an algorithm that solves a problem, you can use that same algorithm in combination with some extra moves to solve another 'version' of that same problem. For example, if you know how to flip two edges, you can use the same trick to flip two other edges:

In the applets above, the first algorithm flips the UF and UB edge. The second algorithm is basically the same as the first one, only it starts with R'F' and ends with FR. In that case, two other edges are flipped: The edges that are in the UF and UB position after R'F'.

If you look at the two problems in the applets above, you will have no problem seeing how the first 'problem' can be solved. E will do the job! The second one will be a bit harder. However, both of these problems are very similar. You can think of the second problem being another 'version' of the first problem. In both cases, we have to cycle around 4 centres and 4 edges. We know how to solve this problem if all the pieces that need to be cycled are in the E layer. So all we have to do is find some setup moves to bring all the edges that we want to cycle in the E layer: RBLR'FR. Then E cycles the pieces, and the inverse of the setup moves will give us the solved cube!

The last example illustrates that setup moves are useful for solving problems that have the same 'cycle structure' as a problem we can already solve: If you know an algorithm to cycle around three pieces, you can cycle around three other pieces, using setup moves.

Solving random three-cycles of corners

On the right you can see a picture of me and Stefan Pochmann in a restaurant in Downtown Disney. Stefan just showed me how to solve a random three-cycle of corners, and gave me one to try it.

Example 4: Look at the three cycle in the first applet. If we want to solve that three cycle with the basic commutator moves I explained, where do we have to look at? First of all, we look at the 3 three-cycles of stickers, and their shapes (when you have a cube in your hands, you can place three of your fingers on the stickers you need to cycle). We can look at this in three different ways:

We can try to do the cycle: URF -> FDL -> BRU. OR we can choose to do: RFU -> DLF -> RUB. Or we can choose to do: FUR -> LFD -> UBR. In the second case, we know that we can solve it in 8 moves, because two stickers are on the R face, and the other one is in the L layer, but NOT on the L face. In this case, BL2B' replaces the RUB sticker by the DLF one, so P = BL2B'. (Notice that this is just a variant of RU2R', if we used green as bottom layer). Then R replaces the RUB sticker with the RFU one, so Q = R. Then P^-1Q^-1 should finish the three cycle: B L2 B' R'. And indeed, B L2 B' R B L2 B' R' solves the three cycle! (Play the first applet to see this).

Example 5: Look at the three cycle in the first applet, and the 3 possible three-cycles of stickers we can look at. In this case, none of the stickers are on the same face, so we can't solve this in 8 moves. However, we can use a setup-move to create a pattern that we CAN solve in 8 moves. Click on the 'play' button in the second applet. By doing the move B, we 'create' a three cycle of stickers that we can solve in 8 moves. So after B, we take P = R D2 R' and Q = U' and build a commutator of those two algorithms. After executing the commutator, we have to undo B to solve the cube. Thus, the whole solution of the three cycle is 10 moves: B - (R D2 R') U' (R D2 R') U - B'. (This is not the only way to do it... Looking at the other two applets, and using other setup-moves, you might find other 10 move solutions for this problem)

Using the method described here, you can always solve a three cycle of corners in 12 moves or less. However, 12 moves is really the 'worst case scenario', and you will see that you can do it in 10 moves or less in most cases.

More easy-to-understand commutators

So far, I only discussed commutators that cycle three pieces. But you can do more with commutators. In this part, I will give some examples with a short explanation. You don't really have to memorise these moves: if you understand how they work, they are very natural solutions. Play around with these moves, and you will get a feel for how it works.

The end...

Yes... This is the end. I enjoyed writing this, and I certainly hope you enjoyed reading it. If you have any questions about this subject, or if you spot an error in this page, or if you know an interesting commutator move that I can add to this page, please contact me and tell me about it!