/** 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). <P>    Note: subclasses Canvas only to emulate multiple inheritance for    GraphicalBoard.    @see GraphicalBoard    @see KnightThread*/public class KnightBoard extends java.awt.Canvas {    /** Value of the starting square as returned by getValue().        Greater than any other valid weight values.        @see #getValue    */    public static final int STARTSQUARE = Integer.MAX_VALUE;    /** Minimum width and height of the board in squares. */    public static final int MIN_DIMENSION = 5;    /** Width of the board in squares. */    public final int width;    /** Height of the board in squares. */    public final int height;    private int[][] value;              // Value of square    private int[][] move;               // Number of move    private final boolean[][] wayback;  // Is adjacent to start square?    private final int[][][][] adjlist;  // Adjacency list    private int waysback = 0;    private int nummoves = 0;    /** Constructs a board of the specified size.        @param width width of the board in squares.        @param height height of the board in squares.    */    public KnightBoard(int width, int height) {        if (width < MIN_DIMENSION || height < MIN_DIMENSION)            throw new RuntimeException("board dimension too small");        this.width = width;        this.height = height;        move = new int[width][height];        wayback = new boolean[width][height];        adjlist = new int[width][height][9][2];        value = new int[width][height];        initBoard();    }    /** 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.        @param x x-index of start square.        @param y y-index of start square.        @return true if OK, false if start square already set.        @see #STARTSQUARE    */    public boolean setStartSquare(int x, int y) {        if (nummoves == 0 && waysback == 0) {            value[x][y] = STARTSQUARE;            for (int i = 0; adjlist[x][y][i][0] >= 0; ++i) {                int jx = adjlist[x][y][i][0];                int jy = adjlist[x][y][i][1];                wayback[jx][jy] = true;                ++waysback;            }            return true;        } else            return false;    }    /** Moves the knight to the specified square, updating adjacent values.        Also checks for possibly resulting unreachable squares.        @param x x-index of the square to move to.        @param y y-index of the square to move to.        @return true if successful; false if unreachable squares resulted,        in which case the move should probably be undone.                @see #undoMove    */    public boolean moveKnight(int x, int y) {        move[x][y] = ++nummoves;        if (wayback[x][y])            --waysback;        if (!changeAdjacentValues(x, y, -1))            return false;        if (waysback == 0 && !isFinished(x, y))            return false;        return true;    }    /** Undoes the move to the specified square, updating adjacent values.        If the cancelled move is not the most recent one, the result is        undefined.        @param x x-index of the knight.        @param y y-index of the knight.        @see #moveKnight    */    public void undoMove(int x, int y) {        --nummoves;        move[x][y] = 0;        changeAdjacentValues(x, y, 1);        if (wayback[x][y])            ++waysback;    }    /** Returns the number of moves done thus far.        @return number of moves.    */    public int getNumMoves() {        return nummoves;    }    /** Returns the value of the specified square. The value is the number of        exits, ie. unvisited squares currently reachable from the specified one.        @param x x-index of square.        @param y y-index of square.        @return value of the square.    */    public int getValue(int x, int y) {        return value[x][y];    }    /** Similar to getValue() but with range checking.        @param x x-index of square.        @param y y-index of square.        @return value of the square or Integer.MIN_VALUE if index out of range.        @see #getValue    */    public int getValueAt(int x, int y) {        if (x >= 0 && x < width && y >= 0 && y < height)            return value[x][y];        else            return Integer.MIN_VALUE;    }    /** Returns the number of the move that visited the specified square.        @param x x-index of square.        @param y y-index of square.        @return number of move, zero if unvisited.    */    public int getMove(int x, int y) {        return move[x][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!        @param x x-index of square.        @param y y-index of square.        @return 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.    */    public int[][] getAdjacencyList(int x, int y) {        return adjlist[x][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.    */    public boolean isFinished(int x, int y) {        if (nummoves == width*height - 1 && move[x][y] == nummoves && wayback[x][y])            return true;        else            return false;    }    /** 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.        @return number of unvisited squares adjacent to the start square.    */    public int getWaysBack() {        return waysback;    }    /** 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.        @return true if the board is valid; false means a serious bug!    */    public boolean Invariant() {        if (nummoves < 0 || nummoves > width*height)            return false;        if (value == null || move == null || wayback == null || adjlist == null)            return false;        int moves_count = 0, wayback_count = 0, max_move = 0;        int startx = -1, starty = -1;        // Go through all squares, count number of moves and ways back        for (int y = 0; y < height; ++y) {            for (int x = 0; x < width; ++x) {                int this_value = 0;                // There should be only one start square                if (value[x][y] == STARTSQUARE) {                    if (wayback_count != 0)                        return false;                    if (move[x][y] != 0 && move[x][y] != width*height)                        return false;                    startx = x;                    starty = y;                }                if (value[x][y] < 0 || move[x][y] < 0)                    return false;                if (move[x][y] > 0) {                    ++moves_count;                    max_move = (move[x][y] > max_move) ? move[x][y] : max_move;                }                // Go through the adjacency list, calculate value                int i;                for (i = 0; adjlist[x][y][i][0] >= 0; ++i) {                    int jx = adjlist[x][y][i][0];                    int jy = adjlist[x][y][i][1];                                        if (move[jx][jy] == 0)                        ++this_value;                    // Do we have wayback[]s in right places?                    if (value[x][y] == STARTSQUARE && move[jx][jy] == 0) {                        if (!wayback[jx][jy])                            return false;                        ++wayback_count;                    }                }                // At least one neighbor                if (i < 1)                    return false;                // Does the calculated value match?                if (value[x][y] != STARTSQUARE && this_value != value[x][y])                    return false;            }        }        // Do the number of moves and ways back match?        if (moves_count != nummoves || max_move != nummoves || wayback_count != waysback)            return false;            // If the tour is not finished, stop here        if (nummoves < width*height)            return true;        // Check that all steps are adjacent and in correct order        int x = startx, y = starty;        for (int n = 1; n <= nummoves; ++n) {            boolean found = false;            for (int i = 0; adjlist[x][y][i][0] >= 0; ++i) {                int jx = adjlist[x][y][i][0];                int jy = adjlist[x][y][i][1];                if (move[jx][jy] == n) {                    found = true;                    x = jx;                    y = jy;                    break;                }            }            if (!found)                return false;        }        // All checked!        return true;    }    /** 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!        @param x x-index of square.        @param y y-index of square.        @param offset the value to be added to the adjacent squares.        @see #getWaysBack    */    private boolean changeAdjacentValues(int x, int y, int offset) {        boolean orphans = false;        for (int i = 0; adjlist[x][y][i][0] >= 0; ++i) {            int jx = adjlist[x][y][i][0];            int jy = adjlist[x][y][i][1];                        if (value[jx][jy] != STARTSQUARE) {                if (((value[jx][jy] += offset) == 0 && move[jx][jy] == 0) ||                    (wayback[jx][jy] && move[jx][jy] == 0 &&                     value[jx][jy] == 1 && nummoves < width*height - 2))                    orphans = true;            }        }        return !orphans;    }    /** Initializes the board, computing the adjacency list and value        for each square in the board. Called from the constructor.        @see #getAdjacencyList        @see #getValue    */    private void initBoard() {        for (int y = 0; y < height; ++y) {            for (int x = 0; x < width; ++x) {                int i = 0;                if (getValueAt(x - 2, y - 1) >= 0) {                    adjlist[x][y][i][0] = x - 2; adjlist[x][y][i++][1] = y - 1; }                if (getValueAt(x + 2, y - 1) >= 0) {                    adjlist[x][y][i][0] = x + 2; adjlist[x][y][i++][1] = y - 1; }                if (getValueAt(x - 2, y + 1) >= 0) {                    adjlist[x][y][i][0] = x - 2; adjlist[x][y][i++][1] = y + 1; }                if (getValueAt(x + 2, y + 1) >= 0) {                    adjlist[x][y][i][0] = x + 2; adjlist[x][y][i++][1] = y + 1; }                if (getValueAt(x - 1, y - 2) >= 0) {                    adjlist[x][y][i][0] = x - 1; adjlist[x][y][i++][1] = y - 2; }                if (getValueAt(x + 1, y - 2) >= 0) {                    adjlist[x][y][i][0] = x + 1; adjlist[x][y][i++][1] = y - 2; }                if (getValueAt(x - 1, y + 2) >= 0) {                    adjlist[x][y][i][0] = x - 1; adjlist[x][y][i++][1] = y + 2; }                if (getValueAt(x + 1, y + 2) >= 0) {                    adjlist[x][y][i][0] = x + 1; adjlist[x][y][i++][1] = y + 2; }                adjlist[x][y][i][0] = adjlist[x][y][i][1] = -1;                  value[x][y] = i;            }        }    }}