ch.randelshofer.rubik.solver
Class TripleSearchSolver

java.lang.Object
  ch.randelshofer.rubik.solver.TripleSearchSolver

public class TripleSearchSolver
extends java.lang.Object

An implementation of Herbert Kociemba's Triple Search solver.

Description of the algorithm (by Tom Rokicki):

Kociemba's original two phase algorithm works great, but there are a lot of positions that give it some difficulty. He now uses something called "Triple Search" in his cube explorer, and this is very effective in making it work better on many cubes.

The way this works is by solving essentially *three* positions at once, the input position, and two other positions where the L/R and F/B face are mapped, respectively, to U/D. If the original position gives some difficulty, chances are the other two will not. So instead of

 for (increasing allowed_phase1_depth) {
    trytosolve(allowed_phase1_depth)
 }
 

we do

 for (increasing allowed_phase1_depth) {
    for (three positions of input) {
      trytosolve(position, allowed_phase1_depth)
    }
 }
 This can give a tremendous speedup; on average, for finding a
 distance 20 position for 30,000 random positions, I find it
 is about six times faster.
 

 I have made an additional, further improvement.  Instead of
 just considering three positions, consider 6, where the other
 three are *inverses* of the first three.  If you do that, you gain
 another factor of two speed.
 

 (You can potentially exploit this to easily use multiple cores
 in modern processors too, so each core gets a position and
 depth to work on.  But this is somewhat secondary.)




Author:
  
Werner Randelshofer
 @version 1.0 Mar 3, 2008 Created.








Constructor Summary
TripleSearchSolver()



           
 



Method Summary

 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 





Constructor Detail



TripleSearchSolver
public TripleSearchSolver()