How to solve the knight's tour
|
|
Many methods can be used to solve the knight's tour problem, from brute force search on a computer, perhaps aided by a heuristic, to sophisticated mathematical methods based on magic squares. One frequently used method is to break up the 8x8 chessboard into smaller rectangles and solve the problem for the smaller rectangles in such a way that it is possible to combine the smaller paths into one grand path.
| Contents |
Finding a tour by hand
This section presents a method that is easy to learn and can be used to construct a knight's tour in five minutes. The tours so constructed are re-entrant: they have the property that it is possible for the knight to step from the final square to the initial square, thus forming a closed path or cycle.
Broadly, our strategy is to stay near the edges of the board as much as possible, so that towards the end, the squares that are remaining form a well-connected subgraph at the center of the board, enabling us to complete the last few moves by trial and error.
Knights_tour_solution_1.png
1. Start from one of the edge squares, but not one of the corner squares. Keep close to the edges of the board, and avoid the 16 central squares unless there is no alternative. If you are one move away from a corner square, you must necessarily move to the corner square (as indicated by the red arrow).
Knights_tour_solution_2.png
2. Follow these rules until all edge squares and all squares bordering an edge square have been visited. You should be in a position like the one shown on the right.
Knights_tour_solution_3.png
3. With fewer than 16 squares unvisited, you may be able to complete the tour by inspection. But if that is not possible, complete the cycle however you can (the red path in the figure on the right). Now find pairs of adjacent squares along the tour that are both one move away from some unvisited square. Use such pairs to complete the tour by deleting the edge joining the pair (the dotted lines) and replacing it with a path using up some unvisited squares (the blue and green paths).
Knights_tour_solution_4.png
4. If this works out, then you'll have a completed tour. If not, go back to step 2, undo some moves and try again, making different choices this time.
The Warnsdorff heuristic
Knights_tour_solution_Warnsdorff.png
If you are programming a computer to find a knight's tour (as opposed to enumerating all the tours) it's useful to have a heuristic to direct the computer into productive regions of the search space. One popular heuristic is the Warnsdorff rule. According to this rule, at each step the knight must move to that square which has the lowest degree (the degree of a square is the number of squares to which the knight can move from that square). The rationale for this is that towards the end, we will be left with squares having a high degree, and so there is a smaller chance of arriving at a square from which there is no move.
References
- H. C. Warnsdorff, "Des Rösselsprungs einfachste und allgemeinste Lösung", Schmalkalden, 1823.
External links
- Warnsdorff's rule (http://w1.859.telia.com/~u85905224/knight/eWarnsd.htm)
- History of knight's tours (http://www.ktn.freeuk.com/1a.htm)