Introduction :

To the best of my knowledge, no exhaustive study of Warnsdorff’s rule for Knight’s Tour of the chessboard has been published. This paper presents the results for the work done on closed (re-entrant) solutions (tours) obtainable on a standard 8 x 8 chessboard. Since an exhaustive study was intended, no attempt has been made to resolve a tie, if it occurs along the way. Instead, all the alternative paths have been followed, without assigning priority thereto.

While conducting this study, it was noticed that strictly following the rule does not necessarily take the knight to a square with truly minimum further outlets. Some variations of the rule were hence thought of, without violating the rule in its true spirit. In doing so, some new terms such as “Corner Dash (CD)” (full or semi), “End Corner Dash (ECD)” and “Extended End Corner Dash (XCD)” have been coined and defined. All the computations have been carried out for all the 10 (Ten) unique starting points and their corresponding 53 (Fifty-three) ending points to make the tour closed.

Warnsdorff’s Rule :

Warnsdorff’s Rule[1] for Knight’s Tour states that at every step, a move should be made to a square from where there are fewest outlets to unvisited cells. This suggests that before making a move, one should work out available number of moves from each target square. All such available number of moves should be compared and the target square from where minimum further moves are available, should be chosen for making the move to that target cell.

This immediately raises a question. If there are two or more such target squares from where equal number of further moves are available and this number is minimum when compared with other remaining target squares, which target square should be chosen for the move? Many people have devised methods for resolving this “Tie”. Literature is full of rules for resolving the tie. The present work has not bothered with resolving any tie. The reason for this is already given above and will appear again later.

Previous Work Done :

The problem of Knight’s Tour of the chessboard, being at least 5 (perhaps 11 to 12) centuries old, has been widely worked on. A simple search using the Google® Search Engine easily detects several thousand significant results (web-pages). I have visited several hundred such web-pages. I have not found any work similar to the one presented here.

I have published a book[2] in which a full chapter is devoted to this subject. All the material in this paper has been extracted from the book.

Background :

A little bit of background about the present work is in order. A computer program was made in 1978 for working out Knight’s Tour solutions. It followed a so called “brute-force” method.

Moves were numbered from 1 to 8. Move number 1 was two squares to right and one square down. Going clockwise, move number 2 was two squares down and one square right, and so on, till move number 8 was two squares to right and one square up.

This scheme is shown in Figure – 1.

At each move, the program worked out all the available moves for the knight from where it stood. Naturally, the moves that took the knight outside the board or the moves that took the knight to an already visited square were omitted. These available moves were stored in a matrix called an Options Matrix against the move number to be made on the board. After storing all available moves from the particular square (cell), the program made the numerically highest move and deleted the move being made from the Options Matrix.

This procedure was continued, hoping that it would result in a solution. The aim was to work out all available solutions, of course, a very naïve approach. If a solution was reached, the program would store the solution and back-track by one move. Again, the numerically largest of the remaining available moves would be made and the process would continue. If at any stage the knight is stuck-up and without a further move, it would back-track by one move. Once again, the process would continue with the numerically highest move and so on.

This program did not produce even a single solution despite providing lots of CPU time on DEC-1077 mainframe computer. This is when a friend suggested using Warnsdorff’s rule. In addition to the evaluation part (of Warnsdorff’s rule) the only modification necessary in the available program was that instead of storing all the available moves at each stage, the available options were stored only when there was a tie between (among) two (or more) moves for “minimum outlets” condition. Since all the alternative paths were to be tested one-by-one, no need was felt of resolving the tie. All the options for equally minimum outlets were indeed tried out. This is the reason for labeling this work as an exhaustive study of Warnsdorff’s rule. There is one more reason for calling this as exhaustive study but that will be discussed later in appropriate context.

If there is no tie for any particular position (only a single move has minimum further outlets), then no entry is made into the Options Matrix.

As mentioned earlier, back-tracking would be invoked under two circumstances. One is when the knight is stuck-up and there is no move left. Second is when a full solution is reached. In the modified program, instead of back-tracking by one move only, it is by several moves, till the previous tie position is reached. This is easily detected by looking for a non-zero entry in the Options Matrix.

The program was modified and run in 1981. It was a pleasant surprise to find out that solutions started pouring in. Six thousand solutions were printed out on 250 pages, 24 solutions per page, with five sets of 1,200 solutions per set of 50 pages. Each set of 1,200 solutions took only between 52 and 58 seconds of CPU run time on the mainframe computer. The 6,000 solutions were studied carefully. It was found that the first 25 moves were identical in all the solutions. This meant that the solutions would be so many that it may not be feasible to record all of them. Therefore, it was decided to concentrate on getting closed solutions only. The program was once again modified to get only closed solutions. This attempt was also successful in 1981. In order to get a closed solution, the program first defines the starting point and ending point on the board. Obviously, to have a closed tour, the ending point and starting points are at a knight’s move apart. Since several sets of starting and ending points exist on the board, there are as many sets of different number of solutions in each set.

Number of Sets (Algorithms) Worked Out :

Let us first understand the co-ordinate system used. Standard notation used for recording moves of a game of chess labels the columns from left to right as “a to h”. White pieces side is at the bottom of the board, therefore, the rows are numbered from bottom to top as “1 to 8”. This system is depicted in Figure – 2.

There are only 10 unique starting points on the board of 64 cells. Other 54 cells are isomorphic with these 10. These starting points are:

1) Cell a8. There are 3 more (total 4) isomorphic points on the board.
2) Cell b8. There are 7 more (total 8) isomorphic points on the board.
3) Cell c8. There are 7 more (total 8) isomorphic points on the board.
4) Cell d8. There are 7 more (total 8) isomorphic points on the board.
5) Cell b7. There are 3 more (total 4) isomorphic points on the board.
6) Cell c7. There are 7 more (total 8) isomorphic points on the board.
7) Cell d7. There are 7 more (total 8) isomorphic points on the board.
8) Cell c6. There are 3 more (total 4) isomorphic points on the board.
9) Cell d6. There are 7 more (total 8) isomorphic points on the board.
10) Cell d5. There are 3 more (total 4) isomorphic points on the board.

These starting points are shown in Figure – 3.

The corresponding ending points for a closed tour are:

1) cells c7 or b6; i.e., 2 ending points
2) cells a6, c6 or d7; i.e., 3 ending points
3) cells a7, b6, d6 or e7; i.e., 4 ending points
4) cells b7, c6, e6 or f7; i.e., 4 ending points
5) cells a5, c5, d6 or d8; i.e., 4 ending points
6) cells a8, a6, b5, d5, e6 or e8; i.e., 6 ending points
7) cells b8, b6, c5, e5, f6 or f8; i.e., 6 ending points
8) cells b8, a7, a5, b4, d4, e5, e7 or d8; i.e., 8 ending points
9) cells c8, b7, b5, c4, e4, f5, f7 or e8; i.e., 8 ending points
10) cells c7, b6, b4, c3, e3, f4, f6 or e7; i.e., 8 ending points

There are thus 53 combinations in total for all the starting and ending points, giving us 53 algorithms for working out all the solutions with Warnsdorff’s rule.

Working of the Computer Program :

With the background as above, we are ready to understand the working of the program and how all the options from Warnsdorff’s rule are tried out one after another. We will generate the first solution along with its options matrix. The starting point selected is the top left corner of the board, the cell “a8”. This gets the number 1. From here, we start evaluating each move before actually making any move. From square marked 1, we have two moves available. Move type 1 takes us to cell “c7” and move type 2 takes us to cell “b6”. Since we are aiming to make the tour closed, the cell “c7″is arbitrarily reserved for move number 64. Hence, the only target cell now left is b6. We write the number 2 in this cell, i.e., move the knight to this square b6.

From the cell marked 2, we have five moves available. Move type 1 takes us to cell “d5”, type 2 takes us to cell “c4”, type 3 takes us to cell “a4”, type 7 takes us to cell “c8” and type 8 takes us to cell “d7”. From d5 and c4, there are 7 outlets available. From d7, there are 5 outlets. From a4 and c8, there are 3 outlets. The minimum number of outlets is 3 and these are from two target cells, a4 and c8. There is thus a tie for this move. Any one move can be chosen, reserving the other for later evaluation. As per the program logic, the numerically higher move (type 7) is chosen, taking us to c8. At the same time, Options Matrix stores the information that from cell numbered 2 move type 3 was also having minimum outlets. This is achieved by storing the number 3 at location MO(2,1). Here, MO is the options matrix with DIMENSION (64,8).

Thus, we write the number 3 in the cell c8 and proceed further. The further working is continued in similar manner till we reach the cell a5 at move number 20. From here, there are three target cells by move types 1, 2 and 8; reaching c4, b3 and c6 respectively. When we evaluate the number of outlets from each of these target cells, we find that from each target cell, there are exactly 4 outlets. Thus, there is a triple tie. As before, per program logic, we select the last direction (8) and move to cell c6 and write the number 21 in that cell. Now, we have here two more target cells to be remembered within the Options Matrix, having equal number of outlets to the selected option. This is done by storing (move type) number 1 at MO(20,1) and storing (move type) number 2 at MO(20,2).

Further working is not discussed in detail. By proceeding further as per above algorithm, we complete the tour as per Figure 4. This is the first solution obtained with this method.

There was no need to use back tracking of moves even once. While generating the solution, there are further entries in the options matrix MO whenever there are two or more target cells with equal number of minimum outlets. Having obtained the first solution as above, now let us see how we can generate more solutions from the first one. First, let us review the nonzero entries in the options matrix MO. These are at (2,1), (20,1), (20,2), (41,1), (41,2), (43,1), (47,1), (48,1) and (49,1) being the last nonzero entry. Hence, we come back to the cell e6 marked 49, erasing the numbers 50 through 64 working manually, or storing 0 (zero, signifying that the square is available [unvisited] for the knight) into those locations when the computer program back tracks to the cell e6 marked 49. At this point, we see that MO(49,1) had the value 2. So, we make move type 2 and write number 50 in cell f4. At the same time, we set the value of location MO(49,1) to 0 (zero) because we have now used up the option. The further working is normal upto the solution obtained in Figure – 5 as the second solution by this method. Here, at move 54, there is a tie and a nonzero entry MO(54,1) = 5 gets generated.