Class KnightThread

java.lang.Object
   |
   +----java.lang.Thread
           |
           +----KnightThread

public class KnightThread
extends Thread
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 Also:
GraphicalBoard

Variable Index

 o anim
 o board
 o DELAY
 o label
 o squares
 o startx
 o starty
 o steps

Constructor Index

 o KnightThread(GraphicalBoard, Label)
Creates a new thread.

Method Index

 o distance(int, int)
Calculates the Pythagorean (x^2 + y^2) distance of the specified square from the start square, unless the board is smaller than 36 squares.
 o pause()
In animated mode, updates the board on screen and pauses for a while.
 o run()
Solves the Knight's Tour problem.
 o setAnimation(boolean)
Sets animation on or off.
 o setStartSquare(int, int)
Sets the start square.
 o solution(int, int)
A recursive function called for each new knight position tried.
 o update()
Updates the board and the help text.

Variables

 o DELAY
 private static final int DELAY
 o board
 private final GraphicalBoard board
 o label
 private final Label label
 o squares
 private final int squares
 o anim
 private boolean anim
 o startx
 private int startx
 o starty
 private int starty
 o steps
 private int steps

Constructors

 o KnightThread
 public KnightThread(GraphicalBoard board,
                     Label statuslabel)
Creates a new thread.

Parameters:
board - a properly initialized board.
statuslabel - label for displaying status text.

Methods

 o setStartSquare
 public boolean setStartSquare(int x,
                               int y)
Sets the start square.

Parameters:
x - x-index of start square.
y - y-index of start square.
Returns:
true if OK, false if start square is already set.
See Also:
setStartSquare
 o run
 public void run()
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.

Overrides:
run in class Thread
 o setAnimation
 public void setAnimation(boolean anim)
Sets animation on or off. By default, animation is disabled.

Parameters:
anim - true enables animation, false disables.
 o update
 public void update()
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'.

 o solution
 private boolean solution(int x,
                          int y)
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.

Parameters:
x - x-index of knight position.
y - y-index of knight position.
Returns:
true if a solution was found beginning from the specified position.
See Also:
KnightBoard
 o distance
 private int distance(int x,
                      int y)
Calculates the Pythagorean (x^2 + y^2) distance of the specified square from the start square, unless the board is smaller than 36 squares.

Parameters:
x - x-index of square.
y - y-index of square.
Returns:
distance from start square, or zero if the board is small.
 o pause
 private void pause()
In animated mode, updates the board on screen and pauses for a while.