### Problem Description

The Knight's Tour is a classic chess problem which was
studied (and probably solved) over 1000 years ago. The famous
mathematician, Euler, published the first rigid mathematical analysis of the problem
in 1759.

Here's the problem: ** From an arbitrary starting
position, move a Knight chess piece around a chess board visiting all other squares on the board exactly
once. **

### Background & Techniques

This program is a logical extension of the search techniques previously
developed in **Graph Traverse**. We will be performing a depth
first search by recursively calling a **SolveFrom** function. After
each successful move, we'll call **SolveFrom** with the new location.
After we have moved 64 times (counting the initial knight placement as move
number 1), we have solved the problem.

A successful move is a move to a square not previously visited. Unlike ** Graph
Traverse**,
an exhaustive search will not be necessary in this case, we need
to find only one path that visits all squares to solve the
problem. The complication is that the number of possible paths is
vastly larger than in ** Graph Traverse**. For each move, there are between 0
and 8 choices for the next move, and most of the time this number will be closer
to 8 than 0. If we assume only 2 possible moves for each position,
there would be 2^{63} (or about 10^{20}) paths, about the same number
required to solve the Towers of Hanoi
puzzle. Searching a million paths per second would still
require a few million years to find a solution!

Fortunately, help is at hand. A technique known as ** Warnsdorf's
heuristic** allows us to make much better choices for next move than random
selection. The heuristic, discovered by H. C. von Warnsdorf in 1823
tells us to select as our next move the one which has the fewest choices for
moving on from there. This heuristic works so well that , although I have
implemented backtracking to remove bad choices, I have yet to see a move
retracted while making a tour.

**SolveFrom** works by counting how many next moves would be available for
each valid potential move from the current location. This list of
potential moves is sorted by the "next move count" and the smallest one
selected. A move is made and a recursive call to ** SolveFrom** is made with
this new location. If the call returns true, we leave the move in place
and exit with a result of true. If the function fails, the move is
retracted and the next potential move is tried. If there are no more to
try, we exit with the result set to false.

A ** TBoard** object is derived from** TStringGrid** to handle both the computational
and the display aspects of the problem. The solutions are animated as in Graph
Traverse, and an **OnDrawCell** exit handles grid display. **TBoard** also contains computational
routines such as **IsValidMove, MakeMove, UndoMove, SolveFrom,**
etc.

A trackbar component was added to the form allow the user to adjust the speed
of the solution display. A manual move mode was also implemented to allow
the user to try to solve the problem himself. Both of these features are
straight forward.

As always, if there's something that's still confusing after studying
the code, or if you find a bug, let me know.

**Addendum December 20, 2000:** I just reviewed the program for the
first time since posting it 2 years ago. A viewer had suggested the
ability to auto-solve from a specified position (the original version
started from a random board position). New edit boxes now specify the
starting
row and column. The same viewer also re-introduced me to the concept of
a "Closed Tour" where the starting knight position is a
valid destination for the final position. (Thanks Arne!) I
added this as an option with the result that a little more backtracking is
required to complete then tour. Starting at the 5th row in column 1
requires 981 trial moves to find the 63 moves that complete the closed
tour, the most I've seen in my tests so far.

And, as usual when doing a review, I found and fixed a
couple of minor bugs:

**Bug fix: **The first press of the "Let me try"
button while solving manually was ignored.
**Bug fix:** There was no way to interrupt auto-solve until it
finished.

**Addendum June 12, 2003: **A modification was posted today
which allows users to specify an ending square as well as a beginning square for
program solution searches. Since knight moves will land on squares
with alternating colors, the 63rdmove, the final one, must land on a square that
does not match the starting square in color. The algorithm
implemented here uses backtracking to try all paths until one with the desired
end point is found. In most cases this procedure will find a solution in a
few hundred trial moves. However, a test case starting at (1,1) and
ending at (8,1) was cancelled after 10,000,000 trial moves, so there is
obviously room for a smarter method!

**Addendum June 13, 2003: **It didn't take long for alert reader
Charles Doumar to come up with the improvement posted today. In the **IsValidMove**
function testing, he added a check that says, "If this is not the last move
and there is no move from here, then this is not a valid move". The
result is to stop all path searching one level earlier than without this
test, and that's enough to solve the case mentioned above in 794
trial moves!

**Addendum July 18, 2003: ** Viewer Kurt White sent me a very fast
exhaustive depth-first search version of the tour and questioned whether
Warnsdorf was really necessary. I converted it to Delphi and, sure enough,
starting at the top left corner square the program finds 141 solutions in the
first minute after checking 660 million board positions.
Unfortunately, it appears to be a fluke and I've yet to find a solution staring
at any interior square. So I guess Warnsdorf wins
again! Here's a link to download
the source for Knights_BF if you want to check it out. I
have included the original C code as comments at the bottom of the
listing. The conversion process was an interesting exercise in any
event.

**Addendum August 27, 2004: ** Another version of the program based
on a user request. The version posted today allows users to add arbitrary constraints
specifying one or more (move number, column, row) constraints for any
auto-solve solution found. Constraint data may be saved and
reloaded from a file. Some checking for consistency is performed
as constraints are defined, but it is still possible to define a set
of constraints that cannot be solved. The original problem was
from a challenge posted at another puzzle site. User Ian was working on the
problem and wondered if I could help. So did I, and when we finally
got it working, I decided to generalize the code and post it here. The
included file contains the 10 or so constraints that defined the original challenge and finds a solution after several hours of CPU
time.

**Addendum December 11:2004: **A user asked for the option to
continue searching after the first solution is found. Added it today.

**Addendum May14, 2007: **Board sizes may now be changed by the user
with sizes selected from 4x4 to 12x12 cells. (5x5 seems to be the smallest
solvable square board). The physical display area of the board is
also now changed as the form is resized.

**Addendum September 14, 2007:** A new program was added today **
AllKnightsTours** answers a question posed by a viewer a few weeks ago.
"Does at least one tour exist from every square on an 8x8 chessboard to every
other valid ending square?" Since there are an odd number of squares
to be touched (63) and Knights alternate between light and dark squares on each
move, only the 32 squares of the color not the same as the starting square need
to be checked as ending squares. There are a number of cases that
the Warnsdorf algorithm does not seem to solve, probably when ties for
next move choice exist and the wrong choice happens to be made. If this
happens early in the tour, it could take days or years to backup far enough to
correct ther error. I could have a made a special case for the these
"tie score" cases and traversed those rather than backtracking when a solution
was not not found right away, but the idea just occurred to me. What I did
do was to take advantage of the fact that a tour can be traveled in either
direction, so if we can find a reverse tour from the ending square to the start
square, we have the one running in the other direction. The same idea
applies to rotating the board. If we rotate the board 1/4 turn, rename the
start and end points for their new locations, and can find a tour using these
new points, we can mathematically rotate that tour back to have one that meet
the original objective. Those two techniques were good enough
to solve the problem. All of that took a couple of weeks of spare time
programming but the answer is - yes there is at least one tour from
each square to each of its 32 possible ending squares.

**Addendum February 22, 2007: ** At a viewer's request, **Version 4
**of Knights tour was posted today which allows non-square boards. The
Warnsdorf heuristic does not seem to be as effective with the rectangular
boards I've tried (7x4 solved only after 110,000 moves tried,
for example; no solution found for 10x4). I haven't worked on improving
the algorithm.

### Running/Exploring the Program