| Knight's Tour |
Article Index for Knight's |
Website Links For Knights |
Information AboutKnight's Tour |
|
The Knight's Tour is a mathematical problem involving a Knight on a Chessboard . The knight is placed on the empty board and, moving according to the rules of Chess , must visit each square exactly once. There are several Billion solutions to the problem, of which about 122,000,000 have the knight finishing on a square from which it attacks the starting square, called a ''recursive solution.'' Such a tour is described as ''closed''. Otherwise the tour is ''open'' (as in the diagram). Many variations on this topic have been studied by Mathematician s, including Euler , during the centuries using:
The knight's tour problem is an instance of the more general Hamiltonian Path Problem in Graph Theory , which is NP-complete . The problem of getting a closed knight's tour is similarly an instance of the Hamiltonian Cycle Problem . Note however that, unlike the general Hamiltonian Path Problem , the knight's tour problem can be solved in linear time ( Conrad et al 1994). The pattern made by a Knight's Tour has often been used as a Literary Constraint . The earliest instance of this is found in Rudrata's Kavyalankara written during the 9th Century . In the ''. SCHWENK'S THEOREM For any ''m'' × ''n'' board with ''m'' less than or equal to ''n'', a closed knight's tour is possible unless one or more of these three conditions are true: 1. ''m'' and ''n'' are both odd 2. ''m'' = 1, 2, or 4 3. ''m'' = 3 and ''n'' = 4, 6, or 8 It is not hard to show that when condition 1 is true a closed knight's tour is impossible. Imagine a chessboard colored black and white in the manner that we are all familiar with (alternating). Whenever a knight moves it lands on the opposite color. If it is on white, it moves to black. If it is on black, it moves to white. Since ''m'' and ''n'' are both odd, the number of white squares and black squares are different. It follows that a closed tour is impossible on such a board. Open tours may still exist. It is also easy to see why when ''m'' = 1 or 2 that no knight's tour is possible: the knight would not be able to reach every square (with the exception of the trivial case 1x1). SEE ALSO REFERENCES
EXTERNAL LINKS |
|
|