ch.randelshofer.rubik.solver
Class PruningTable

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

public class PruningTable
extends java.lang.Object

Constructs a pruning table from a pair of move mapping tables. The pruning table contains an entry corresponding to each possible pairing of entries from the two tables. Thus the number of pruning table entries is the product of the number of entries of the two move mapping tables. A breadth first search is performed until the table is filled. Each table entry contains the number of moves away from the cube home configuration that is required to reach that particular configuration. Since a breadth first search is performed, the distances are minimal and therefore they constitute an admissible heuristic. When an admissible heuristic is used to prune a heuristic search such as IDA*, the search is guaranteed to find an optimal (i.e. least number of moves possible) solution. This class has been derived from pruningt.cpp and pruningt.h from the 'Kociemba Cube Solver 1.0' (KCube) (c) Greg Schmidt.

Version:

0.0 2000-07-01

Author:

Werner Randelshofer, Hausmatt 10, CH-6045 Immensee, Switzerland

Constructor Summary

PruningTable(MoveTable moveTable1, MoveTable moveTable2, int homeOrdinal1, int homeOrdinal2)
Constructor - Must provide a pair of move mapping tables and the associated ordinal corresponding to the cube's "home" configuration.

Method Summary

void	dump() Dump table contents.
int	getValue(int index) Get a pruning table value corresponding to the specified index.
void	initialize(java.io.File file, ProgressObserver pm, java.lang.String pmNote) Initialize the pruning table by either generating it or loading it from an existing file.
int	moveTableIndicesToPruningTableIndex(int ordinal1, int ordinal2) Convert a pair of move mapping table indices to the associated pruning table index.
void	setValue(int index, int value) Set a pruning table value at the specified index.
int	size() Obtain the size of the table (number of logical entries).

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

PruningTable

public PruningTable(MoveTable moveTable1,
                    MoveTable moveTable2,
                    int homeOrdinal1,
                    int homeOrdinal2)

Constructor - Must provide a pair of move mapping tables and the associated ordinal corresponding to the cube's "home" configuration. The home ordinals correspond to the root node of the search.

Method Detail

initialize

public void initialize(java.io.File file,
                       ProgressObserver pm,
                       java.lang.String pmNote)

Initialize the pruning table by either generating it or loading it from an existing file.

moveTableIndicesToPruningTableIndex

public int moveTableIndicesToPruningTableIndex(int ordinal1,
                                               int ordinal2)

Convert a pair of move mapping table indices to the associated pruning table index.

getValue

public int getValue(int index)

Get a pruning table value corresponding to the specified index.

setValue

public void setValue(int index,
                     int value)

Set a pruning table value at the specified index.

size

public int size()

Obtain the size of the table (number of logical entries).

dump

public void dump()

Dump table contents.