|
CubeTwister 2.0alpha142 2012-02-11 | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object ch.randelshofer.rubik.solver.Solver
public class Solver
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.
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 |
---|
public static final int NOT_FOUND
public static final int FOUND
public static final int OPTIMUM_FOUND
public static final int ABORT
Constructor Detail |
---|
public Solver()
Method Detail |
---|
public static void initializeTables(ProgressObserver pm)
public int solve(ProgressObserver progressMonitor, KociembaCube scrambledCube, Notation notation)
public SequenceNode getSolution()
|
(c) Werner Randelshofer. All rights reserved. |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |