# 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.
We do a triple phase 1 search in parallel in three different directions. That means that our goal state is the intersection of the groups <U,D,R2,L2,F2,B2>, <U2,D2,R,L,F2,B2> and <U2,D2,R2,L2,F,B>. By the way, this intersection is not the group <U2,D2,R2,L2,F2,B2> but a group six times larger.

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%:
If we apply an arbitrary move to a cube from the goal state, the resulting cube stays at least in one of the three subgroups mentioned above. This implicates, that at least one of the three pruning values stays 0. So if we do for example 10 moves from the goal state, at least one of the pruning values is 9 or less. If on the other hand all three pruning values are 10, we know that we can use 11 as the effective pruning value. In general: if all three pruning values are n, we can use n+1 as the effective pruning value.

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.