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
-
anim
-
-
board
-
-
DELAY
-
-
label
-
-
squares
-
-
startx
-
-
starty
-
-
steps
-
-
KnightThread(GraphicalBoard, Label)
- Creates a new thread.
-
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.
-
pause()
- In animated mode, updates the board on screen and pauses for a while.
-
run()
- Solves the Knight's Tour problem.
-
setAnimation(boolean)
- Sets animation on or off.
-
setStartSquare(int, int)
- Sets the start square.
-
solution(int, int)
- A recursive function called for each new knight position tried.
-
update()
- Updates the board and the help text.
DELAY
private static final int DELAY
board
private final GraphicalBoard board
label
private final Label label
squares
private final int squares
anim
private boolean anim
startx
private int startx
starty
private int starty
steps
private int steps
KnightThread
public KnightThread(GraphicalBoard board,
Label statuslabel)
- Creates a new thread.
- Parameters:
- board - a properly initialized board.
- statuslabel - label for displaying status text.
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
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
setAnimation
public void setAnimation(boolean anim)
- Sets animation on or off. By default, animation is disabled.
- Parameters:
- anim - true enables animation, false disables.
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'.
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
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.
pause
private void pause()
- In animated mode, updates the board on screen and pauses for a while.