home | alphabetical index | |||||||

## How to solve the knight's tour
## IntroductionHistorically, various methods have been used to solve the Knight's Tour problem. 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.
In the following we will see a method that is easy to learn and can be used to easily construct a knight's tour in less than 5 minutes. The tours so constructed will have the additional property that it is possible for the knight to step from the final square to the initial square, thus forming a closed path or a 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. ## Step 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 (e.g. move 13 of figure 1).
- If you are one move away from a corner square, you must necessarily move to the corner square (See figure 1).
- Follow these rules until all edge squares and all squares bordering an edge square have been visited. You should be in a position similar to figure 2.
Figure 1. If you can move to a corner square, you must do so.
Figure 2. Step 1 completed.## Step 2- 2a) Try to complete the tour by inspection. This is often not possible. If that is the case, read on.
- 2b)
*Arbitrarily*extend the path to get a cycle (i.e. without visiting all the remaining squares). In figure 3, the path has been extended to a cycle of length 54. - 2c) Find pairs of squares along the tour such that
- they are one move away from each other.
- each is one move away from some unvisited square.
- 2d) Use such pairs to complete the tour by inserting new squares between the pair of squares. In figure 3, this has been done using the pairs (5,6) and (8,9).
- 2e) Renumber the squares from 1 to 64 (see figure 4).
## A heuristic
One popular heuristic for solving the knight's tour problem is the
#includeNote that the above program is not restricted to 8x8 chessboards; the parameters BWID and BHEIT control the width and the height respectively. One solution obtained using the above program is shown below.
## External links | |||||||

copyright © 2004 FactsAbout.com |