5 August 2004
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% ./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
^C
cdurso% ./knight --help
knights [OPTIONS] [SEARCHPATH]
knights crossing program (v1.0, 03Aug04), by chris durso, ref.
www.durso.org
OPTIONS
-v
--verbose print more information
-g=#
--grid=# use grid of size #
(default 8 for 8x8). Minumum 3, 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.
cdurso% ./knight 27
27 41 42 17 33 50 18 32 44 38 53 21 37 47 20 34 42 19 46 45 22 45 44 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 74344598 many mis steps
27 41 42 17 33 50 18 32 44 38 53 21 37 47 20 34 42 19 46 45 22 45 44 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 75316971 many mis steps
27 41 42 17 33 50 18 32 44 38 53 21 37 47 20 34 42 19 46 45 22 45 44 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 75321545 many mis steps
27 41 42 17 33 50 18 32 44 38 53 21 37 47 20 34 42 19 46 45 22 45 44 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 82534827 many mis steps
27 41 42 17 33 50 18 32 44 38 53 21 37 47 20 34 42 19 46 45 22 45 44 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 89229211 many mis steps
^C
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
