Home | email | Knight's tour | Warnsdorff results

Warnsdorff's rule II

Abstract: Warnsdorff's rule is heuristic. It does not guarantee a complete tour. On the contrary, the risk of running into a dead end cannot be neglected, when the rule is implemented as an algorithm with fixed priority order.
There has also been proposed an amendment to the rule, which performs considerably better.
The results of the rule and the amendment are given for 5x5 - 15x15 boards on the next page: Warnsdorff's rule results.

On this page there is a Java Applet which demonstrates the problems and could be used for investigation of the influence of fixed priority orders and the amendment.
A general piece of advice might be to also apply backtracking, when implementing Warnsdorff's rule as an algorithm with fixed priority order.

This page focuses on the problems with Warnsdorff's rule that emerge- at least when it is to be implemented for the computer.
Arnd Roth in his "The Problem of the Knight" pointed at the inherent ambiguity in the rule given by Warnsdorff. It often gives a choice between several equally good moves.
Kapil Hari Paranjape in his entertaining A Knight's Tour on OCaml (when a Python fails to digest it) observed the importance of in which order possible "next squares" are tested, and the influence of which square was used for start.

These issues interact. Computers are not built to handle ambiguity, so the usual way of dealing with that, is to deny it and pretend it doesn't exist.Why complicate things, why not just give the computer the next value my fine algorithm delivers ? (Here, of course, I'm only talking for myself). But Arnd Roth proposed an amendment to Warnsdorff's rule, to resolve its ambiguity:
If two or more possible "next squares" are equally good, then choose the one farthest away from the centre of the board. This way, the tour tends to go close to the edges of the board, thereby reducing the apparent risk that the board is split into two or more separate uncovered parts.

The applet above is intended for investigation of these issues.
It handles boards from 5x5 to 400x400 squares, and you can choose which square to start from.
You also can choose if you want to use the amendment proposed by Arnd Roth, or if you want to use a fixed priority order for testing possible "next squares". In the latter case you are free to define that order. Just click the "prio." button, and then click on the marked squares in the order you want them tested. Just remember that the applet has to be stopped befor any changes to the setting could be done.

The speed of the applet however, could be changed whenever you want.
For 15x15 boards or less there is a "step" facility. If this is chosen, the number of free exits (red figures) and priority order for the possible next squares are displayed. Click the button "next" to watch next move.

The first time a tour is completed, and the first time it hits a dead end, the applet is paused and the speed set to "slow". Click "cont." and watch the backtracking. Or change the speed - "fast" is fast enough to find all "Warnsdorff tours" on a 8x8 board within some minute.

The applet has two built in examples.
"ex.1" gives a 50x50 board and a priority order that will cause the tour to split the board into two separate uncovered parts.
"ex.2" gives a 8x8 board and a priority order that will cause the tour not to be ended until it has hit dead ends 35 times.

Exercise: On a NxN board where N is odd, you must start at a dark square, or there will not be any complete tour at all. Explain why !

Visitors: