Warnsdorff's algorithm

Warnsdorff's algorithm is a heuristic method for solving the Knight's Tour. The algorithm was first described in "Des Rösselsprungs einfachste und allgemeinste Lösung" by H. C. Warnsdorff in 1823.

Warnsdorf's rule was to always choose the next square that had the fewest possible further knight's moves. This more generally can be applied to any graph, by always choosing the next node that has smallest degree. Pohl generalized this by adding a rule for breaking ties. Although the Hamiltonian path problem is NP-hard in general, on many graphs that occur in practice this linear-time heuristic is able to successfully locate a solution. The knight's tour is a special case.

External links

* [http://web.telia.com/~u85905224/knight/eWarnsd.htm Warnsdorff's rule]
*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|url = http://portal.acm.org/citation.cfm?id=363463|doi = 10.1145/363427.363463
* [http://www.slac.stanford.edu/cgi-wrap/getdoc/slac-pub-0261.pdf Preprint of Pohl's paper (freely accessible)]