import java.awt.*; /** This class is responsible for actually solving the Knight's Tour problem of finding a Hamiltonian cycle for the knight on a chess board. The tour goes through each square on the board once, returning finally to the first square. The tour is only possible on boards with an even number of squares.
The class must first be instantiated with a GraphicalBoard object, the start square then set with setStartSquare(), and the actual calculation finally started with Thread.start() or by invoking run().
Graphical animation is off by default; it can be turned on using setAnimation(). The thread also displays a help text on the specified label depending on its internal state: running, animated, or completed. @see GraphicalBoard */ public class KnightThread extends Thread { private static final int DELAY = 300; // milliseconds private final GraphicalBoard board; private final Label label; private final int squares; private boolean anim = false; private int startx, starty; private int steps; /** Creates a new thread. @param board a properly initialized board. @param statuslabel label for displaying status text. */ public KnightThread(GraphicalBoard board, Label statuslabel) { if (!board.Invariant()) throw new RuntimeException("board not valid"); if (statuslabel == null) throw new RuntimeException("statuslabel == null"); this.board = board; this.label = statuslabel; squares = board.width * board.height; label.setText("Choose the starting square:"); label.repaint(); setPriority(Thread.MIN_PRIORITY); } /** Sets the start square. @param x x-index of start square. @param y y-index of start square. @return true if OK, false if start square is already set. @see KnightBoard#setStartSquare */ public boolean setStartSquare(int x, int y) { return (board.setStartSquare(startx = x, starty = y)); } /** Solves the Knight's Tour problem. The board must be properly initialized and the start square set. A RuntimeException is thrown if the board is not valid. The thread dies when either a solution has been found or all possible combinations have been tried. */ public void run() { if (!board.Invariant()) throw new RuntimeException("board not valid"); update(); if (solution(startx, starty)) label.setText("Solution found; " + (steps+1) + " positions tried."); else label.setText("No solution found; " + (steps+1) + " positions tried."); label.repaint(); board.repaint(); board.setResizable(true); if (!board.Invariant()) throw new RuntimeException("board not valid"); } /** Sets animation on or off. By default, animation is disabled. @param anim true enables animation, false disables. */ public void setAnimation(boolean anim) { this.anim = anim; } /** Updates the board and the help text. In animated mode, the number of positions checked thus far is displayed; otherwise, the label reads simply 'Running'. */ public void update() { if (isAlive()) { if (anim) label.setText("Running... Positions tried: " + steps); else label.setText("Running..."); label.repaint(); } board.repaint(); } /** A recursive function called for each new knight position tried. This implements a depth-first search that always chooses the unvisited square with the lowest value, ie. least exits first. If there are many, the one with the greatest distance from the start square is tried first, unless the board is smaller than 36 squares.
Positions leading to unreachable squares are not pursued further. This prunes the search tree to something like 1/20th of its original size. Arrays and insertion sort are used for maximum speed. @param x x-index of knight position. @param y y-index of knight position. @return true if a solution was found beginning from the specified position. @see KnightBoard */ private boolean solution(int x, int y) { /* // FOR DEBUGGING. Too slow for ordinary use... if (!board.Invariant()) throw new RuntimeException("board not valid"); */ int[][] adjlist = board.getAdjacencyList(x, y); int[][] al = new int[8][3]; // x, y, value int n = 0; // List all adjacent, unvisited, non-start squares to al[][]. for (int i = 0; adjlist[i][0] >= 0; ++i) { int ax = adjlist[i][0], ay = adjlist[i][1]; if (board.getMove(ax, ay) > 0) continue; int v = board.getValue(ax, ay); if (v == board.STARTSQUARE) continue; int d = distance(ax, ay); // Insertion sort first by value, then by distance from start square. // Efficient, since we have to copy the list anyway. int j; for (j = n; j > 0; --j) { if (v < al[j-1][2] || (v == al[j-1][2] && d > distance(al[j-1][0], al[j-1][1]))) { al[j][0] = al[j-1][0]; al[j][1] = al[j-1][1]; al[j][2] = al[j-1][2]; } else break; } al[j][0] = adjlist[i][0]; al[j][1] = adjlist[i][1]; al[j][2] = v; ++n; } // Try all possibilities in order for (int i = 0; i < n; ++i) { int ax = al[i][0], ay = al[i][1]; if (!board.moveKnight(ax, ay)) { // Bad idea: unreachable squares. Skip. board.undoMove(ax, ay); continue; } ++steps; pause(); // Are we finished? if (board.getWaysBack() == 0) { board.moveKnight(startx, starty); return true; } // Recursively call ourselves to find a solution... if (solution(ax, ay)) return true; else { board.undoMove(ax, ay); pause(); } } // All possibilities checked. return false; } /** Calculates the Pythagorean (x^2 + y^2) distance of the specified square from the start square, unless the board is smaller than 36 squares. @param x x-index of square. @param y y-index of square. @return distance from start square, or zero if the board is small. */ private int distance(int x, int y) { if (squares < 36) return 0; int dx = startx - x, dy = starty - y; return (dx*dx + dy*dy); } /** In animated mode, updates the board on screen and pauses for a while. */ private void pause() { if (anim) { update(); try { sleep(DELAY); } catch (InterruptedException e) { } } } }