Puzzle 5: Solution

Q     If 32 Knights are placed on all the light squares of a standard 8-by-8 chess board, no two Knights observe each other. Likewise, of course, if we use all the dark squares instead. It has long been known that 32 is the maximum, and that those are the only configurations that attain it [Newman, Patenaude, and Greenberg: Problem E1585 and solutions, Amer. Math. Monthly 71, Feb.1964].
A) Instead of requiring each Knight to be unobserved, suppose we relax the condition by allowing each Knight to be either unobserved or observed by just one other Knight. How many Knights can the 8-by-8 board accommodate now?
B) What if we require that each Knight be observed by exactly one other Knight?

A    
A) Still 32 (though with more possible configurations).
B) Again 32 — this time again with a configuration unique up to board symmetries!

For (A), divide the board into four 4-by-4 squares. In each of these, divide the 16 squares into four knight circuits of length 4. At most two Knights can be put into each circuit if no Knight is to be observed by two or more others. Hence the 8-by-8 board can accommodate no more than 4·4·2=32 Knights.

Given part (A), clearly the answer to part (B) is at most 32. So, it is exactly 32, as long as there's at least one configuration of 32 Knights that works. Can you find this configuration? Can you prove its uniqueness?

(See my joint article “The Mathematical Knight” with Richard Stanley, in the Math. Intelligencer, Vol. 25 (2003), #1, pages 22-34.)