Algorithm
Development Kit 1.0

algs.model.problems.eightpuzzle
Class EightPuzzleNode

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

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

Represents a node in the Eight-Puzzle space.

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

Note there is a static global variable debug which controls the way that nodeLabel() computes its string value.

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 boolean debug
          Since this node is responsible for its formatted output in debugging, we place that localized control here.
static int EmptyMark
          Empty Mark.
static int MaxC
          Max constant for number of columns.
static int MaxR
          Max constant for number of rows.
 
Constructor Summary
EightPuzzleNode(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(EightPuzzleNode 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)
          Determine is the given (r,c) in the board is empty.
 java.lang.Object key()
          Return key that satisfies rotational symmetry.
 java.lang.String nodeLabel()
          Return label to appear within the debugger output.
 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()
          Return the data stored with the node.
 java.lang.Object storedData(java.lang.Object o)
          Store the given piece of information with the node and return the last piece of information which had been stored with the node.
 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 constant for number of rows.


MaxC

public static int MaxC
Max constant for number of columns.


debug

public static boolean debug
Since this node is responsible for its formatted output in debugging, we place that localized control here. If true, then the generated DOTTY nodes show the score with each node. Make true for A*Search, false for DFS/BFS, when generating the images in chapter 7.

Constructor Detail

EightPuzzleNode

public EightPuzzleNode(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 - the state being compared against.

equals

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

Overrides:
equals in class java.lang.Object
Parameters:
o - object being compared against.

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 function 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
Parameters:
s - designated score for this node.

storedData

public java.lang.Object storedData(java.lang.Object o)
Store the given piece of information with the node and return the last piece of information which had been stored with the node.

If null is returned, then no prior information was stored.

Specified by:
storedData in interface INode
Parameters:
o - object to be stored with the node.

storedData

public java.lang.Object storedData()
Return the data stored with the node.

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].

Parameters:
r - source location row
c - source location column

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 - source location row
fromC - source location column
toR - destination location row
toC - destination location column

swap

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

Parameters:
fromR - source location row
fromC - source location column
toR - destination location row
toC - destination location column

isEmpty

public boolean isEmpty(int r,
                       int c)
Determine is the given (r,c) in the board is empty.

Parameters:
r - row to be checked.
c - column to be checked.

toString

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

Overrides:
toString in class java.lang.Object

nodeLabel

public java.lang.String nodeLabel()
Return label to appear within the debugger output.

Specified by:
nodeLabel in interface IGraphEntity

compareTo

public int compareTo(EightPuzzleNode 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).

Needed if, for example, node is ever to appear in a data structure that stores information by comparisons.

Specified by:
compareTo in interface java.lang.Comparable<EightPuzzleNode>
Parameters:
n - node with which to compare.

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.