Wolfram Demonstrations Project

12,000+ Open Interactive Demonstrations
Powered by Notebook Technology »

Laceable Knight Graphs

Download to Desktop Copy to Clipboard
Source

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

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.

Contributed by: Stan Wagon (July 2012)
(Macalester College)
Open content licensed under CC BY-NC-SA

Snapshots

Details

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.

Embed Code

Take advantage of the Wolfram Notebook Emebedder for the recommended user experience.

Related Demonstrations More by Author
Browse all topics
Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send