Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: 'Greek-key' tours on 3xn chessboards
Replies: 9   Last Post: Apr 23, 1999 4:48 AM

 Messages: [ Previous | Next ]
 Thomas Womack Posts: 161 Registered: 12/6/04
'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

Date Subject Author
4/21/99 Thomas Womack
4/21/99 QSCGZ
4/22/99 Thomas Womack
4/22/99 QSCGZ
4/22/99 Thomas Womack
4/23/99 QSCGZ
4/21/99 Antreas P. Hatzipolakis
4/21/99 Phillip
4/21/99 Robin Chapman
4/22/99 Thomas Womack