December 2001
<<November December January>>
Part 1: None.
Each closed knight's tour must alternate white and black.
It must also alternate between outer rows (row 1&4) and inner rows (row 2&3), because each square on the outer row must be surrounded by squares on the inner row, and a counting argument shows they must then strictly alternate.
Then squares visited on even-numbered turns are white squares on outer rows, and those visited on odd-numbered turns are black squares on inner rows. You never hit the other squares.
Part 2: All positive integers N except N=1, 2, 4.
You can easily convince yourself that N=1 or 2 won't work.
N=4 won't work: by an argument similar to that for the closed knight's tour, when we go from the eighth square to the ninth square we must change color; we must go from the second to the third row vertically (or vice versa); and we must go from the second column to the third column (or vice versa).
For N=3 the following example suffices:
| 1 | 8 | 3 | ||
| 4 | 11 | 6 | ||
| 7 | 2 | 9 | ||
| 10 | 5 | 12 |
For N=5:
| 14 | 5 | 18 | 1 | 12 | ||||
| 19 | 10 | 13 | 6 | 17 | ||||
| 4 | 15 | 8 | 11 | 2 | ||||
| 9 | 20 | 3 | 16 | 7 |
How to add three columns:
If you have an open knight's path for N, create from it an open knight's path for N+3. Assume that in the existing path on the 4xN board there is a link between the upper left corner (marked k) and the square (k') in the third row down, second column from left. Replace that link with a path as pictured below, visiting in order
k, k+1, k+2, k+3, k+4, k+5, k+6, k'.
Similarly, replace the link (m,m') with the path visiting
m, m+1, m+2, m+3, m+4, m+5, m+6, m'.
| m+2 | k+4 | m+6 | k | ? | ? | ? | ? | |||||||
| m+5 | k+1 | m+3 | ? | m' | ? | ? | ? | |||||||
| k+5 | m+1 | k+3 | ? | k' | ? | ? | ? | |||||||
| k+2 | m+4 | k+6 | m | ? | ? | ? | ? |
If k' preceded k, we need to traverse the added path backwards.
We assumed there was a link between k and k'; this will be the case if we start with the N=3 or N=5 construction pictured above, or if we applied the "how to add three columns" to a 4x(N-3) construction.
How to add four columns:
To go from N columns to N+4, we mimic the previous construction, using the following pattern:
| k+6 | m+2 | k+4 | m+8 | k | ? | |||||
| k+3 | m+5 | k+7 | m+1 | ? | m' | |||||
| m+3 | k+5 | m+7 | k+1 | ? | k' | |||||
| m+6 | k+2 | m+4 | k+8 | m | ? |
Finally, starting from N=3 or N=5 and successively adding 3 or 4 columns at a time, we can reach any positive integer N except for 1, 2 or 4.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com