Main Page | See live article | Alphabetical index

How to solve the knight's tour

Table of contents
1 Introduction
2 A heuristic
3 x2 && y1 + incy[i]
4 External links


Historically, 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 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.

Step 1

Figure 1. If you can move to a corner square, you must do so.

Figure 2. Step 1 completed.

Step 2

It might happen that there is no way to complete the tour in steps 2c and 2d. If that is the case, repeat step 2b until it is possible to get a complete tour.

Figure 3. The sequence 5->6 has been extended to 5->5a->5b->5c->5d->6 and 8->9 has been extended to 8->8a->8b->8c->8d->8e->8f->9 to complete the tour.

Figure 4. Completed and properly numbered tour.

A heuristic

One popular heuristic for solving the knight's tour problem 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. The Warnsdorff rule is particularly suitable for writing computer programs to solve the knight's tour. Below is an example C program which uses this heuristic.

Example C program for solving the knight's tour using the Warnsdorff rule


/* The dimensions of the chess board */
#define BWID 8
#define BHEIT 8
/* The moves of the knight */
#define JWID 1
#define JHEIT 2

/* Macros for convenience */
#define isinboard(board,x,y) ((x)>=0 && (y)>=0 && (x)

x2 && y1 + incy[i]

y2) return 1; return 0; }

/* Generate a path with a random starting square and each square * chosen according to the smallest degree rule. If a hamiltonian * cycle results, print the solution and return 1. Else return 0. */ int gen_sol() { /* board[y * BWID + x] represents the move number in which the square (x, y) was visited. It is -1 if the square has not been visited so far */ int board[BWID*BHEIT]; /* x and y represent the coordinates of the square being currently visited */ int i, x, y, startx, starty; for(i=0; i

Note 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.

Figure 5. Computer solution using the Warnsdorff heuristic.

External links