5 August 2004, 15 February 2012
back_home


Knights Tour Program


background:

The knights tour is a path starting at an arbitrary position on an arbitrarily sized square grid, such that every square is visited exactly once in a sequence of legal chess moves.  ( In chess, the knight is permitted to move up to eight different positions, its move consisting of shifting +/-2 squares in one axis and +/-1 square in the other.)   The tour may be re-entrant, meaning that the last square to be occupied is one move away from the first, forming a convoluted loop.  If the last square is not one move away form the first the tour is said to be open.  There are a number of different methods find knights tours, and claims on the internet to have determined the total number of re-entrant knights tours for as large as a standard 8x8 board.  Some of these claims are clearly wrong for obvious reasons, and I am unsure if others are correct or not.  See the references below for a more comprehensive background.

interest:

My original interest was to determine all the possible tours of the open tour, but a simple combinatorics calculation and a bit of experimentation indicates that this goal is not likely to be small enough to practically obtain.  In multiplying all the legal moves together (discounting those that take you off the edge) and then multiplying that result by 64 (representing the arbitrary starting position) you will see the upward boundary of the problem is ~5E45 in size.  With just a little bit of experimenting (of approximately 24 cpu hours) I searched 6E12 of these paths to record 1.4E6 knights tours on a pentium laptop.  If this result is anything representative (and there are no guarantees that it is) then one might expect approximately 1E39 of knight tours.

approach:

The program I have created uses a simple and optimized backtracking algorithm that searches approximately 6 million attempts per cpu second.  The search path's path (or the path of all paths) is very simple but complete.  It however can go down a blind alleys where it would take a practically long time to extract itself as it explores the possibly large number of permutations of the blind alley.  The program currently accepts a starting position or path to continue from, so I may need to generate a higher level program to representatively sample the space of all possible paths.  If I do this then I would be able to statistically determine the number of knight tours with a very small fraction of actual searching, something that I could easily perform with distributed computing.  This statistical approach may actually require the blind alley's to be integrated into the mix, unless I somehow also integrate how many failed paths follow any given blind alley.

One possible blind ally avoidance would be to periodically (say once every million failed paths) back-trace tours for that have unreachable pockets.  This may make it possible to bolt forward quite a bit, depending on what a typical dead end looks like.  This technique adds an element of another approach involving weighing candidate moves favoring least accessible squares. 

I have choosen backtracking as a primary technique as I am not sure how many true tours are skipped by the weighted candidate approach.   I would not expect an occasional search for pockets to significantly slow the algorithm back-trace algorithm.

program:

The program was coded in the C++ language, and compiled with the gcc compiler.  It uses only the stdio library so it should be easy to recompiled on any platform. 

It is pretty efficient for a backtracking only effort with precomputation of a move table and a table offset stack to record current position and previous paths searched.  The only further optimization that I have made was the elimination of a division operation for resolving the current position in the inner loop of approximately 70 lines of code.  As I mentioned before this algorithm will search on the order of 6 million jumps per second on a gigahertz pentium laptop. 


knights_tour_animated_600k
results:


cdurso% wget http://www.durso.org/knights_tour/knight.cpp
cdurso% g++ -O3 -o knight knight.cpp
cdurso% ./knight

0 10 4 14 20 3 9 19 2 8 18 1 11 5 15 21 6 12 22 7 13 23 29 35 25 40 34 17 27 33 16 26 32 49 43 28 38 55 61 44 59 53 63 46 31 37 47 30 36 51 57 42 48 58 52 62 45 39 54 60 50 56 41 24
path 1 found after 67679582 many mis steps


cdurso% ./knight --help
knights crossing program (v1.1, 12Feb12), by chris durso, ref. www.durso.org
OPTIONS
-v --verbose print more information -g=# --grid=#use grid of size # (default 8 for 8x8). Minimum 5, Maximum 11.
Note no white spaces!

SEARCHPATH

The optional SEARCHPATH is a sequence of positive numbers not longer than grid x grid in length, and thier numerical values in the range of 0 to grid x grid and non repeating. Each number is sequence must be a legal chess knights move from the previous number in the SEARCHPATH.
COORDINATE SYSTEM

The bottom left hand corner is noted as 0 and the increment first goes up and wraps to the right. The bottom left is 0, the top left is grid -1, and the top right square is grid x grid -1.

7 15 23 31 39 47 55 63
6 14 22 30 38 46 54 62
5 13 21 29 37 45 53 61
4 12 20 28 36 44 52 60
3 11 19 27 35 43 51 59
2 10 18 26 34 42 50 58
1 9 17 25 33 41 49 57
0 8 16 24 32 40 48 56

chdurso$ ./knight 27 | head -n 50
initial stack: 27 10

27 10 0 17 2 8 18 1 11 5 15 21 4 14 20 3 9 19 13 7 22 12 6 23 29 35 25 40 34 24 41 26 16 33 48 58 43 28 38 53 63 46 31 37 52 62 47 30 36 51 57 42 32 49 59 44 61 55 45 39 54 60 50 56

path 1 found after 41847204 many dead ends

27 10 0 17 2 8 18 1 11 5 15 21 4 14 20 3 9 19 13 7 22 12 6 23 29 35 25 40 34 24 41 26 16 33 48 58 43 28 38 55 61 44 59 49 32 42 57 51 36 30 47 53 63 46 31 37 52 62 45 39 54 60 50 56

path 2 found after 42394878 many dead ends

27 10 0 17 2 8 18 1 11 5 15 21 4 14 20 3 9 19 13 7 22 12 6 23 29 35 25 40 34 24 41 26 16 33 48 58 43 28 38 55 61 44 59 49 32 42 57 51 36 53 63 46 31 37 52 62 47 30 45 39 54 60 50 56

path 3 found after 42397394 many dead ends

27 10 0 17 2 8 18 1 11 5 15 21 4 14 20 3 9 19 13 7 22 12 6 23 29 35 25 40 34 24 41 26 16 33 48 58 43 49 32 42 57 51 36 30 47 62 52 37 31 46 63 53 59 44 61 55 38 28 45 39 54 60 50 56

path 4 found after 46446352 many dead ends

27 10 0 17 2 8 18 1 11 5 15 21 4 14 20 3 9 19 13 7 22 12 6 23 29 35 25 40 34 24 41 26 16 33 48 58 43 53 63 46 31 37 52 62 47 30 36 51 57 42 32 49 59 44 61 55 38 28 45 39 54 60 50 56

path 5 found after 50411400 many dead ends

27 10 0 17 2 8 18 1 11 5 15 21 4 14 20 3 9 19 13 7 22 12 6 23 29 35 25 40 34 24 41 26 16 33 48 58 52 37 31 46 63 53 36 30 47 62 45 39 54 44 59 49 32 42 57 51 61 55 38 28 43 60 50 56

path 6 found after 54121086 many dead ends
cdurso% time ./knight --grid=9

0 11 58 15 8 25 6 13 2 9 20 1 12 59 16 23 30 19 36 29 10 57 14 61 24 17 34 41 22 33 26 43 32 21 28 39 46 27 38 31 42 35 52 59 40 47 54 73 66 49 68 79 62 51 44 61 80 69 50 57 76 65 72 55 74 63 56 45 64 75 58 77 70 53 60 71 78 67 48 37 18
path 1 found after 499139831 many mis steps

0 11 58 15 8 25 6 13 2 9 20 1 12 59 16 23 30 19 36 29 10 57 14 61 24 17 34 41 22 33 26 43 32 21 28 39 46 27 38 31 42 35 52 59 40 47 54 73 66 49 68 79 62 51 44 61 80 69 50 67 78 71 60 53 70 77 58 75 64 45 56 63 74 57 76 65 72 55 48 37 18
path 2 found after 499155890 many mis steps

0 11 58 15 8 25 6 13 2 9 20 1 12 59 16 23 30 19 36 29 10 57 14 61 24 17 34 41 22 33 26 43 32 21 28 39 46 27 38 31 42 35 52 59 40 47 54 73 66 49 68 79 62 51 44 61 80 69 76 57 50 67 78 71 60 53 70 77 58 75 64 45 56 63 74 55 72 65 48 37 18
path 3 found after 499195006 many mis steps
^C  78.990 [seconds]u 0.350s 1:21.22 97.6%  0+0k 0+0io 0pf+0w

cdurso% time ./knight 17
^C 302.330
[seconds] u 1.260s 5:50.85 86.5% 0+0k 0+0io 0pf+0w

No success starting at square 17.  This last example (if I recall correctly) was run over night still not finding the first successful path.  If I coded it to backtrace on discovered unreachable pockets would likely remedy the problem.

reference sites: wolfram, tomasson
back home