Warnsdorff's rule

In the beginning of the 19:th century a practical method for solving the Knight's tour emerged. In "Des Rösselsprungs einfachste und allgemeinste Lösung" (Schmalkalden, 1823) H. C. Warnsdorff presented his method of constructing knight's tours.

The aim is to avoid creating dead ends - squares from which the knight cannot get further without getting to an already visited square. For that reason the possible squares to be chosen next are examined before every move. One counts the number of free new choices - entrances - every one of them has, and then moves to the square with the lowest number of new choices. (Example see [1] )

Warnsdorff's rule is heuristic. Theoretically there are objections [2], but on a normal 8*8 squares board the rule works just fine.

The Java applet on this page demonstrates the efficiency of Warnsdorff's rule:

Click on any starting square of your choice (mouse left). The numbers of free entrances to the squares of the next legal move will be displayed. Click on the one with the lowest number, and continue this way until the whole board is covered and the knight's tour completed. In many cases there are equal choices and sometimes one might spare a square with the lowest number (in order to have it as the end square of a reentrant tour). There is a certain limited freedom of choice, but squares with one entrance are due to be visited at once - otherwise they will turn into dead ends. One such square can serve as ending square for the whole tour, two means trouble.
Back: Click with mouse right on an already visited square, and the tour will be shortened so that the move from that square can be redone.

Try it and discover how easy it is to solve the Knight's tour with the help of Warnsdorff's rule !

1. Example: Take a look at a square in a corner of the board. From such a square a knight can jump to only two other squares. And the square in the corner can be reached only from these two other squares - the square in the corner has two "entrances". When a knight during a tour happens to visit any of these entrances, it is almost bound to visit the corner square next. If the knight doesn't do that, it has used up one of the two free entrances of the corner square - and thus turned that square into a dead end; the corner square can still be reached later, but there will no longer be any unused way out.
During a knight's tour the number of free entrances to all squares of the board are gradually used up. Warnsdorff's rule serves to direct the knight to the squares with the least numbers of free entrances left - before these squares have turned into dead ends.

2. Warnsdorff's rule gives solutions, but not all possible solutions (One can make moves opposing the rule and yet get a complete tour). The rule possesses a trait of arbitrariness; there is often a choice between equal alternatives. And on really big boards the rule runs into trouble. Warnsdorff scarcely had the possibilities to explore this, but Arnd Roth at the Max-Planck-institut für Medizinische Forschung presents an investigation of this in "The Problem of the Knight"

3. More about the heuristic nature of Warnsdorff's rule and its performance could be found at Efficiency of Warnsdorff's rule.

Reedited 00 03 08

Visitors: