Jaap's Puzzle Page

The Cmetrick Too Hard contest

From June to August 2006 I hosted a contest for the CMetrick Too Hard on behalf of elogIQ. There were two winners in this contest - Tomas Rokicki and Silviu Radu, who shared the $500 prize between them. On this page I will describe the methods they used to get a computer to find optimal solutions to the problem of the contest.


The Contest Problem
Tom Rokicki's method
Sliviu Radu's method

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
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.

example moves

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.

DepthPositions
01
18
248
3236
41089
54736
619672
777910
8295374
91064288
103631121
1111616626
1234335284
1392242146
14219343290
15444627867
16742857680
17989913992
181019505291
19792980677
20458469996
21193958688
2259377220
2312785460
241836044
25160848
264792
2716
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.

All in all I found this contest to be a great experience. It has allowed me to see how others have attempted to solve such a problem. I would like to thank all the contestants for their hard work, and elogIQ for creating the puzzle and for asking me to host the contest.

Jaap