Warnsdorff's Rule

Warnsdorff's Rule is a heuristic for finding knight's tours on chessboards. Some research I did in the 1990s at a Research Experience for Undergraduates programme under Paul Cull suggests very strongly that Warnsdorff's rule, with suitable modifications, can give a knight's tour on any square board.

This site is not an introduction to Warnsdorff's Rule (see the Wikipedia article and research paper linked above for this). Instead it provides:

• A Python program (hosted at github) that produces Warnsdorff's Rule tours for square boards of arbitrary size and can convert these to various visual representations;
• A set of output files from this program, representing Warnsdorff's Rule tours of square boards of size 5 to 1000 (the product of several days' computation on a reasonably fast computer); and
• Several Flash movies showing Warnsdorff's Rule tours being executed on boards of various sizes (one is playing above, if your browser supports Flash). These movies were produced by the Python program described above. In these movies a square is coloured when the knight visits it: blue if the knight does not need to invoke a tiebreak rule, red if a tiebreak is needed (see the research paper for more details).

I hope that readers are inspired to learn more about Warnsdorff's Rule, and perhaps to prove that the modified rule will actually produce tours on all square boards (this is known for boards whose size is equivalent to 7 mod 8, thanks to Sam Ganzfried's REU paper on the subject).