Algorithm
Development Kit 1.0

algs.model.problems.fifteenpuzzle
Class FifteenPuzzleNode

java.lang.Object
  extended by algs.model.problems.fifteenpuzzle.FifteenPuzzleNode
All Implemented Interfaces:
IGraphEntity, INode, java.lang.Comparable<FifteenPuzzleNode>

public class FifteenPuzzleNode
extends java.lang.Object
implements INode, java.lang.Comparable<FifteenPuzzleNode>

Represents a node in the Fifteen-Puzzle space.

    1 2 3 4
    5 6 7 8
    9101112
   131415 * 
 
To experiment with some of the searching algorithms, this class implements the Comparable interface by simply comparing the char[][] boards.

Since:
1.0
Version:
1.0, 6/15/08
Author:
George Heineman

Nested Class Summary
 
Nested classes/interfaces inherited from interface algs.debug.IGraphEntity
IGraphEntity.Formatter
 
Field Summary
static int EmptyMark
          Empty Mark.
static int MaxC
           
static int MaxR
          Max constants
 
Constructor Summary
FifteenPuzzleNode(int[][] b)
          Constructor for initiating and copying the state.
 
Method Summary
 int cell(int r, int c)
          Return contents of cell[r][c].
 int compareTo(FifteenPuzzleNode n)
          Offer rudimentary compareTo method by comparing boards.
 INode copy()
          Return a copy of the game state.
 boolean equals(java.lang.Object o)
          Determine equals via equivalence of state.
 boolean equivalent(INode n)
          Determine equivalence of state.
 int hashCode()
          Define the hashcode to be based on the key()
 boolean isAdjacentAndEmpty(int fromR, int fromC, int toR, int toC)
          Ensure that the empty square is in [toR][toC] and that [fromR][fromC] is adjacent horizontally or vertical.
 boolean isEmpty(int r, int c)
           
 java.lang.Object key()
          Return key that satisfies rotational symmetry.
 java.lang.String nodeLabel()
          Return string label for this entity.
 int score()
          Compute the score function on the board state.
 void score(int s)
          External agent rates the board and stores the score here.
 java.lang.Object storedData()
          Retrieve additional specific information stored with this search tree.
 java.lang.Object storedData(java.lang.Object o)
          Store additional information with this search tree, returning the old information that had been stored (if at all).
 boolean swap(int fromR, int fromC, int toR, int toC)
          Swap contents of neighboring cells.
 java.lang.String toString()
          Useful debugging method.
 DoubleLinkedList<IMove> validMoves()
          Given the game state, return the set of valid moves.
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 

Field Detail

EmptyMark

public static final int EmptyMark
Empty Mark.

See Also:
Constant Field Values

MaxR

public static int MaxR
Max constants


MaxC

public static int MaxC
Constructor Detail

FifteenPuzzleNode

public FifteenPuzzleNode(int[][] b)
                  throws java.lang.IllegalArgumentException
Constructor for initiating and copying the state.

Throws:
java.lang.IllegalArgumentException
Method Detail

copy

public INode copy()
Return a copy of the game state. Scoring Function is copied, but note that the storedData is not copied.

Specified by:
copy in interface INode

key

public java.lang.Object key()
Return key that satisfies rotational symmetry. Considering the four corners of the board, select the lowest digit and then read off the remaining eight positions in a fixed order as an integer. Return that value.

Specified by:
key in interface INode

equivalent

public boolean equivalent(INode n)
Determine equivalence of state.

Specified by:
equivalent in interface INode
Parameters:
n - State in question

equals

public boolean equals(java.lang.Object o)
Determine equals via equivalence of state.

Overrides:
equals in class java.lang.Object

hashCode

public int hashCode()
Define the hashcode to be based on the key()

Overrides:
hashCode in class java.lang.Object

score

public int score()
Compute the score function on the board state.

If cached value is present, use it instead of evaluating the functino again.

Specified by:
score in interface INode
Returns:
score of the board.

score

public void score(int s)
External agent rates the board and stores the score here.

Specified by:
score in interface INode

storedData

public java.lang.Object storedData(java.lang.Object o)
Description copied from interface: INode
Store additional information with this search tree, returning the old information that had been stored (if at all).

Returns the prior object that had been stored with the node.

Specified by:
storedData in interface INode
Parameters:
o - object to store with the INode object.

storedData

public java.lang.Object storedData()
Description copied from interface: INode
Retrieve additional specific information stored with this search tree.

Specified by:
storedData in interface INode

validMoves

public DoubleLinkedList<IMove> validMoves()
Given the game state, return the set of valid moves.

Specified by:
validMoves in interface INode

cell

public int cell(int r,
                int c)
Return contents of cell[r][c].


isAdjacentAndEmpty

public boolean isAdjacentAndEmpty(int fromR,
                                  int fromC,
                                  int toR,
                                  int toC)
Ensure that the empty square is in [toR][toC] and that [fromR][fromC] is adjacent horizontally or vertical.

Parameters:
fromR -
fromC -
toR -
toC -

swap

public boolean swap(int fromR,
                    int fromC,
                    int toR,
                    int toC)
Swap contents of neighboring cells. FromC must be the empty spot.


isEmpty

public boolean isEmpty(int r,
                       int c)

toString

public java.lang.String toString()
Useful debugging method.

Overrides:
toString in class java.lang.Object

nodeLabel

public java.lang.String nodeLabel()
Description copied from interface: IGraphEntity
Return string label for this entity.

Specified by:
nodeLabel in interface IGraphEntity

compareTo

public int compareTo(FifteenPuzzleNode n)
Offer rudimentary compareTo method by comparing boards.

based on String representation since we must be careful to ensure that a.compareTo(b) is the opposite of b.compareTo(a).

Specified by:
compareTo in interface java.lang.Comparable<FifteenPuzzleNode>

Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.