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

**The
Knight's Tour Revisited
**

by F.C. Kuechmann

**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