IBM Research | Ponder This | December 2001 solutions
Skip to main content

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: