Knight’s tours

A knight’s tour is a sequence of moves of a knight on an $n \times n$ chessboard following the rules of chess such that the knight visits each square exactly once. A knight’s tour is called a closed tour if the knight finally returns to the starting square and otherwise it is called an open tour.

For example, here is an open knight’s tour on a $5 \times 5$ board:

A knight’s tour corresponds to a Hamiltonian path in a graph whose nodes represent the squares of the board, and two nodes are connected with an edge if a knight can move between the squares according to the rules of chess.

A natural way to construct a knight’s tour is to use backtracking. The search can be made more efficient by using heuristics that attempt to guide the knight so that a complete tour will be found quickly.

Warnsdorf’s rule

Warnsdorf’s rule is a simple and effective heuristic for finding a knight’s tour¹. Using the rule, it is possible to efficiently construct a tour even on a large board. The idea is to always move the knight so that it ends up in a square where the number of possible moves is as small as possible.

For example, in the following situation, there are five possible squares to which the knight can move (squares $a \ldots e$):

1. This heuristic was proposed in Warnsdorf’s book Des Rösselsprunges einfachste und allgemeinste Lösung in 1823. There are also polynomial algorithms for finding knight’s tours (I. Parberry, An efficient algorithm for the Knight’s tour problem, 1997), but they are more complicated. ↩