CubeTwister 2.0alpha142 2012-02-11

ch.randelshofer.rubik.solver
Class Solver

java.lang.Object
  extended by ch.randelshofer.rubik.solver.Solver

public class Solver
extends java.lang.Object

This class performs a two phase IDA* search for a solution to the scrambled cube.

Phase 1 searches the group spanned by 'U,D,R,L,F,B' until a configuration is discovered where the three coordinates of twist, flip, and choice are "correct" with respect to a solved cube. This means that no edge cubie is twisted, no corner cubie is flipped, and the four middle slice edge cubies are in the middle slice (but not necessarily in their correct permutation within that slice). At this point, we have found a member of an element of the phase two group.

Phase 2 uses the resulting phase 1 configuration as the starting point for a search of the group spanned by 'U,D,R2,L2,F2,B2', the goal being to reach 'I', the identity (i.e. the solved configuration). Note that this group preserves the three coordinates of the phase 1 search since in phase 2 it is impossible to alter the twist, flip, or choice aspects of the cube. The U, D moves do not alter corner or edge parity and do not affect the choice of the middle slice edge cubies. The same is true for the R2, L2, F2, B2 moves. This can be verified by considering the effect these moves have on cube parity (see cube.cpp for details on the parity frame of reference used).

In search parlance, the pruning tables (a.k.a. "pattern databases) constitute an "admissible" heuristic. This means that they always underestimate the distance (i.e. number of moves required) to reach the goal state. It can be proven that any search, such as IDA*, that examines nodes at progressively increasing cost values and employs an admissible heuristic is "optimal". This means that the first solution found by the search is guaranteed to be of minimal distance required to reach the target, or goal, state.

Since the search is split into two sequential IDA* search phases, the optimality condition above does not always hold. However, since we allow the phase 1 search to iteratively deepen, if let run long enough, it will eventually deepen to the point where it is capable of finding a complete solution. At this point, we know we have an optimal solution as we have degenerated to a a single IDA* search of the cube space, but this takes a very long time to occur. The main strength of the two phase search is that it finds a near optimal solution very quickly and outputs successively better solutions until it eventually finds one that is optimal. In most cases though, the search is terminated early (due to lack of patience) once an "adequate" solution is found.

For more information concerning IDA* and admissibility, see the paper "Depth-First Iterative-Deepening: An Optimal Admissable Tree Search" by Richard E. Korf. This paper appears in volume 25 of "Artificial Intelligence" 1985, pp. 97-109. Also, there are many texts on AI (Artificial Intelligence) or books on search techniques that cover these topics in depth.

This class has been derived from solver.cpp and solver.h from the 'Kociemba Cube Solver 1.0' (KCube) (c) Greg Schmidt.

Version:
1.0.2 2003-03-16 Text provided to progress monitor improved.
1.0.1 2002-12-23 Text provided to progress monitor improved.
1.0 2000-09-22
Author:
Werner Randelshofer, Hausmatt 10, CH-6045 Immensee, Switzerland

Field Summary
static int ABORT
          The search was aborted.
static int FOUND
          A sub-optimal solution was found.
static int NOT_FOUND
          A solution was not found.
static int OPTIMUM_FOUND
          An optimal solution was found.
 
Constructor Summary
Solver()
           
 
Method Summary
 SequenceNode getSolution()
          Returns the solution generated by solve().
static void initializeTables(ProgressObserver pm)
          Initializes both the move mapping and pruning tables required by the search.
 int solve(ProgressObserver progressMonitor, KociembaCube scrambledCube, Notation notation)
          Perform the two phase search.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

NOT_FOUND

public static final int NOT_FOUND
A solution was not found.

See Also:
Constant Field Values

FOUND

public static final int FOUND
A sub-optimal solution was found.

See Also:
Constant Field Values

OPTIMUM_FOUND

public static final int OPTIMUM_FOUND
An optimal solution was found.

See Also:
Constant Field Values

ABORT

public static final int ABORT
The search was aborted. (i.e. phase 2 did not yield an improved solution).

See Also:
Constant Field Values
Constructor Detail

Solver

public Solver()
Method Detail

initializeTables

public static void initializeTables(ProgressObserver pm)
Initializes both the move mapping and pruning tables required by the search.


solve

public int solve(ProgressObserver progressMonitor,
                 KociembaCube scrambledCube,
                 Notation notation)
Perform the two phase search.

Returns:
NOT_FOUND, FOUND, OPTIMUM_FOUND or ABORT.

getSolution

public SequenceNode getSolution()
Returns the solution generated by solve().

Returns:
The solution or null if the solver has been aborted.

(c) Werner Randelshofer.
All rights reserved.