A fast Coset Solver 

To show that God's number is 20 we have to show for 55,882,296 Hcosets, each coset containing 19,508,428,800 positions, that all these positions can be solved within 20 moves. We are able to solve each coset within 20 seconds on average, that is about 1 billion positions per second! This speed is absolutely crucial for our proof and we describe the method to achieve this in more detail in this section. 

Let us take for example the Hcoset which contains the well known "cubeinthecube" pattern r
Phase 1 of the TwoPhaseAlgorithm searches maneuvers m of increasing length which transform r into an Hposition. Here are the first 6 maneuvers found, together with the resulting Hpositions and the positions m' (the inverse of m):
Have a closer look at the positions m'. If you relabel them you will get exactly the H*r coset visualization. This means that they are all elements of the coset H*r and if you apply the maneuver m to them the result is the solved cube. 

This is the first key idea of the coset solver: Taking a position r, we perform a phase1 IDA* search. Every new Hposition found by a maneuver m of length N corresponds to the solve of a a position in the coset H*r of length N. We show this more formally: If we have found a maneuver m with r*m = h (with h from H) we have (h'*r)*m = Id, and because the inverse h' of h also is from H the position (h'*r) is from the coset H*r and is solved by the maneuver m. h1'*r = h2'*r is equivalent to h1=h2, so the mapping f from H > H*r : f(h) = h'*r is one to one. This means if we have "visited" all elements of H by the phase 1 search applied to position r with maneuvers with length <=N, we also have shown that all elements of the coset H*r can be solved within N moves. 

The time do do a full IDA* search grows exponentially with the maneuver length N. It is not possible to do a full search even to depth 16 within a reasonable time for the 55,882,296 Hcosets. We only do a full depth 15 IDA*search and use a bitvector of dimension 19,508,428,800 to mark all visited Hpositions. This means that at this point we solved exactly those positions of the coset H*r which do not need more than 15 moves. The time for this task is about 1.9 s per coset with the reference hardware used (Nehalem X3460 CPU running at 2.8GHz with four cores and hyperthreading enabled). Our IDA* implementation visits about 25,000,000 positions/second and uses a pruning table of size 680 MB. 

If we append any move from A=<U,U2,U',D,D2,D',R2,F2,L2,B2> to an Hposition, we get a different Hposition. This is the second key idea of our coset solver: If we append all moves from A to all positions marked already as visited in the depth 15 bitvector, we visit a lot of new Hpositions, all reachable within 16 moves. We store all these positions together with the old ones in a new depth 16 bitvector. We call this operation a prepass; our implementation takes 3.1 s for a single prepass. Achieving this speed is anything but trivial and requires careful organization of the bitvector.We repeat this prepass 4 more times to get a depth 20 bitvector. At this point we have solved all positions of the coset H*r where the solving maneuver has a maximum of 15 arbitrary moves followed by a maximum of 5 moves from A. The total computation time at this point is about 17.4 s for one coset. 

Usually there still are a few bits not set in the bitvector, around a few hundred on average. If a bit for the Hposition h still is 0, this means that we still have not solved the H*rcoset position (h'*r). All these positions can be solved individually with a TwoPhaseAlgorithm solver within 20 moves. At this point we have finally solved the complete H*r coset within 20 moves, total time is about 20 s on average. 

The above description is a bit simplified. For a fraction of "difficult" cosets there are too many individual positions left at the end. For these it is better do proceed in the following way:


The computation time  donated by Google  for all 55,882,296 Hcosets was about 35 CPUyears. <previous> 