And now for something entirely different—solving a cube puzzle with the aid of a Prolog program
My kids got this puzzle cube as a gift. Daddy, how do you solve it?
I know how to solve a regular Rubik's cube, using this beginner's method. This time, I wanted to develop a solution myself instead of following someone else's.
After some time of confused twisting and taking notes, I decided that I needed some heavier machinery and wrote a Prolog program to figure out how the faces and vertices moved. And then I assigned that to my Programming Languages class. With the program, I discovered enough moves with simple effects that I was able to put together a solution.
Afterwards I found some Youtube videos that aim to do the same. This one is typical. Check it out!
Here is a good way to label the vertices:
6-------7
/| /|
2-------3 |
| | | | y
| 4-----|-5 | z
|/ |/ |/
0-------1 +--x
The origin 0 has neighbors 1, 2, 4 in the x, y, z direction, and the others are sums thereof.
I label the faces as f r u d l r (front, rear, up, down, left, right).
You can grab each corner of the puzzle cube and twist it 120 degrees clockwise or counterclockwise. Let ri be the clockwise rotation about vertex i. These rotations have the following effects on the vertices and faces:
r0 (1 4 2) (d l f) r1 (0 3 5) (d f r) r2 (0 6 3) (f l u) r3 (1 2 7) (f u r) r4 (0 5 6) (b l d) r5 (1 7 4) (b d r) r6 (2 4 7) (b u l) r7 (3 6 5) (b r u)
Here, r0 is the rotation around vertex 0. Vertex 1 moves to vertex 4, vertex 4 moves to vertex 2, and vertex 2 moves to vertex 1. Such a permuation is called a cycle. Three faces are also permuted in a cycle. Note that the remaining vertices and faces are not permuted.
If r is a rotation, then r-1 (called the inverse or r) is the rotation in the opposite direction. (Cubers usually write this as r'.)
If r and s are two rotations, then their commutator [r, s] is the product r s r-1 s-1. That is, first do r, then s, then the inverse of r, then the inverse of s. If r and s commute (i.e., r s = s r), the commutator is the identity operation. Otherwise, it measures by how much r s differs from s r.
On the vertices, r0 and r1 commute—since they move different vertex groups, it doesn't matter in which order you do them. But on the faces, [r0, r1] has the effect (d r)(f l); that is, it flips the down/right and front/left faces.
This is the key for putting the faces to the right place. First arrange the vertices so that they are at the right position (which you can do by hand, without the need of an algorithm). Then use commutators repeatedly to permute the faces while leaving the vertices in place. You will see the exact algorithm below.
Once that is complete, the vertices and faces will be at the right positions, but unfortunately, the vertices will be twisted.
That is where [r0, r1]2 comes in—do [r0, r1], and then do it again. It preserves the vertices because [r0, r1] did, and it preserves the faces because [r0, r1] flipped down/right and front/left. Doing it twice flips them back. This squared commutator has a predictable effect on the twists of the vertices that you can use to untwist them all.
Finally, and that's why this cube is called “xtreme”, there are color codes along each face that need to match with their neighbor. It turns out that the squared commutator [r0, r1]2 spins four faces by 180 degrees, but leaves two faces in their the original orientation. Of course, it also twists the vertices. But if you repeat it three times (that is, use [r0, r1]6), then the vertices are unaffected and the face spin is done three times, which is the same as doing it once. By orienting the cube appropriately and fixing four faces at a time, you can get the faces to match perfectly.
When solved with yellow in front and the “T. Fischer” signature to the left, the colors are:
f: yellow (y) b: white (w) l: red (r) r: purple (p) u: green (g) d: blue (b)
Look at the vertices and note that each has three colors. Twist the cube so that the y-b-r color is in position 0, possibly twisted. Then put the y-p-b vertex in position 1, the y-r-g vertex in position 2, and the y-g-p vertex in position 3. You can just wing this.
When you are done, look at the back of the cube. Note that the four vertices are automatically at the correct position (but probably twisted).
The yellow face is in the right place. Count how many faces are out of place.
Place the correct faces in the u and b position. There are three possible swaps of faces. Fix the faces with the appropriate commutator:
(d r)(f l) = [r0, r1]
(d f)(l r) = [r0-1, r1] (the “sledgehammer”)
(d l)(f r) = [r0-1, r1-1]
If each incorrect face is to be swapped with a neighbor, put the correct faces in the l and r position. and one of those pairs to be swapped in the f and d positions, and do (d f)(l r) = [r0-1, r1]. Then continue with Case 1a.
If each incorrect face is to be swapped with an opposite face, put the correct faces in the f and b positions, and do [r0-1, r1]. Then continue with Case 2b.
Put that common vertex into the 2 position and do [r0, r1]. You will have four faces out of place. Then continue with Case 1a.
Put the faces into the left, back, and right position. Do [r0-1, r1]. Then continue with Case 1a.
Put the correct face to the back. Put the face to which the front face should go to the bottom. Do [r0-1, r1]. You now have at most four faces out of place.
Now the cube has the correct faces and vertices, but some vertices are likely to be twisted. Look at them and see what clockwise or counterclockwise twists are needed to fix them. If you are lucky, only one of the sides needs to be fixed.
The “double sledgehammer”, [r0⁻¹,r1]² twists vertices 0 and 2 counterclockwise, 1 and 5 clockwise, and it leaves the top four vertices (2, 3, 5, 7) as they are. Note that this move is made up of eight rotations.
○-------○
/| /|
○-------○ |
| | | |
| ⊕-----|-⊕
|/ |/
⊖-------⊖
In principle, you can keep applying the move over and over, rotating the cube as necessary. For example, a double sledgehammer, a 90 degree rotation of the cube around the z-axis, and another double sledgehammer produce this result, canceling out diagonally opposite twists:
○-------○
/| /|
○-------○ |
| | | |
| ⊖-----|-○
|/ |/
○-------⊕
This can be tedious, and I find it useful to look for other moves that can help. These two square commutators have twisting patterns in the y, x, and z direction like this:
[r0,r1]2 [r0-1,r1-1]2
⊖ ⊖
| |
| ⊕ ⊕ |
| / / |
⊖-------⊕ ⊕-------⊖
With a bit of practice, they are easy to recognize, and can save you some time.
When all vertices are twisted correctly, you may have two or four faces are correct, with the others flipped 180 degrees. Carefully look at matching edges. If you have exactly two correctly flipped faces, with one matching edge, put the correct faces in the u and b positions and do the sledgehammer 6 times. That's 24 rotations. You will be done.
In all other cases, put the incorrect faces in the t and f, t and d, or t-f-d-b positions, and do the sledgehammer 6 times, reducing to the first case.
Computing the effect of multiple rotations on the vertices and faces is tedious. Sure, [r0, r1]2 is (d l f)(d f r)(d f l)(d r f), but to compute the result (d l)(f r) by hand is no fun, and there are many more calculations like that. In Prolog, it isn't too hard to implement a predicate cycles so that
cycles([[d,l,f],[d,f,r],[d,f,l],[d,r,f]], X).
yields
X = [[d,l],[f,r]]
It's part 2 of this assignment. Give it a try yourself or peek at the solution.
I considered having my students implement this in Scala or Scheme, but Prolog turned out to be a great choice for doing experiments.
Once you have the cycles predicate, you can use it for many routine computations. For example, is it really the case that in Step 2, Case 2a can be reduced to Case 1a? Here is the proof:
cycles([[d,r],[f,l],[l,f,u]], X). X = [[d,r], [l,u]].
The effect predicate computes the effect of a sequence of rotations:
effect([r0,r1,r0,r0,r1,r1], V, F). V = [], F = [[d, r], [f, l]].
The findVertexFixingRotations predicate finds all vertex-fixing sequences of rotations that have a given effect on the faces:
findVertexFixingRotations([[d, r, f]], X). X = [r0, r0, r1, r0, r0, r2, r6, r7, r3] ; X = [r0, r0, r1, r0, r0, r5, r7, r6, r4] ; ... X = [r0, r0, r2, r0, r2, r1, r2, r2, r1] ; ...
This is how you can show that you can generate the entire permutation group.
With some ad-hoc queries, I discovered a number of moves that are simpler than the ones in the algorithm for cycles of length 3 and 5:
r0⁻¹ r4 r1 r0 r4 r1 = (b l r) // 3-cycle with opposing faces r0⁻¹ r5⁻¹ r4 r0 r5⁻¹ r4⁻¹ = (d r f) // 3-cycle with neighboring faces r0 r3⁻¹ r0 r3⁻¹ = (d r f l u) // 5-cycle that moves one face to an opposite
Unfortunately, I found the moves too confusing to actually apply them reliably, and ended up settling on the three commutators in the algorithm.
In step 1 of the algorithm, we put the four front vertices in the right position. Why don't we have to worry about the back?
The vertex rotations split into two halves. The rotations r0, r3, r5, r6 rotate only vertices 1, 2, 4, 7. And r1, r2, r4, r7 rotate only vertices 0, 3, 5, 6. Each of the halves acts as the alternating group A4 on its vertices (because it is generated by even permutations).
Once 0 and 3 are fixed, then 5 and 6 can't be flipped (since that would be an odd permutation). The same holds for 4 and 7 once vertices 1 and 2 are fixed. Therefore, the back is fixed as soon as the front is.
In step 2 of the algorithm, we have one correct face and rotate the other faces into their positions. Why does this always work?
The eight principal rotations r0 ... r7 are 3-cycles on the faces, so any product of them yields an even permutation of the six faces. It is easy to see that you can produce a set of generators, and hence all rotations, of the alternating group A6 (for example, by making a Prolog query for each generator).
In our method, we keep the yellow face fixed. The remaining faces are permuted by an even permutation. Therefore, you can't have exactly two incorrect faces, and four incorrect faces must be a pair of flips (and not a cycle of length 4). Those facts, and a few cycle calculations, show that Step 2 enumerates all possibilities
In step 3 of the algorithm, we need to twist all vertices, using the square commutators that leave the faces in place. Why does this always work?
A vertex is twisted when it is rotated. The twist can be 0 (in order), 1 (off by 120 degrees) or 2 (off by 240 degrees). 0, 1, and 2 correspond to ○ ⊕ ⊖ in the pictures above.
Rotation ri twists vertex i by 120 degrees and rotates three others without twisting them.
Recall that vertex rotations split into two halves: r0, r3, r5, r6 rotate only vertices 1, 2, 4, 7, and r1, r2, r4, r7 rotate only vertices 0, 3, 5, 6.
For a permutation that is composed of ri, separately compute the sum of the twists on { 1, 2, 4, 7 } and { 0, 3, 5, 6 } (modulo 3). When the permutation leaves the vertices unchanged, both of the sums are zero. To verify this, note that each ri adds a twist of 1. The twist sum defines a homomorphism Πrini↦ Σni from A4 to Z3 (whose kernel is the Klein 4-group with the ri rj-1).
In particular, if you have only two twisted vertices, they must be in the same vertex group (i.e. diagonally opposed in a face) and have twist values 1 and 2. You can repair that by two double sledgehammers, as shown in step 3 of the algorithm.
Now look at twist patterns (t1, t2, t3, t4) in GF(3)4. Since t1 + t2 + t3 + t4 = 0, they form a space of dimension 3, generated by the linearly independent (1, 2, 0, 0), (1, 0, 2, 0), (1, 0, 0, 2). Therefore, repeatedly applying the double sledgehammer can turn any twist pattern to (0, 0, 0, 0).
In step 4 of the algorithm, we need to flip some faces, using the six-fold sledgehammer, so that all faces are oriented correctly. Why does this always work?
Each of the rotations adds a 90 or 180 degree twist to some faces. To measure that twist, mentally draw an arrow on each face that goes from the lowest-numbered to the highest-numbered corner. This provides a “natural” orientation for each face. Then apply the rotation and see where the arrow lands on the target face. For example, consider r1. It moves f to r and the arrow (0,3) to (3,5). That's a 90 degree twist of the natural r face orientation, as given by the arrow (1, 7). Now consider how r1 brings the d face to the f face. The arrow (0, 5) becomes the arrow (3, 0), which is a 180 twist from the natural f face orientation. The third face that r1 rotates is also twisted by 90 degrees. The sum of all twists is 360 degrees. This is also the case for r2 ... r6. The rotations r0 and r7 don't twist any faces (due to the arbitrary definition of the “natural” orientation). In any sequence of rotations, the sum of all the twists is divisible by 360 degrees.
When you map out all these twists, you will note that all rotations ri that bring an element of { f, d, l } back to that set, or an element of { b, r, u } back to that set, twist the element by 0 or 180 degrees. However, all rotations that bring an element of { f, l, d } to { b, r, u } or from { b, r, u } to { f, l , d } twist the element by 90 or 270 degrees. Therefore, a face is always twisted 0 or 180 degrees when it is rotated back to the original position.
In summary, when all faces are rotated back to their original position, each of them is twisted 0 or 180 degrees (“flipped”), and the number of flipped faces is even. That tells you all possible flip patterns.
The six sledgehammer move fixes all flips if two adjacent faces are unflipped. It is easy to see how a second application of six sledgehammers takes care of the other cases, as described in Step 4.
Comments powered by Talkyard.