[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

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⁶³ (or about 10²⁰) 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:  

1. Bug fix: The first press of the "Let me try" button  while solving manually was ignored.   
2. 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 

Suggestions for Further Explorations

  [Feedback]   [Newsletters (subscribe/view)] [About me]

Copyright © 2000-2018, Gary Darby    All rights reserved.