Class KnightBoard

java.lang.Object
   |
   +----java.awt.Component
           |
           +----java.awt.Canvas
                   |
                   +----KnightBoard

public class KnightBoard
extends Canvas
A variable-size chess board that supports finding a complete tour, or Hamiltonian cycle, for the knight on the board. The dimensions (width and height) of the board may be specified, but must be at least five. Individual squares are referenced by their x and y indices, the first one being (0, 0).

Note: subclasses Canvas only to emulate multiple inheritance for GraphicalBoard.

See Also:
GraphicalBoard, KnightThread

Variable Index

 o adjlist
 o height
Height of the board in squares.
 o MIN_DIMENSION
Minimum width and height of the board in squares.
 o move
 o nummoves
 o STARTSQUARE
Value of the starting square as returned by getValue().
 o value
 o wayback
 o waysback
 o width
Width of the board in squares.

Constructor Index

 o KnightBoard(int, int)
Constructs a board of the specified size.

Method Index

 o changeAdjacentValues(int, int, int)
Changes the values of the squares adjacent to the specified one by the offset.
 o getAdjacencyList(int, int)
Returns an adjacency list, or rather an array, of the squares reachable directly from the specified one.
 o getMove(int, int)
Returns the number of the move that visited the specified square.
 o getNumMoves()
Returns the number of moves done thus far.
 o getValue(int, int)
Returns the value of the specified square.
 o getValueAt(int, int)
Similar to getValue() but with range checking.
 o getWaysBack()
Returns the number of unvisited squares reachable directly from the start square; in other words, the number of ways back to it.
 o initBoard()
Initializes the board, computing the adjacency list and value for each square in the board.
 o Invariant()
A quite complete invariant test for the KnightBoard class.
 o isFinished(int, int)
Checks if the specified square is next-to-last in the tour.
 o moveKnight(int, int)
Moves the knight to the specified square, updating adjacent values.
 o setStartSquare(int, int)
Sets the first (and last) square of the tour.
 o undoMove(int, int)
Undoes the move to the specified square, updating adjacent values.

Variables

 o STARTSQUARE
 public static final int STARTSQUARE
Value of the starting square as returned by getValue(). Greater than any other valid weight values.

See Also:
getValue
 o MIN_DIMENSION
 public static final int MIN_DIMENSION
Minimum width and height of the board in squares.

 o width
 public final int width
Width of the board in squares.

 o height
 public final int height
Height of the board in squares.

 o value
 private int value[][]
 o move
 private int move[][]
 o wayback
 private final boolean wayback[][]
 o adjlist
 private final int adjlist[][][][]
 o waysback
 private int waysback
 o nummoves
 private int nummoves

Constructors

 o KnightBoard
 public KnightBoard(int width,
                    int height)
Constructs a board of the specified size.

Parameters:
width - width of the board in squares.
height - height of the board in squares.

Methods

 o setStartSquare
 public boolean setStartSquare(int x,
                               int y)
Sets the first (and last) square of the tour. The square is marked reserved - its value becomes STARTSQUARE, but the knight is not actually moved to it. The intent is to move to this square as the last step that completes the tour.

Parameters:
x - x-index of start square.
y - y-index of start square.
Returns:
true if OK, false if start square already set.
See Also:
STARTSQUARE
 o moveKnight
 public boolean moveKnight(int x,
                           int y)
Moves the knight to the specified square, updating adjacent values. Also checks for possibly resulting unreachable squares.

Parameters:
x - x-index of the square to move to.
y - y-index of the square to move to.
Returns:
true if successful; false if unreachable squares resulted, in which case the move should probably be undone.
See Also:
undoMove
 o undoMove
 public void undoMove(int x,
                      int y)
Undoes the move to the specified square, updating adjacent values. If the cancelled move is not the most recent one, the result is undefined.

Parameters:
x - x-index of the knight.
y - y-index of the knight.
See Also:
moveKnight
 o getNumMoves
 public int getNumMoves()
Returns the number of moves done thus far.

Returns:
number of moves.
 o getValue
 public int getValue(int x,
                     int y)
Returns the value of the specified square. The value is the number of exits, ie. unvisited squares currently reachable from the specified one.

Parameters:
x - x-index of square.
y - y-index of square.
Returns:
value of the square.
 o getValueAt
 public int getValueAt(int x,
                       int y)
Similar to getValue() but with range checking.

Parameters:
x - x-index of square.
y - y-index of square.
Returns:
value of the square or Integer.MIN_VALUE if index out of range.
See Also:
getValue
 o getMove
 public int getMove(int x,
                    int y)
Returns the number of the move that visited the specified square.

Parameters:
x - x-index of square.
y - y-index of square.
Returns:
number of move, zero if unvisited.
 o getAdjacencyList
 public int[][] getAdjacencyList(int x,
                                 int y)
Returns an adjacency list, or rather an array, of the squares reachable directly from the specified one. The return value is a reference - the contents of the array may not be changed!

Parameters:
x - x-index of square.
y - y-index of square.
Returns:
reference to a two-dimensional array of size [9][2]. The first index enumerates the adjacent squares; 0 and 1 in the second correspond to their x and y coordinates. The list is terminated with negative coordinates.
 o isFinished
 public boolean isFinished(int x,
                           int y)
Checks if the specified square is next-to-last in the tour. If it is, the tour can be completed by moving the knight to the start square.

 o getWaysBack
 public int getWaysBack()
Returns the number of unvisited squares reachable directly from the start square; in other words, the number of ways back to it. If the return value is zero, but the tour is not finished, the start square is unreachable and the tour is impossible to complete.

Returns:
number of unvisited squares adjacent to the start square.
 o Invariant
 public boolean Invariant()
A quite complete invariant test for the KnightBoard class. Checks the validity of the various parameters and squares of the board. Useful for debugging and testing purposes.

Returns:
true if the board is valid; false means a serious bug!
 o changeAdjacentValues
 private boolean changeAdjacentValues(int x,
                                      int y,
                                      int offset)
Changes the values of the squares adjacent to the specified one by the offset. If the change results in either 1) unvisited squares with value zero, or 2) wayback-squares with value one, false is returned, as those squares are unreachable!

Parameters:
x - x-index of square.
y - y-index of square.
offset - the value to be added to the adjacent squares.
See Also:
getWaysBack
 o initBoard
 private void initBoard()
Initializes the board, computing the adjacency list and value for each square in the board. Called from the constructor.

See Also:
getAdjacencyList, getValue