The Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Thomas Womack

Posts: 161
Registered: 12/6/04
'Greek-key' tours on 3xn chessboards
Posted: Apr 21, 1999 7:16 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply



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







Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2017. All Rights Reserved.