Knight's Tour Problem

This combinatorial problem consists in finding a way for a knight on an empty chessboard to visit each square exactly once. If the final square is only one knight's move from the starting square, the tour is referred to as closed; otherwise, it is open. A generalisation involves considering boards of other shapes and sizes or n-dimensional boards.

History

The mathematician Leonhard Euler addressed this "curious question which is not subject to analysis" in 1759 and presented his solution in detail. Ever since, countless people, including many mathematicians, have examined the knight's tour problem. However, it is also an old chess problem first documented in Indian and Arabic manuscripts back in the ninth century. Throughout the entire Middle Ages and still to this day, the problem has never lost its intrigue.  

Mathematics

There are efficient algorithms for the knight's tour problem: an initial approach involves using a simple backtracking technique, whereby a random route is selected. If you reach a dead end, you retrace your last move and choose an alternative one instead. Although this algorithm definitely finds a solution, provided one exists, it is very slow. In 1823 H.C. Warnsdorff proposed a rule where the knight always moves to the space with the fewest vacant spaces for the next move, i.e. ones the knight has not yet visited. Based on this approach, better methods were then developed, where the board is divided into smaller rectangles, for which a solution is known.