
'Greekkey' tours on 3xn chessboards
Posted:
Apr 21, 1999 7:16 AM


Let a Greek key tour be a path visiting all squares of an orthogonallyconnected 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_{n1} + 3/2 * 2^n
and E_n satisfies
E_1 = 17, E_n = 4E_{n1} + 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

