Jump to content

Warnsdorff's algorithm

Add links
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Dcoetzee (talk | contribs) at 18:42, 14 June 2008 (Arrange, update). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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.

  • Warnsdorff's rule
  • Pohl, Ira (July 1967). "A method for finding Hamilton paths and Knight's tours". Communications of the ACM. 10 (7): 446–449. doi:10.1145/363427.363463.
  • Preprint of Pohl's paper (freely accessible)
Stub icon

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Warnsdorff%27s_algorithm&oldid=219331215"