The problem
Find a sequence of moves that changes the solved position of the Cmetrick Too Hard shown below-left to the solved position shown below-right:
 |
 |
| Before |
After |
In other words, find a move sequence that makes it look just as if you had turned the whole puzzle
180 degrees around its centre.
To write down the moves, you will need some kind of notation. The four balls are given the letters
a to d, clockwise like this:
a b
d c
Each of the four balls can be rotated up, down, left or right. These directions are given the letters U, D, L, and R respectively. A move can therefore be described by a combination of two letters, one for the ball, and on for the direction of the move.
Here is one solution for the problem, which has 88 moves:
aR bR bU cU dU aU aR bR bU bU bL aL aD dD cD bD bL aL
aR bD cL dU aR bR bU cU dU aU aR bR bU bU bL aL aD dD cD bD bL aL dD cR bU aL
aD bL cU dR aR bR bU cU dU aU aR bR bU bU bL aL aD dD cD bD bL aL dL cD bR aU
aL bL bD cD dD aD aL bL bD bD bR aR aU dU cU bU bR aR
Note that half turns are counted as two moves, for example the bU bU in the middle of the first line of this example solution.
Checking your solution
When you have found your own solution, you can verify it here:
Just type (or cut & paste) your solution into the box and click the button. A message should pop up saying whether or not it was a valid solution, and also tell you how many moves it is. Try it out with the example solution to see how it works.
Tom Rokicki's method
Tom's main insight was that the four shared locations between the spheres were
the bottlenecks. If any piece is to move from one sphere to another, it will
have to pass through one of those four locations. Furthermore, any move will
affect exactly one such location, replacing its piece by another.
In the problem position every coloured piece has to move to its diagonally opposite
sphere. The 16 coloured pieces therefore each have to pass through two of those shared
locations. This means that there are at least 32 moves where a coloured piece is moved
into a shared location. At the end all the shared locations must have a white piece, and
that needs four more moves. This immediately shows that at least 36 moves are needed.
In the above I counted the number of times the pieces move into the shared locations.
A slight variation of this insight is to count how many times they move out of them.
You still get the same conclusion: The 16 coloured pieces each have to come through (i.e. out
of) the shared locations twice, and at the start you need 4 moves to get the white pieces out
of the shared locations.
This way of looking at it works a bit better in general because in a mixed position you can
determine whether a white piece at a shared location needs to be moved or not. If a white piece
occupies the shared location between two spheres, but either:
1. a piece opposite the white piece on one of the two adjacent
spheres is not yet placed correctly, or
2. some coloured piece needs to move across that location
then the white piece will have to move out at some point.
For any mixed position we can use the above insights to get a lower bound on how many moves it
takes to solve it. A different way to get a lower bound is to count for each piece how many
moves it would take to get it to its solved position, sum these together and divide by four.
This works because any move affects exactly four pieces, and hence can reduce that sum by at
most four.
Tom Rokicki's program uses a straightforward IDA* search
(see the Computer Cubing page). Instead of pruning tables, it
uses the above two heuristics. As the problem position happens to be quite far away from
being solved (possibly an antipode), and the heuristics happen to be very good for such a
distant position, Tom's program could find a solution relatively quickly. Unfortunately the
program is not well suited to random positions, and takes a very long time to solve those.
Tom suggested that it is possible to improve the program by taking into account which moves
have to be performed to solve each piece (instead of just the total number of moves), and that
this would probably allow it to solve random positions.
Tomas Rokicki's source code, written in C++.
Silviu Radu's method
Silviu has made an optimal solver. He used techniques similar to those I describe on the
Computer Cubing page.
He used a large pruning table that gives the number of moves that it takes to solve the eight
disks of two adjacent colours. This single pruning table can of course be applied four times,
to any pair of adjacent colours. If these four applications of the pruning table all give a
distance of zero, then the puzzle must have been solved. The only degree of freedom left is a
permutation of the white pieces, but that is okay because those pieces are considered identical.
To speed up the search, he used move tables (or transition tables). Four coloured pieces have
20!/16! = 116280 possible positions amongst the 20 piece locations. The locations of four coloured
pieces in a position can therefore be given by a number less than 116280. The move table simply
gives the new position number of four pieces when given the previous position number and a move
that is applied to it.
The pruning table mentioned earlier is very large. It has 1162802 = 13,521,038,400
entries. This is too large to work with, so Silviu had to reduce it by using only 2 bits
per position (storing the distance modulo 3). He also used symmetry to reduce it by a further
factor of about 12. This allowed him to store it in memory, using about 1162802/48 bytes,
or 280 Mb. Below is the depth information from the pruning table. Note that only 20!/12! =
5,079,110,400 table entries are actually used.
| Depth | Positions |
|---|
| 0 | 1 |
| 1 | 8 |
| 2 | 48 |
| 3 | 236 |
| 4 | 1089 |
| 5 | 4736 |
| 6 | 19672 |
| 7 | 77910 |
| 8 | 295374 |
| 9 | 1064288 |
| 10 | 3631121 |
| 11 | 11616626 |
| 12 | 34335284 |
| 13 | 92242146 |
| 14 | 219343290 |
| 15 | 444627867 |
| 16 | 742857680 |
| 17 | 989913992 |
| 18 | 1019505291 |
| 19 | 792980677 |
| 20 | 458469996 |
| 21 | 193958688 |
| 22 | 59377220 |
| 23 | 12785460 |
| 24 | 1836044 |
| 25 | 160848 |
| 26 | 4792 |
| 27 | 16 |
| Total | 5079110400 |
|---|
Silviu used GAP, a maths program for
computational group theory, to calculate the move tables and symmetries. A C program, based on
Mike Reid's
optimal cube solver,
then computes the pruning table and does the search for a solution.
An interesting trick can be used to make the pruning more effective. Herbert Kociemba used it in his
Cube Explorer and he credits the idea to
Michiel de Bondt. Suppose you have the puzzle in a mixed position, and that the pruning table says that
it takes 10 moves to solve the colours a and b. Suppose further that you look up colours c and d in the
pruning table and it says that those need 10 moves to solve as well. Whichever move you do to the
solved state, it can affect only one of the colour pairs, not both. Therefore if you do 10 moves from
the starting state, one pair of colours can always be solved in at most 9 moves. Conversely, if both
pairs of colours each need 10 moves to solve, the puzzle as a whole cannot be merely 10 moves from the
start. What this means is that if a & b need n moves according to the pruning table, and c & d
need n moves as well, then the puzzle as a whole actually needs at least n+1 moves. The same can be
said if we look at the other two pairs of adjacent colours.
The analysis of the symmetries of the Cmetrick Too is also surprising. The puzzle obviously has
16 symmetries, arising from 90 degree rotation about the central vertical axis (4), rotation
about a horizontal axis (2) and from reflection (2). There is more symmetry however. Suppose you
reflect only one ball, say ball c, through the horizontal plane. The roles of two opposite coloured
disks swap, and the move cR now becomes cL and vice versa, as do the moves cU and cD. This is a
perfectly valid symmetry of the puzzle. One way to see this is as follows. Start with two identical
puzzles. Mix them up the same way by using the same random moves on each, except that whenever you
move ball c on one puzzle, you do the inverse ball c move on the other. The end result will be that
the positions that the two puzzles are very similar, the only difference being that the two disks on
opposite sides of ball c have swapped, as have the two disks that belong in those two positions.
Conversely, any two positions that are related in that way can be solved in the same number of moves.
Each of the balls can be reflected separately, so the puzzle as a whole has 128 symmetries.
Silviu also had several fascinating ideas before he made this optimal solver. His first plan was
to make a 2-phase solver. The first phase would put the puzzle into a position that could be
solved using only the moves {bR,aD,aR,dL,cL,cD}. The special thing about the group that remains
is that it is a direct product, i.e. it consists of two independently solvable puzzles. The
balls a and b can be solved using {bR,aD,aR} without affecting balls c and d, and similarly
c and d can be solved with {dL,cL,cD} without affecting a and b at all. The two subgroups are
isomorphic, so they can be solved in exactly the same way reducing the amount of memory the
program needs. Eventually he abandoned this idea since it wasn't quite able to solve the
position from the contest within a reasonable time.
Silviu Radu's source code, written in C and GAP.