The Knight's Tour
Volume Number: 14
Issue Number: 11
Column Tag: Programming Puzzles
by F.C. Kuechmann
A seemingly simple problem with thousands of solutions
There is a class of problems that, though seemingly simple in concept, involve
numbers so large that the time or material required for solution renders them
effectively impossible to solve manually within a human lifetime. The "grains of wheat
on a chessboard" described by Gamow [1988] is one of the simpler and more easily
explained examples of this sort of problem. We start with a single grain of wheat on
the first square of the board, two grains on the second, four on the third, eight on the
fourth, and so on. Each square receiving twice the number of grains as the previous
square, until all 64 squares are occupied. Simple enough, right? Gamow suggests that
it would take the entire world's wheat production for 2000 years to fill the board! In
this article we're going to look at a similar challenge and show how to solve it with
your Macintosh.
The Problem
The "knight's tour" is another chessboard problem that involves deceptively large
numbers (this one is simpler though - we don't need any wheat). In the game of chess
the knight can move only in L-shaped patterns consisting of two squares one direction
and a single square perpendicular to the direction of the first two. There are eight
possible moves from any given starting square, shown in Figure 1. From the 16
squares at the middle of a chessboard all eight moves can be executed without leaving
the board; Away from the center fewer moves are executable because the knight would
end up off the board entirely. In general, a knight in row 1 or 8, or column 1 or 8, can
execute only 4 moves. A knight in row 2 or 7, or column 2 or 7, can execute 6 moves.
A knight on a corner square has only two executable moves.
Figure 1. The eight possible moves of a knight.
The object of the knight's tour is, from a given starting square, to visit each square on
the board exactly once.
From many of the 64 possible starting squares no complete tours are possible,
whereas others offer thousands. My experiments have shown that, if there is at least
one complete tour from a given starting square, there is a large number of complete
tours from that square.
Starting at square one, we test eight possible moves. Each time a move is executed, we
must test another eight moves, then another eight, and another, until we have either
visited all 64 squares or exhausted the possible moves. At square 63, eight moves
must be considered. At square 62, 8^2 moves must be tested. More generally, at any
given square n, the number of moves to be tested is 8^(64-n), with a significantly
smaller number of executable moves. If the knight's tour were as straightforward as
the grains of wheat problem, determining all possible solutions from any given
starting square would be described by a geometric progression of
8+(8^2)+(8^3)..+(8^62)+(8^63) - or 8^64 tests. That is not a small number! In
fact, we get eight new tests only when we actually execute a move, so the number of
required tests is somewhat smaller.
A human with a chessboard, a knight, and a pad of paper to record moves, together with
a well-conceived systematic method and fast hands, would require so much time to
derive even a single solution that it is practically if not theoretically impossible using
hand methods.
1 38 59 36 43 48 57 52
60 35 2 49 58 51 44 47
39 32 37 42 3 46 53 56
34 61 40 27 50 55 4 45
31 10 33 62 41 26 23 54
18 63 28 11 24 21 14 5
9 30 19 16 7 12 25 22
64 17 8 29 20 15 6 13
Figure 2. One complete knight's tour.
Niklaus Wirth [1976,1986] describes a trial-and-error approach to the problem
using recursion and backtracking, with soucecode in Pascal [1976] and Modula-2
[1986]. Unlike a human, a computer can find solutions quite easily, although it can
still take a great deal of time. With Wirth's method and CodeWarrior Pascal, the
solution shown in Figure 2 requires 66,005,601 possible moves to be considered,
8,250,732 moves to be executed, and occupies 35 seconds of time on a PPC Mac
6500/225. A total of 107 solutions for the same starting square were found in just
under two hours with 16,114,749,106 total position tests and 2,014,343,776
moves; 12 hours got more than a thousand solutions without testing more than a
fraction of the possible moves. At that rate finding all solutions for the entire board
would take a very long time. Because of symmetries, however, we could simply divide
the board into four 16-square quadrants, Figure 3, and find the solutions for any
quadrant, then calculate the solutions for the remaining quadrants by mirroring.
1
2
3
4
Figure 3. The board as quadrants.
Solutions for quadrant 2 mirror those for quadrant 1 on the vertical axis. Quadrants 3
and 4 mirror quadrants 1 and 2 on the horizontal axis.
The Program
The chess board occupies the leftmost 2/3 of the window, with a control panel on the
right. Top left of the control panel are three times...
1. total time
2. time on current starting square
3. time since the most recent solution was found.
Tour 1 has only number 1; Tour 2 has numbers 1 and 3.
Top right is the current rotation pattern for testing possible moves; the patterns are
toggled between 1 and 2 by clicking the Pat button, and the position is selected by
clicking the Rot button. Below the time are statistics on move tests, moves,
backtracks, and the maximum backtrack level.
Buttons for starting, pausing, pattern and rotation selection, update board status, tour
selection [eight options], and speed 1-9 follow at bottom right.
The EvUp/SolUp button toggles update status. In the default EvUp mode the board is
updated whenever the events are tested, and those intervals are determined by the
speed setting; in SolUp mode the board is updated only if and when a complete tour is
achieved. Since testing for events and updating the board require large amounts of time
relative to calculating the knight's moves, higher execution speeds offer less frequent
event testing and board updating.
The Tours
The eight tour options are:
• Tour 1 - finds one solution from the starting square and terminates;
starting square selected by clicking on it.
• Tour 2 - finds all solutions from starting square; starting square
selected by clicking on it.
• Tour 3 - starts at row 1, column 1 and moves through the entire board;
if a solution is found, the next square becomes the starting square.
• Tour 4 - starts at row 1, column 1 and moves through the entire board;
finds all solutions for each square.
• Quad 1 - finds all solutions for upper left quadrant.
• Quad 2 - finds all solutions for upper right quadrant.
• Quad 3 - finds all solutions for lower left quadrant.
• Quad 4 - finds all solutions for lower right quadrant.
Several program options are selected by menu.
The minimum is no pause, the maximum 30 seconds, the default 1 second.
starting square. In the cases of tours 1 and 2, pursuit of solutions ceases at
that point; with the other six tours execution continues at the next square. The
minimum selection is 2 minutes; the maximum specific interval 4 weeks. The
default in no time limit.
• The Save menu offers options of No save, Save as text, and Save as
records. The default is No save.
Drawing the Chess Board
The empty chess board is drawn and optionally initialized by calling the procedure in
Listing 1. It calls the code in Listing 2 64 times, passing row, column and flag values.
The flag determines whether the global array ggChessBd, which stores the current
moves, is affected. If the flag is TRUE, the array location ggChessBd[row,column] is
set to zero. The flag is TRUE during initialization, FALSE during all other updates.
Listing 1.
ClearTheBoard
procedure ClearTheBoard(flag:boolean);
{clear the board by drawing blank squares at}
{all 64 positions}
var
row,column:integer;
begin
for column:=1 to ggN do
for row:=1 to ggN do
SnuffKnight(row,column,flag);
end;
The SnuffKnight procedure in Listing 2 erases the square at the location given by row
and column by drawing a light or dark empty square.
Listing 2.
SnuffKnight
procedure SnuffKnight (row,column:integer;flag:boolean);
{erases the move number at the specified row and column}
{position by drawing an empty square there}
var
vOffset,hOffset,height,width:integer;
pictureRect:Rect;
thePicture:PicHandle;
begin
SetPort(ggKnightWindow);
ggTourRect:=ggKnightWindow^.portRect;
if column mod 2=0 then