Editing Knight's tour (section)

===Warnsdorf's rule===
{{Chess diagram
| tright
|
|  |  |  |  |  |  |  |
|  |  |  |  |  |  |  |
|x3|  |x7|  |  |  |  |
|  |  |  |x7|  |  |  |
|  |nl|  |  |  |  |  |
|  |  |  |x7|  |  |  |
|x2|  |x5|  |  |  |  |
|  |  |  |  |  |  |  |
|A graphical representation of Warnsdorf's Rule. Each square contains an integer giving the number of moves that the knight could make from that square. In this case, the rule tells us to move to the square with the smallest integer in it, namely 2.
}}

[[File:Knight's Tour of 130x130 Square Board.png|thumb|A very large (130 × 130) square open knight's tour created using Warnsdorf's Rule]]

Warnsdorf's rule is a [[heuristic]] for finding a single knight's tour. The knight is moved so that it always proceeds to the square from which the knight will have the ''fewest'' onward moves. When calculating the number of onward moves for each candidate square, we do not count moves that revisit any square already visited. It is possible to have two or more choices for which the number of onward moves is equal; there are various methods for breaking such ties, including one devised by Pohl<ref name="pohl"/> and another by Squirrel and Cull.<ref>{{cite web |url=https://github.com/douglassquirrel/warnsdorff/blob/master/5_Squirrel96.pdf?raw=true |title=A Warnsdorff-Rule Algorithm for Knight's Tours on Square Boards |access-date=2011-08-21 |last=Squirrel |first=Douglas |author2=Cull, P. |website=[[GitHub]] |year=1996}}</ref>

This rule may also more generally be applied to any graph. In graph-theoretic terms, each move is made to the adjacent vertex with the least [[degree (graph theory)|degree]].<ref name="Van Horn et. al">{{cite conference| first=Gijs| last=Van Horn| author2=Olij, Richard| author3=Sleegers, Joeri| author4=Van den Berg, Daan| title=A Predictive Data Analytic for the Hardness of Hamiltonian Cycle Problem Instances| conference=DATA ANALYTICS 2018: The Seventh International Conference on Data Analytics| publisher=[[Xpert Publishing Services|XPS]]| location=Athens, greece| pages=91–96| year=2018| url=https://pure.uva.nl/ws/files/30312375/_2018_Van_Horn_et_al_A_Predictive_Data_Analytic.pdf| access-date=2018-11-27| isbn=978-1-61208-681-1}}</ref> Although the [[Hamiltonian path problem]] is [[NP-hardness|NP-hard]] in general, on many graphs that occur in practice this heuristic is able to successfully locate a solution in [[linear time]].<ref name="pohl">{{cite journal|last= Pohl|first= Ira|title= A method for finding Hamilton paths and Knight's tours|journal= Communications of the ACM|volume= 10|issue= 7|date= July 1967|pages= 446–449|doi= 10.1145/363427.363463|citeseerx= 10.1.1.412.8410|s2cid= 14100648}}</ref> The knight's tour is such a special case.<ref name="alwan-waters">{{cite conference| first=Karla |last=Alwan|author2=Waters, K. |title=Finding Re-entrant Knight's Tours on N-by-M Boards|conference=ACM Southeast Regional Conference| publisher=[[Association for Computing Machinery|ACM]]| location=New York, New York| pages=377–382| year=1992| doi= 10.1145/503720.503806}}</ref>

The [[heuristic]] was first described in "Des Rösselsprungs einfachste und allgemeinste Lösung" by H. C. von Warnsdorf in 1823.<ref name="alwan-waters"/>

A computer program that finds a knight's tour for any starting position using Warnsdorf's rule was written by Gordon Horsington and published in 1984 in the book ''Century/Acorn User Book of Computer Puzzles''.<ref>{{cite book |title=Century/Acorn User Book of Computer Puzzles|editor-first=Simon|editor-last=Dally|isbn=978-0712605410|year=1984|publisher=Century Communications }}</ref>