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
-
adjlist
-
-
height
- Height of the board in squares.
-
MIN_DIMENSION
- Minimum width and height of the board in squares.
-
move
-
-
nummoves
-
-
STARTSQUARE
- Value of the starting square as returned by getValue().
-
value
-
-
wayback
-
-
waysback
-
-
width
- Width of the board in squares.
-
KnightBoard(int, int)
- Constructs a board of the specified size.
-
changeAdjacentValues(int, int, int)
- Changes the values of the squares adjacent to the specified one
by the offset.
-
getAdjacencyList(int, int)
- Returns an adjacency list, or rather an array, of the squares
reachable directly from the specified one.
-
getMove(int, int)
- Returns the number of the move that visited the specified square.
-
getNumMoves()
- Returns the number of moves done thus far.
-
getValue(int, int)
- Returns the value of the specified square.
-
getValueAt(int, int)
- Similar to getValue() but with range checking.
-
getWaysBack()
- Returns the number of unvisited squares reachable directly from
the start square; in other words, the number of ways back to it.
-
initBoard()
- Initializes the board, computing the adjacency list and value
for each square in the board.
-
Invariant()
- A quite complete invariant test for the KnightBoard class.
-
isFinished(int, int)
- Checks if the specified square is next-to-last in the tour.
-
moveKnight(int, int)
- Moves the knight to the specified square, updating adjacent values.
-
setStartSquare(int, int)
- Sets the first (and last) square of the tour.
-
undoMove(int, int)
- Undoes the move to the specified square, updating adjacent values.
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
MIN_DIMENSION
public static final int MIN_DIMENSION
- Minimum width and height of the board in squares.
width
public final int width
- Width of the board in squares.
height
public final int height
- Height of the board in squares.
value
private int value[][]
move
private int move[][]
wayback
private final boolean wayback[][]
adjlist
private final int adjlist[][][][]
waysback
private int waysback
nummoves
private int nummoves
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.
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
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
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
getNumMoves
public int getNumMoves()
- Returns the number of moves done thus far.
- Returns:
- number of moves.
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.
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
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.
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.
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.
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.
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!
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
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