net.pacbell.jfai.toh.domain
Class Solver

java.lang.Object
  net.pacbell.jfai.toh.domain.Solver

public class Solver
extends Object

There is a base with three pins to accept disks. Each disk has a certain size. At the beginning all disks are stacked on one pin. The goal is to move the stack to another empty pin.

Legal moves:

1. Any disk can go onto the base.
2. A smaller disk can go onto a larger disk.
3. Only one disk at a time can move.

An instance of this class implements the solution of the problem of moving the initial tower from the source pin to the target pin.

Before invoking solve(), you may configure an instance by setting the number of disks, the source pin and the target pin.

Bound Bean Properties:

• numberOfDisks
• state
• source
• target
• moveCount

Author:

Jürgen Failenschmid

Nested Class Summary

class	Solver.AbstractState Abstract superclass for all state classes of Solver.
class	Solver.Idle State while Solver is being configured.
static interface	Solver.IStateListener An object that wants to be notified about specific state changes can implement this interface.
class	Solver.Paused State while the solver is paused.
class	Solver.Solving State while Solver is running to solve the puzzle.

Field Summary

(package private) static Log	LOG The trace file.
static String	PROPERTY_MOVE_COUNT Name of bound property: number of disks.
static String	PROPERTY_NUMBER_OF_DISKS Name of bound property: number of disks.
static String	PROPERTY_SOURCE Name of bound property: source pin.
static String	PROPERTY_STATE Name of bound property: solver's state.
static String	PROPERTY_TARGET Name of bound property: target pin.

Constructor Summary

Solver()
Creates an idle instance with default number of pins and disks.

Method Summary

void	addPropertyChangeListener(PropertyChangeListener listener) Adds a listener for changes to any property.
void	addPropertyChangeListener(String propertyName, PropertyChangeListener listener) Adds a listener for changes to the given property.
void	addStateListener(Solver.IStateListener listener) Adds the listener to receive a notification if the state changes.
Base	getBase() Gets the base.
List<Disk>	getDisks() Answer a list of all the disks in the puzzle, sorted by descending size.
long	getMoveCount() Answers the number of moves that the solver has executed.
protected long	getMoveCounter() Gets the number of executed moves.
int	getNumberOfDisks() Gets the number of disks.
long	getRemainingMoves() Answers the number of remaining moves that the solver has to execute.
protected Date	getSolutionStartTime() Gets the start time.
Pin	getSource() Gets the source pin.
Date	getStartTime() If the solver is idle, then the result is null.
Solver.AbstractState	getState() Gets the state.
Pin	getTarget() Gets the target pin.
long	getTotalMoves() Answers the total number of moves necessary to solve the puzzle.
static long	getTotalMoves(int numberOfDisks) Let toh(n) be the number of moves for a puzzle with n disks.
boolean	hasListeners(String propertyName) Checks if there are any listeners for changes to the given property.
void	pause() Pauses the solver.
void	removePropertyChangeListener(PropertyChangeListener listener) The given listener does no longer receive property change events.
void	removePropertyChangeListener(String propertyName, PropertyChangeListener listener) The given listener does no longer receive property change events for the given property.
void	removeStateListener(Solver.IStateListener listener) The listener does no longer receive notifications about state changes.
void	resume() Resumes the solver.
protected void	setMoveCounter(long moveCounter) Sets the number of executed moves.
void	setNumberOfDisks(int newValue) Requests to change the number of disks at the source pin.
protected void	setSolutionStartTime(Date solutionStartTime) Sets the time when the solution started.
void	setSource(Pin newSource) Requests to change the source pin, which effectively moves all disks to this pin.
protected void	setState(Solver.AbstractState newState) Sets the state.
void	setTarget(Pin newTarget) Requests to change the target pin.
void	solve() This is the entry point to solve the problem of moving the initial tower from the source pin to the target pin.
(package private) void	stackDisksAt(Pin pin) Position all disks at the given pin.

Methods inherited from class java.lang.Object

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

Field Detail

PROPERTY_MOVE_COUNT

public static final String PROPERTY_MOVE_COUNT

Name of bound property: number of disks.

See Also:

Constant Field Values

PROPERTY_NUMBER_OF_DISKS

public static final String PROPERTY_NUMBER_OF_DISKS

Name of bound property: number of disks.

See Also:

Constant Field Values

PROPERTY_SOURCE

public static final String PROPERTY_SOURCE

Name of bound property: source pin.

See Also:

Constant Field Values

PROPERTY_STATE

public static final String PROPERTY_STATE

Name of bound property: solver's state.

See Also:

Constant Field Values

PROPERTY_TARGET

public static final String PROPERTY_TARGET

Name of bound property: target pin.

See Also:

Constant Field Values

LOG

static final Log LOG

The trace file.

Constructor Detail

Solver

public Solver()

Creates an idle instance with default number of pins and disks.

Method Detail

getTotalMoves

public static final long getTotalMoves(int numberOfDisks)

Let toh(n) be the number of moves for a puzzle with n disks. It takes one move to reposition a tower with one disk:

toh(1) = 1

To move a tower with n disks, move the upper (n-1) disks to the temporary spot, then move the lowest disk, then move the (n-1) disk tower from the temporary spot to the destination.

toh(n) = toh(n-1) + 1 + toh(n-1) = 2 * toh(n-1) + 1 [ A ]

toh(2) = 1 + 1 + 1 = 3
toh(3) = 3 + 1 + 3 = 7
toh(4) = 7 + 1 + 7 = 15

Hypothesis: toh(n) = 2 ⁿ - 1 [ B ]

Proof:

toh(n+1)

= 2 * toh(n+1-1) + 1 (from A)

= 2 * toh(n) + 1

= 2 * (2 ⁿ - 1) + 1 (apply B)

= 2 ⁿ⁺¹ - 2 + 1

= 2 ⁿ⁺¹ - 1

q.e.d.

Parameters:

numberOfDisks - the number of disks

Returns:

the total number of moves to solve the puzzle

addPropertyChangeListener

public void addPropertyChangeListener(PropertyChangeListener listener)

Adds a listener for changes to any property.

Parameters:

listener - listener who wants to receive property change events

addPropertyChangeListener

public void addPropertyChangeListener(String propertyName,
                                      PropertyChangeListener listener)

Adds a listener for changes to the given property.

Parameters:

propertyName - the name of the property of interest

listener - listener who wants to receive property change events

addStateListener

public void addStateListener(Solver.IStateListener listener)

Adds the listener to receive a notification if the state changes.

Parameters:

listener - the listener

getBase

public Base getBase()

Gets the base.

Returns:

the base plate of the puzzle

getDisks

public List<Disk> getDisks()

Answer a list of all the disks in the puzzle, sorted by descending size.

Returns:

all the disks of the puzzle

getMoveCount

public long getMoveCount()

Answers the number of moves that the solver has executed.

If the solver is idle, then the result is 0. Otherwise the result is the number of moves made so far.

Returns:

the number of moves

getNumberOfDisks

public int getNumberOfDisks()

Gets the number of disks.

Returns:

the total number of disks of the puzzle

getRemainingMoves

public long getRemainingMoves()

Answers the number of remaining moves that the solver has to execute.

If the solver is idle the result is the total number of moves to solve the puzzle. Otherwise, the result is the number of remaining moves to solve the puzzle.

Returns:

the number of remaining moves

getSource

public Pin getSource()

Gets the source pin.

Returns:

the source pin, where the tower is initially

getStartTime

public Date getStartTime()

If the solver is idle, then the result is null. Otherwise the result is the start time when the puzzle solution was started.

Returns:

the start time (or null)

getState

public Solver.AbstractState getState()

Gets the state.

Returns:

the current state

getTarget

public Pin getTarget()

Gets the target pin.

Returns:

the target pin, where the tower will be at the end

getTotalMoves

public long getTotalMoves()

Answers the total number of moves necessary to solve the puzzle.

Returns:

the total number of moves

hasListeners

public boolean hasListeners(String propertyName)

Checks if there are any listeners for changes to the given property.

Parameters:

propertyName - the name of a property

Returns:

does the solver have any listeners for this property?

pause

public void pause()

Pauses the solver.

removePropertyChangeListener

public void removePropertyChangeListener(PropertyChangeListener listener)

The given listener does no longer receive property change events.

Parameters:

listener - a property change listener

removePropertyChangeListener

public void removePropertyChangeListener(String propertyName,
                                         PropertyChangeListener listener)

The given listener does no longer receive property change events for the given property.

Parameters:

propertyName - a property name

listener - a property change listener

removeStateListener

public void removeStateListener(Solver.IStateListener listener)

The listener does no longer receive notifications about state changes.

Parameters:

listener - the listener

resume

public void resume()

Resumes the solver.

setNumberOfDisks

public void setNumberOfDisks(int newValue)

Requests to change the number of disks at the source pin. If the solver is in a state that does not allow this change, an IllegalStateException is thrown.

Parameters:

newValue - new number of disks

setSource

public void setSource(Pin newSource)

Requests to change the source pin, which effectively moves all disks to this pin. If the solver is in a state that does not allow this change, an IllegalStateException is thrown.

Parameters:

newSource - new source pin

setTarget

public void setTarget(Pin newTarget)

Requests to change the target pin. Makes sure that all disks are at the source pin: some of them might have moved before the solution was paused and the target pin was changed. If the solver is in a state that does not allow this change, an IllegalStateException is thrown.

Parameters:

newTarget - new target pin

solve

public void solve()
           throws ConfigurationException,
                  InvalidMoveException,
                  InterruptedException

This is the entry point to solve the problem of moving the initial tower from the source pin to the target pin. Number of Disks must be positive and the source and target pins must be different pins, otherwise an exception is thrown.

Throws:

ConfigurationException - if an invalid configuration is detected

InvalidMoveException - if an invalid move is detected

InterruptedException - If the solving thread is interrupted

getMoveCounter

protected long getMoveCounter()

Gets the number of executed moves.

Returns:

the number of executed moves

getSolutionStartTime

protected Date getSolutionStartTime()

Gets the start time.

Returns:

the time when the solution was started recently

setMoveCounter

protected void setMoveCounter(long moveCounter)

Sets the number of executed moves.

Parameters:

moveCounter - the number of executed moves

setSolutionStartTime

protected void setSolutionStartTime(Date solutionStartTime)

Sets the time when the solution started.

Parameters:

solutionStartTime - the start time

setState

protected void setState(Solver.AbstractState newState)

Sets the state.

Parameters:

newState - the new state

stackDisksAt

void stackDisksAt(Pin pin)

Position all disks at the given pin.

Parameters:

pin - a Pin