'Greek-key' tours on 3xn chessboards
Thomas Womack
orthogonally-connected chessboard; for example,
1 2 3
4 5 6
7 8 9
1 2 4 5 7 8 9 6 3
is a tour.
It's fairly easy to enumerate these, by a straightforward backtracking
search or by a cleverer method if required, and I've counted them on
chessboards of various sizes. For the 3xn boards, I get (for n=1 .. 12)
1 3 8 17 38 78 164 332 680 1368 2768 5552 11168 22368
Splitting into sequences for even and odd n, and removing one or two of
the start terms to get recurrence relations to fit, we get series
O_n = 8 38 164 680 2768 11168
and
E_n = 3 17 78 332 1368 5552 22368
O_n seems to satisfy the recurrence relation
O_1 = 8, O_n = 4O_{n-1} + 3/2 * 2^n
and E_n satisfies
E_1 = 17, E_n = 4E_{n-1} + 5/2 * 2^n
What I'd like to know is, how can I find an explicit solution to the
recurrence relations. I suspect the recurrence relations can be derived
by inspiration about the problem, but I'm not quite sure how to solve
them once they're derived. Since I'm lacking inspiration about the
problem, I'd like to see what the solution looks like to see if that
helps any.
For 4xn boards, the series is 1 4 17 52 160 469 1337 3750 10347 28249
76382 204996; this fits a curve of the form 3^n quite well, but there's
no such obvious recurrence relation to spot.
For larger boards, the computations get painful; 7x7 has been running
all night on this P2/350 and might well need some more nights yet.
Tom
QSCGZ
>Let a Greek key tour be a path visiting all squares of an
>orthogonally-connected chessboard; for example,
>
>1 2 3
>4 5 6
>7 8 9
>
>1 2 4 5 7 8 9 6 3 is a tour.
^^^
you mean 1 2 5 4 7 8 9 6 3 ?! In fairy-chess-notation this is a
"prince" or a (1,0)-leaper as someone else recently wrote in rec.puzzles.
These tours are also called "self-avoiding walks" .
And from your numbers below I conclude, that you only allow tours that
start in the upper left corner.
>3xn : 1 3 8 17 38 78 164 332 680 1368 2768 5552 11168 22368
> O_n = 8 38 164 680 2768 11168
> O_1 = 8, O_n = 4O_{n-1} + 3/2 * 2^n
> E_n = 3 17 78 332 1368 5552 22368
> E_1 = 17, E_n = 4E_{n-1} + 5/2 * 2^n
>4xn : 1 4 17 52 160 469 1337 3750 10347 28249 76382 204996
>7x7 has been running all night on this P2/350 and might well need
> some more nights yet.
I can spare you the waiting: it's 1510446 , which I got on this
P1/166 in 25 seconds.
(Note, that moves to a square with an occupied square ahead and free
squares on the left and right can be disregarded ! )
--qscgz
Antreas P. Hatzipolakis
<mert...@sable.ox.ac.uk> wrote:
> Let a Greek key tour be a path visiting all squares of an
> orthogonally-connected chessboard; for example,
Nice name !
What else from the "castle of the classicism" (as I had once named it
elsewhere) ? (I mean Oxford)
>
> 1 2 3
> 4 5 6
> 7 8 9
>
> 1 2 4 5 7 8 9 6 3
>
> is a tour.
>
> It's fairly easy to enumerate these, by a straightforward backtracking
> search or by a cleverer method if required, and I've counted them on
> chessboards of various sizes. For the 3xn boards, I get (for n=1 .. 12)
>
> 1 3 8 17 38 78 164 332 680 1368 2768 5552 11168 22368
Neither this nor the other one below were found in the Sloane's
_Encyclopedia_ at:
http://www.research.att.com/~njas/sequences/index.html
[...]
> For 4xn boards, the series is 1 4 17 52 160 469 1337 3750 10347 28249
> 76382 204996; this fits a curve of the form 3^n quite well, but there's
> no such obvious recurrence relation to spot.
>
> For larger boards, the computations get painful; 7x7 has been running
> all night on this P2/350 and might well need some more nights yet.
>
> Tom
I took the liberty to FWD the entire your posting to Neil Sloane
in case he would like to include your sequences in his great collection.
Good Luck !
Antreas
Phillip
Thomas Womack wrote:
>
> Let a Greek key tour be a path visiting all squares of an
> orthogonally-connected chessboard; for example,
>
> 1 2 3
> 4 5 6
> 7 8 9
>
> 1 2 4 5 7 8 9 6 3
>
> is a tour.
>
> It's fairly easy to enumerate these, by a straightforward backtracking
> search or by a cleverer method if required, and I've counted them on
> chessboards of various sizes. For the 3xn boards, I get (for n=1 .. 12)
>
> 1 3 8 17 38 78 164 332 680 1368 2768 5552 11168 22368
>
> Splitting into sequences for even and odd n, and removing one or two of
> the start terms to get recurrence relations to fit, we get series
>
> O_n = 8 38 164 680 2768 11168
>
> and
>
> E_n = 3 17 78 332 1368 5552 22368
>
> O_n seems to satisfy the recurrence relation
>
> O_1 = 8, O_n = 4O_{n-1} + 3/2 * 2^n
>
> and E_n satisfies
>
> E_1 = 17, E_n = 4E_{n-1} + 5/2 * 2^n
>
> What I'd like to know is, how can I find an explicit solution to the
> recurrence relations. I suspect the recurrence relations can be derived
> by inspiration about the problem, but I'm not quite sure how to solve
> them once they're derived. Since I'm lacking inspiration about the
> problem, I'd like to see what the solution looks like to see if that
> helps any.
>
> For 4xn boards, the series is 1 4 17 52 160 469 1337 3750 10347 28249
> 76382 204996; this fits a curve of the form 3^n quite well, but there's
> no such obvious recurrence relation to spot.
>
> For larger boards, the computations get painful; 7x7 has been running
> all night on this P2/350 and might well need some more nights yet.
>
> Tom
For the recurrence relation
a_(n+1) = b * a_n + c * d^n with a_1 = p,
(Note the difference in the notation)
We can write the general solution ( as per Mathematica ) as:
a_n = ( -b * c * d^n + b^n * d *(c-p) + b^(n+1) * p ) / ( b* (b-d) )
So for you first relation
a_1 = 8, a_(n+1) = 4 * a_{n} + 3 * 2^n
We have: ( b=4,c=3,d=2,p=8) (Note: c=3 and not 3/2)
a_n = 2^(n-2) * ( 11 * 2^n - 6 )
I hope this helps with the general solution to your problem once you
come up with the correct recurrence relation
Phillip
Robin Chapman
>
<snip>
> Splitting into sequences for even and odd n, and removing one or two of
> the start terms to get recurrence relations to fit, we get series
>
> O_n = 8 38 164 680 2768 11168
>
> and
>
> E_n = 3 17 78 332 1368 5552 22368
>
> O_n seems to satisfy the recurrence relation
>
> O_1 = 8, O_n = 4O_{n-1} + 3/2 * 2^n
>
> and E_n satisfies
>
> E_1 = 17, E_n = 4E_{n-1} + 5/2 * 2^n
>
> What I'd like to know is, how can I find an explicit solution to the
> recurrence relations. I suspect the recurrence relations can be derived
> by inspiration about the problem, but I'm not quite sure how to solve
> them once they're derived. Since I'm lacking inspiration about the
> problem, I'd like to see what the solution looks like to see if that
> helps any.
For the first, write O_n = 4^n A_n. Then
A_n - A_{n-1} = (3/2) 2^{-n}.
Thus A_n - A_1 = (3/2) (1/4 + 1/8 + ... + 1/2^n) = (3/2) (1/2 - 1/2^n)
etc.
--
Robin Chapman + "Going to the chemist in
Department of Mathematics, DICS - Australia can be more
Macquarie University + exciting than going to
NSW 2109, Australia - a nightclub in Wales."
rcha...@mpce.mq.edu.au + Howard Jacobson,
http://www.maths.ex.ac.uk/~rjc/rjc.html - In the Land of Oz
Thomas Womack
>I can spare you the waiting: it's 1510446, which I got
>on this P1/166 in 25 seconds.
So it is. That's a factor 6000 faster than my current program!
>(Note, that moves to a square with an occupied square
>ahead and free squares on the left and right can be
>disregarded ! )
I'm afraid I don't quite see what this note means ... presumably it's an
early-abort strategy for killing impossible paths quickly, but I can't
quite see which class of paths it's killing. Would it be possible to
give an example?
Tom
Thomas Womack
>For the first, write O_n = 4^n A_n. Then
>A_n - A_{n-1} = (3/2) 2^{-n}.
>Thus A_n - A_1 = (3/2) (1/4 + 1/8 + ... + 1/2^n) = (3/2) (1/2 - 1/2^n)
>etc.
Thanks very much; I'm an idiot for not noticing this myself!
Tom
QSCGZ
>>ahead and free squares on the left and right can be
>>disregarded ! )
>
>I'm afraid I don't quite see what this note means ...
yes, it's also a note. But "Note" was meant as imperativ.
>presumably it's an
>early-abort strategy for killing impossible paths quickly,
exactly.
>but I can't quite see which class of paths it's killing.
>Would it be possible to give an example?
______________
|1 2 3 |
| 4 |
| 5 |
| 6 |
|__r_7_l_____|
a
after move 7 , this can never be completed to a tour.
The square ahead (a) is occupied ( I define borders and already
visited squares as occupied) . The squares to the left (l) and right (r)
are free.
This gave a speed-improvement factor of ~100 ,AFAIR .
--qscgz
Thomas Womack
>yes, it's also a note. But "Note" was meant as imperativ.
>
> >presumably it's an
> >early-abort strategy for killing impossible paths quickly,
>
>exactly.
OK, I've implemented it as such (before doing the search for points that
can be added to the path and recursing, I check whether the path
violates your condition and backtrack otherwise) - but I don't get an
improvement as drastic as a factor 100 (I can manage a factor 13 in the
5x9 case). Your code seemed to be something like a factor 6000 faster
than mine, which I don't think is just because of the early-out.
For a vague benchmark, my improved program takes about 120 seconds to
find the 28249 10x4 tours, recursing 20329568 times; this is dire in
comparison to yours.
I can imagine a few implementation speedups - did you do something
clever with stacks? My version passes around lots of structures of the
form
Bitvector containing the visited cells
Number of entries on the tour
The tour
and has to copy the whole tour before each recursion (with concomitant
malloc() and free() calls); were you able to avoid this book-keeping
overhead by some cleverer tactic?
QSCGZ
>can be added to the path and recursing, I check whether the path
>violates your condition and backtrack otherwise) - but I don't get an
>improvement as drastic as a factor 100 (I can manage a factor 13 in the
>5x9 case).
Maybe I didn't remember the factor correctly.
With 5*8 , I now measured a factor of 41 , and 53 with 6*7 .
>Your code seemed to be something like a factor 6000 faster
>than mine, which I don't think is just because of the early-out.
>For a vague benchmark, my improved program takes about 120 seconds to
>find the 28249 10x4 tours, recursing 20329568 times; this is dire in
>comparison to yours.
Mine: ~0.2 sec. , 1078928 recursions . That's 33 CPU-cycles per recursion.
>I can imagine a few implementation speedups - did you do something
>clever with stacks?
My (assembler-)program calls itself recursively.
All needed info is stored on the stack in form of return addresses.
In fact, I used a knight's tours program and only changed the moves.
It makes a valid move, calls itself , removes the move ,
checks next possible move ... returns.
>My version passes around lots of structures of the
>form
>
>Bitvector containing the visited cells
>Number of entries on the tour
>The tour
>
>and has to copy the whole tour before each recursion (with concomitant
>malloc() and free() calls); were you able to avoid this book-keeping
>overhead by some cleverer tactic?
The clever tactic was , to keep it simple . ;-)
I'm just storing the content of the n*m squares in n*m bytes ,
and the border is marked as occupied.
I'm sending the code per email.
You might find some info on your problem by searching for
"self avoiding walks" .
--qscgz
end sci.math.posting