# Knight's tours¶

A knight's tour is sequence of moves of a knight on an $n \times n$ chess board following the rules of chess such that the knight visits each square exactly once.

A knight's tour is

closedif the knight finally returns to the starting square and otherwise it is calledopentour.A knight's tour corresponds to a Hamiltonian path in a graph whose nodes represent the suqare 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 fficient by using

heuristicsthat attempt to guide the knight so that a complete tour will be found quickly

Polynomial algorithms

There are also polynomial algorithms for finding knight's tours, but they are more complicated.

## Warnsdorf's rule¶

Warnsdorf's rule is a simple and effective heruistic 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.

## Related Topic¶

[Hamiltonian Paths]