George Duke wrote on Wed, Jul 22, 2009 06:54 PM UTC:
Falcon tours are known worldwide now thanks to the perspicacity of the
CVariantP, and Knight tours have been known for centuries. Bishop
partial-tours are uninteresting for obvious reasons. Moreover, the neglected fourth force, Rook tours are much appreciated once understood. Specifically closed
4 __ __ __ 4 tours, meaning return to originating square. Especially,
3 __ __ __ 3 closed tours that visit every cell along the
2 __ __ __ 2 way, each once, are the norm. Take 4x4. Rook tours include
1 __ __ __ 1 a1-a2-a3-a4-b4-b3-b2-c2-c3-c4-d4-d3-d2-d1-c1-b1-a1, having
a b c d no pass-over squares. That's sixteen steps, and they will
all have sixteen steps in 4x4, because there is no counting the pass-over
squares at all or the starting square twice. But lengths can vary, if say
starting a1-a4 rather than a1-a2. For example, on 2x3 size instead, you can stretch the Rook total distance to 8 by going a1-c1-c2-a2-b2-b1-a1, squares 6, length 8. You have to visit each square and end where started. Maximum length Rook tour on 2x3 is 8. (1) What is maximum length Rook tour on 4x4? (2) 4x5? (3) 5x5? (4) 5x6? (5) 6x6? (6) 6x7? (7) 7x7? (8) 7x8? (9) 8x8? (10) 8x9? 9x9? 9x10? 10x10? 10x11? 11x11? 11x12? 12x12? [One answer: on 11x12 closed Rook Tour maximum is 996 distance reaching all 132 squares.] Actually, there is a formula now for maximum length, but not an algorithm for how many such maximum-length tours there are altogether beyond the lower sizes. Is a maximum-length tour necessarily closed? All the above exclude reflections and rotations. (11) What does the formula n(n+1)(2n+2)/6 have to do with square chessboards? For 8x8 with n=8, the answer is 204. What is that signifying? #11 is not about Rook tours.