This Demonstration shows how to get from any white square on a chessboard to any black square by a sequence of knight moves that visits all squares. Such a route is called a Hamiltonian path, as opposed to a Hamiltonian cycle, which starts and finishes on the same square. Drag the two locators to change the start and finish squares.

Let denote the knight graph: knight moves on an board, where is always assumed. The graph is always bipartite. A bipartite graph having the property that one can get from any point in one part to any point in the other part using a Hamiltonian path is called Hamilton-laceable. This Demonstration shows that is Hamilton-laceable, thus extending the very old result that is Hamiltonian.

By a theorem of A. Schwenk [1], the collection of graphs that admit Hamiltonian cycles consists of with and even; with odd, , and even; and with even and . Of these, I have shown that the following are not laceable: , , , , and , while the following are laceable: , , , , , and . Thus, one conjecture is that the Hamiltonian graph is laceable iff .

Reference

[1] A. Schwenk, "Which Rectangular Chessboards Have a Knight’s Tour?," Mathematics Magazine,64(5), 1991 pp. 325–332. www.jstor.org/stable/2690649.