The Optimal Solvers |
An optimal solver never needs more moves to restore a scrambled cube than the number of moves used to scramble the cube. The standard optimal solver
implemented in Cube Explorer uses Mike Reid's method from 1997. Because the phase 1 pruning table has an entry for each possible position, phase 1 solutions are generated very fast. So we just produce triple phase 1 suboptimal solutions and throw them away until the cube is solved (the solved cube is a phase 1 solution). Using the pruning table in parallel in three different directions is a nice thing because it substantially improves the tree-pruning quality. If p1, p2 and p3 are the pruning values in the three different directions, we can use max(p1,p2,p3) as the effective pruning value in our search. A look at the distribution
of the pruning values in phase 1 shows that the probability to have
the pruning value 10 in each direction is relatively high. The following
idea (suggested by Michiel de Bondt) improves the performance of the algorithm
by about 35%: |
My huge optimal solver works the same way as the standard optimal solver does. The only difference ist that it uses the UDSliceSorted coordinate instead of the UDSlice coordinate to build the pruning table. The goal state is a subgroup of the group which defines the goal state for the standard optimal solver, because all 12 edges are in place now. The pruning table is about 24 times bigger and the average pruning value is higher, as documented in the distribution of the pruning table. It runs about 5 times faster than the standard optimal solver. |