Friday, September 23, 2011
punctured knight's tours
It's pretty clear that a chess knight cannot travel to every square on a 3x3 board. If the knight starts in the center square, it cannot move at all, while if it starts on any other square, it cannot reach the center. If you puncture the board by removing the central square, your dissapointment with the simplicity of the remaining problem might be somewhat relieved by the niceness of the solution: there is only one possible knight tour on a punctured 3 by 3 board (up to rotation, reflection, and change of direction), and it is closed with a nice star-shaped path.
This nice pattern inspired me to look at knight tours on other punctured square boards - boards with odd dimensions that had the central square removed. On boards that are 5 by 5 I could only find two distinct solutions (other non-distinct tours can be found by rotation, reflection, and reversing direction), but it is likely that there are more. Neither of the ones that I found are closed - the first follows a spiral path and always travelling in the same direction (like the 3 by 3 case), while the second starts out as a spiral in one direction and then changes direction after the ninth move.
However, I found that a nice closed tour can be created on a 7 by 7 punctured board by "gluing" together rotated copies of an open 3 by 4 tour. The technique of building up knight tours from smaller ones by gluing them together in a way that the knight can move from one to the next is a common one, and is particularly helpful when you want to create symmetric or semi-magic tours (this is described in Martin Gardner's essay "Knights of the Square Table" from Mathematical Magic Show).
Although this technique does not give you a spiral pattern like the 3 by 3 case or the first 5 by 5 example, the copy and rotate technique gives the path another nice pattern. You can see this symmetry in the 7 by 7 punctured board if you look at the cell values modulo 12 (doing this tracks where the values in the original board are rotated to).
If you connect the values that are equal to each other mod 12, you get a nice pattern of rotated nested squares - this pattern is completely independent of the tour on the initial 4 by 3 board: all it shows is the rotation that was applied to make the larger board. The image below has done this for some values (not all) - for example 5, 17, 29, and 41 form a square, as do 8, 20, 32, and 44.
This pattern is reminiscent of a more ideal version of the same pattern, which can be made using iterations in Geometer's Sketchpad (the gsp file used to create this is here). It seems that one way or another, we end up finding spirals.
You can use the same "rotate and glue" process to create a closed 9 by 9 punctured tour, made up of copies of a specially constructed open 4 by 5 tour. There are several open 4 by 5 tours that can be glued together to make a closed 9 by 9 punctured tour - here's one below:
kixote, or knight tour puzzles