The Knight's Tour Revisited
GEEK STUFF, by F.C. Kuechmann


The Knight's Tour Revisited
Contemplating a very large number

by F.C. Kuechmann
Updated: 10/15/06

DOWNLOAD SOURCE CODE PACKAGE

AN IMMODEST PROPOSAL
Recreational mathematics is one of those things the bean counters don’t understand. Mental calisthenics don’t show up explicitly on the quarterly bottom line. Bean counters, of course, though claiming to be carbon–based life forms possessing intelligence, also can’t understand that kaffe mocha is an essential programming utility.

One of the perennial problems in recreational mathematics is the knight’s tour. There are still, after all these centuries, a few unanswered questions in recreational mathematics - how many knight's tours are there on an 8-by-8 chess board [the number is astronomically large and estimates vary greatly]? How many magic and semi-magic tours [I know of 8 semi-magic]?

I propose that we Pascal fans set out to answer the questions. The applications and code base we could create could be widely used in college and university algorithms courses. Even in this day of ubiquitous C, Wirth's "Algorithms and Data Structures" is one of the most widely used algorithms textbooks with its Pascal/Modula sample code. In the November 1998 issue of MacTech I published an article on the knight’s tour problem. That article can be found on the web in the MacTech article archives. A compiled Classic app and CodeWarrior project for the program described in the article, which uses the recursive, exhaustive search approach described by Wirth in an event–driven GUI Mac implementation can be found at MacTech's FTP site.

Is anybody interested?

The article subtitle read “A seemingly simple problem with thousands of solutions”. That is a major understatement and was intended humorously. In fact, the number of complete tours possible on an 8-by-8 chess board is so large it is currently unknown and can only be estimated. What is certain is that it is a very large number that is evenly divisible by four. Several estimates can be found on the web. One estimate is 33,439,123,484,294 (Loebbing and Wegener) – that’s 33 trillion, while another is only 13,267,364,410,532 (McKay, 1997) - a bit over 13 trillion.

Beginning in mid-1999 I ran the fastest Mac then available, a Blue-and-White G3/450, for nearly a year and found several million tours after testing only a fraction of the possibilities for a single starting square. An exhaustive search of all 64 possible starting squares using Wirth’s algorithm as described in my article would obviously take a very long time, even using the much faster computers available today.

Let’s see if there’s a reasonable way to find, and count, all possible tours without testing all 64 starting squares.


A CLOSED TOUR PROVES A POINT
A closed tour is one in which move 64 is one knight move away from the starting square. Thus the tour could repeat in an infinite loop. See Figure 1 for an example.

The fact that there are closed tours tells us that there are complete tours possible starting from every square on the board, and a bit of experience shows that, for any given starting square, if there is one tour there are thousands. The estimates above suggest that there are, on average, at least billions of tours from each starting square.


Figure 1 - A closed knight's tour


THE VALUE OF SYMMETRY
Given the symmetry of an 8-by-8 board, a combination of horizontal and vertical axis mirrors would reduce the number of squares needing to be tested to those in any single quadrant - 16, and rotations would seem to provide additional


Figure 2: A knight's tour

FLIP, FLOP, ROTATE
Figure 2 shows a complete tour starting from row 1, column 4. If we flip the board on the vertical axis, we get the tour in Figure 3.


Figure 3- A mirror image of Figure 2.

This symmetry exists for any tour starting from any square. If we mirror the Figure 2 tour on the horizontal axis, we get Figure 4.


Figure 4-Horizontal axis mirror of Figure 2.


If we rotate Figure 2 by 90 degrees clockwise, we get Figure 5.


Figure 5-90-degree CW rotation of Figure 2.


Mirroring Figure 5 on the vertical and horizontal axes gives us tours for three more starting squares. So, for each tour from the starting square in Figure 2, we also have corresponding tours for seven additional starting squares. See Figure 6.


Figure 6.


Thus each tour found gives us eight tours, except for starting squares on the major diagonals. For those squares the mirrors and rotations are the same., so each solution gives only four. The result is that if we find all the tours for the right ten starting squares, we can calculate the tours for the rest of the board by mirroring and rotating. Figure 7 shows one possible set of starting squares that will yield all tours for the entire board.


Figure 7.

If we mirror the tours from the starting squares in Figure 7 on the vertical axis, we have the tours whose starting squares are shown in Figure 8.


Figure 8

Mirroring Figure 8 on the horizontal axis gives us Figure 9, and rotating Figure 9 clockwise or counter-clockwise gives Figure 10, covering the entire board.


Figure 9


Figure 10

LET ME COUNT THE WAYS
To find the total number tours on an 8-by-8 board, we first find the totals for each of the necessary set of ten starting squares. Then we multiply the totals for the four squares on major diagonals by four, multiply the totals for the remaining six squares by eight. Finally we add the ten subtotals together.

Simple enough, right? It depends on how many years and computers you have. With Wirth's recursive algorithm a power outage or equipment failure is disastrous - you have to start over again on the current starting square. Replacing recursion with iteration in the form of two nested repeat..until loops and a bit of code jiggering lets us periodically save the current state, then load and continue from the most recently saved state.

THE CODE OF ROTATION
Rotating and mirroring tours is simple. Assume we've defined the data type ggtBoard as a two-dimensional integer array with 8 elements in each dimension. In Pascal -

type ggtBoard = array[1..8, 1..8] of Sint16;


Each array element holds the move number for that position in the 8-by-8 matrix.

RotateIt
 

Procedure RotateIt (var tourBd : ggtBoard);

Var
    row, row2, col, col2 : SInt16;
    tourBd2 : ggtBoard;

begin
for row := 1 to 8 do
    for col := 1 to 8 do
        tourBd2[col, 9-row] := tourBd[row, col];
tourBd := tourBd2;
end;

MirrorItV
 

Procedure MirrorItV (var tourBd : ggtBoard);

Var
    row, col : SInt16;
    trBd2 : ggtBoard;

begin
for row := 1 to 8 do
    for col := 1 to 8 do
        trBd2[row,9-col]:=trBd[row,col];
tourBd := tourBd2;
end;



MirrorItH
 

Procedure MirrorItH (var tourBd : ggtBoard);

Var
    row, col : SInt16;
    tourBd2 : ggtBoard;

begin
for row := 1 to 8 do
    for col := 1 to 8 do
        tourBd2[9 - row, col] := tourBd[row, col];
tourBd := tourBd2;
end;


A QUESTION OF TIME
Even if we search out all tours for only ten starting squares and calculate the rest, we're talking about a very long time. Equipment malfunctions, power gets cut off and other assorted misfortunes can interrupt the search. In my 1998 implementation, the Try procedure, following Wirth [1986] was recursive.


Try
 

Procedure Try(index,x,y:integer;var q:boolean);

Var
    k,column,row,dX,dY : integer;
    q1:boolean;

begin
// code snipped
repeat
    // code snipped
    Inc(k);
    dX:=gDeltaX[k];
    dY:=gDeltaY[k];
    column:=x+dX;
    row:=y+dY;
    if SquareNotOccupied(row,column) then
        begin
        MakeTheMove(row,column,index); 
        // snip

        if not CompleteTour(index) then
            begin
            //
            Try(index+1,column,row,q1);

            // backtracking here
            if (not q1) then
                begin
                //remove knight from array;
                // board will clear next update
                ggChessBd[row,column]:=0;
                // snip
                end;
            end
        else
            begin
            // complete tour, so find
            // the next one
            ggChessBd[row,column]:=0; 
            end;
        end;
until timeToExit;
q:=q1;
end;


There's no practical way to save the current state of the search, then reload it and resume execution at a later time. The approach shown in Listing 5 replaces recursion with a pair of nested repeat loops. Together with changes elsewhere in the program code, it permits saving and restoring the program state


Try
 

Procedure Try (x, y : SInt32; var q : bool);
Type
    tkRay = array [0..8] of SInt32;

Const
    kRay : tkRay = (1, 2, 3, 4, 5, 6, 7, 8, 0);

Var
    k : SInt32;
    dX, dY, col, row : SInt32;

begin
// snip
repeat
    // snip
    repeat
        // snip
        dX := gDeltaX [k];
        dY := gDeltaY [k];
        col := x + dX;
        row := y + dY;
        if SquareNotOccupied (row, col) then
            begin
            DoMoveData (row, col);
            if not CompleteTour() then
                begin
                // if we're not at square 64 
                // save col, row, k for
                // current square, increment 
                // square # and exit inner
                // loop
                end
            else
                begin
                // we're at square 64
                // so back up & find next tour
                // snip 
                end;
            end;
        // test exit conditions
    until exitConditionsMet;
    // backtrack if we need to
until we're back at square one;
end;


DIVIDING THE CHORES FURTHER
We are now part of the way to where we want to go. Expecting a single computer to find all solutions for a starting square is impractical at best. For one thing, starting from the square at row 1, column 1, there are only two possible moves ¬ to row 2, column 3 and to row 3, column 2. Starting from row 4, column 4 there are 8 possible moves.

The coding that allows a previously saved program state to be loaded and execution continued from that point also permits the "k" values for each level to be pre-set and for program termination to be set for when a specified backtrack level and "k" value have been reached. Thus the work for each starting square can be divided among many computers.
I've got everything working at the "proof of concept" stage, with much of the code still in un-carbonated classic form.

Two screenshots of a current tour GUI display program follow.


Knight's Tour Screenshot 1


Knight's Tour Screenshot 2

TERMINAL VELOCITY
The GUI ap shown above is good for demonstrating Wirth’s exhausttive4 search algorithm, but event and graphics overhead make it suboptimal for simply counting tours. Using a terminal ap and a 12 x 12 board array gives at least a 10x speed-up.

The above screenshots show a 12 x 12 matrix of squares with the 8 x 8 chessboard in the middle. The grey outer squares allow easy display of “off board” moves tested by Wirth’s algorithm. It also suggests a way of eliminating the separate “off board” test by using a 12 x 12 array and initializing rows and columns 1. .2 and 11..12 to non-zero values so they always fail the “is this square occupied” test, which looks for a zero value in a given array position.

First we define a few things this way - 

type
	ggtBoard_12	 =  array[1..12, 1..12] of SInt16;
const
	ggkSquareNotOccuped = 0;
	ggkOffTheBoard = $FFFF;
var
	ggTourBd : ggtBoard_12;

Now we can initialize the board this way 


procedure InitTheBoard ( );

var
	r, c : SInt16;

	begin
	for r := 1 to 12 do
		for c := 1 to 12 do
			begin
			if (r in [3..10]) and (c in [3..10]) then
				begin
				ggTourBd[r, c] := ggkSqUnOccuped;
				end
			else
				begin
				ggTourBd[r, c] := ggkOffTheBoard; 
				end;
			end;
	end;


And use a single zero test to determine the legality of the move 

if (ggTourBd[row, col] <> 0) then
	begin
		cycle;
	end;


If we’re simply counting tours, we don’t need a GUI with its screen update and event overhead, so a simple terminal ap can be used, with termination when a specified condition is met. Figure 13 is a screenshot of a terminal ap that quits when 64k tours have been found.


Figure 13

Amidst the file-handling messages, we see that this run took 58 minutes 52 seconds. The “Start tour #” of 0 and the “Loaded Time” of 000-00:00:00 indicate that the run is a fresh one.

Figure 14 is a screenshot of the same terminal ap . The “Start tour #” of 16384 indicates that the run is a continuation of a previous run and the “Loaded Time” of 000-00:13:46 is the run time for the 16k tours.


Figure 14

Final versions of the prog will terminate at a backtrack and “k” level read from the startup file. The prog saves completed tours at intervals and also saves its current state approximately every hour [to reduce overhead, the time since last hourly save is checked only every 2^24 position tests].

The ability to save and start from files of status records is the key to the project, since it allows me to distribute startup files for people to run, much the way the “at home” projects [SETI, protein folding, &c] distribute work.

IF IT’S TUESDAY, IT MUST BE TIME TO BEG
I am a tad short of resources for this project, so any monetary contributions are most welcome. If a whole bunch of folks each send me a dollar or three, I could devote more time to this and less to hustling for contract work that pays the rent. E-mail contact fkuechmann AT earthlink.net for snailmail address for sending loot.


References

Kuechmann, F.C., The Knight's Tour, MacTech , Vol. 14, number 11; November 1998.

Martin Loebbing and Ingo Wegener, The Number of Knight's Tours Equals 33,439,123,484,294 --- Counting with Binary Decision Diagrams in the EJC, Vol. 3, (no 1).
http://www.combinatorics.org/Volume_3/Abstracts/v3i1r5.html

Comments on: Martin Loebbing and Ingo Wegener, The Number of Knight's Tours Equals 33,439,123,484,294 --- Counting with Binary Decision Diagrams.
http://www.combinatorics.org/Volume_3/Comments/...

B. D. McKay, Knight's tours of an 8x8 chessboard, Tech. Rpt. TR-CS-97-03, Dept. Computer Science, Austral. Nat. Univ. (1997).
http://cs.anu.edu.au/~bdm/papers/knights.ps.gz






Copyright © 2006, F.C. Kuechmann