The Knight's Tour is an intriguing little exercise developed by
the mathematician Euler. The problem in itself is rather simple - is it
possible for the knight, making only moves that are legitimate to a knight, to
visit every single cell on the chess-board once and only once? We are at the liberty of choosing the starting position of the knight. Our exercise is to solve this problem programmatically.
We proceed to solve the riddle by the development of a suitable heuristics or strategy. The trick is to compute for each cell, the number of other cells from which it is accessible, i.e., for any given position, count the number of other positions from where it is accessible. A table illustrating this has been prepared and given below for all the 64 cells.
|
2 |
3 |
4 |
4 |
4 |
4 |
3 |
2 |
|
3 |
4 |
6 |
6 |
6 |
6 |
4 |
3 |
|
4 |
6 |
8 |
8 |
8 |
8 |
6 |
4 |
|
4 |
6 |
8 |
8 |
8 |
8 |
6 |
4 |
|
4 |
6 |
8 |
8 |
8 |
8 |
6 |
4 |
|
4 |
6 |
8 |
8 |
8 |
8 |
6 |
4 |
|
3 |
4 |
6 |
6 |
6 |
6 |
4 |
3 |
|
2 |
3 |
4 |
4 |
4 |
4 |
3 |
2 |
Here therefore, if we consider the bottom-left hand corner cell, we can immediately ascertain that it is accessible only from 2 other cells. Therefore, for every move, the knight merely needs to inspect the cell's accessibility value and travel to that cell which has the least value.
A program implementing the heuristics discussed above has been developed and deployed below in the form of a Java applet. The simulation begins when the "Start" button is clicked. The knight is represented on the board by the alphabet 'K'. Every cell that the knight visits is shaded a gentle cream and marked by a '*' symbol. The cell from which the knight starts the simulation is colored sky-blue. The simulation proceeds until a game has been completed from every cell on the board thus comprising 64 games in all. A text-box has been provided in the applet to control the time spent between moves measured in terms of milliseconds. The user is required to enter the desired value in the text-box and press the return key. To make the moves a bit quicker therefore, you would choose a lower value, enter it into the text-box and press the return key.
It would be a good idea to place the mouse-pointer on the applet while the applet is running in order to view the messages appearing on the status-bar.
Knight's Tour Applet
If you would like to download the source-code (5 KB), please click here.