|
|
'Greek-key' tours on 3xn chessboards
Posted:
Apr 21, 1999 7:16 AM
|
|
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
|
|
