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