How to improve Knight's tour with Warnsdorff's rule?

Question

I know there are several similar threads, but I didn't find a solution even outside of SO. Here's my problem: I implemented Warnsdorff's algorithm for the Knight's Tour problem http://en.wikipedia.org/wiki/Knight%27s_tour , but it doesn't give a solution in some cases. On some places I read it can work much better with some alterations, but nobody specifies which alterations are those. Does somebody know the solution? I know of other algorithms, but they are much more complex.

It sometimes doesn't give a good solution even for a 8x8 chessboard. I think no point in reading through my code, since it's a classical Warnsdorff's: check possible moves, and choose the one with the least possible moves in the next step.

Answer 1

The link for W+ no longer exist, making the accepted answer not usable.

Improvements to the Warnsdorff algorithm are:

Arnd Roth's proposition: Roth decided that the problem in Warnsdorff's heuristic, lays in the random tiebreak rule. The proposition is to break the ties by choosing the successor with the largest euclidean distance from the center of the board.

The problem here is what happens when more than one successor share the same distance.
Arnd Roth claimed that this improvement first failed on a board with 428 rows and had less than 1% failures on all boards with fewer than 2000 rows.

Ira Pohl's proposition: To break the ties Pohl decided to apply Warnsdorff's rule a second time. To achieve this we must take the sum of the degrees of all unvisited neighbors, of the successors that tied, and choose the square whose sum is minimal.

One of the problems here is that no matter how many times we apply Warnsdorff's rule we will result in a tie (between the two adjacent squares) if we start in the corner square. Furthermore if we apply Warnsdorff's heuristic a large number of times then asymptotically this is equal to an exhaustive search.

Pohl also suggested, if we fail to produce a successor after applying Warnsdorff for the 2nd time, to break ties by using a fixed arbitrary ordering of the squares. His claim is that this successfully produces a solution on a 8*8 board.

By using one of these enhancements we have better chances of creating a solution systematically by preventing possible lock-ins.

Answer 2

Here's what I found out:

Please note that this still isn't a definitive answer and I ain't no graph theory expert, so these are observations only.

I'll call the classic Warnsdorff heuristic "W". The improvement from http://mirran.web.surftown.se/knight/bWarnsd.htm (Cached: http://web.archive.org/web/20120213164632/http://mirran.web.surftown.se/knight/bWarnsd.htm) will be called "W+". The improvement from https://github.com/douglassquirrel/warnsdorff/blob/master/5_Squirrel96.pdf?raw=true will be "W2". The number of horizontal fields will be "x" and the vertical will be "y".

So, here are my observations.

The short version:

W is simple, but on many occasions it can't provide a solution. That triggered this question at first. W+ is simple too and gives a big improvement, especially on large boards. W2 is much more complex to implement, and compared to W+ it doesn't seem to give much better results. So I vote for W+. Anyway, that's the variant I'll use.

The long version:

W

advantages: Compared to other Knights Tour algorithms, simplicity. Compared to W+, it doesn't really have advantages. Compared to W2, it's much more easy to implement.

disadvantages: there are plenty of cases when there is a solution, but W can't provide one it tends to mess up with bigger boards (50+)

W+

advantages: Compared to other Knights Tour algorithms, simplicity. Compared to W: it can provide a solution in much more cases and it almost isn't more complex than W. Compared to W2, it's much more easy to implement and W+ works on non-square boards too. 10x20 for example.

disadvantages: Compared to W, it doesn't have disadvantages. Compared to other knights tour algorithms, is that this one can get stuck in some cases. The toughest for W+ are small boards like 5x5, 6x6, 7x7, 9x9 etc. As stated on the Wiki, it has problems with boards when both x and y are even. On the other hand, when x and y are even, but greater than 9 it seems W+ manages to find a solution. Compared to W2, I didn't experience disadvantages.

W2

advantages: Compared to W, it gives solutions in much more cases, especially for large boards. Compared to W+ I didn't notice advantages.

disadvantages: Implementation compared to W and W+.

Conclusion:

My opinion is that W+ is practically the most acceptable. Don't forget that it isn't perfect. And I have to say, that my implementation doesn't allow for really big boards. I tested W+ up to 90x90 (8100 nodes) and it still provided solutions. Although, I didn't do extensive testing because of limited time. I hope this helps someone who confronted this problem before. Because this isn't a definite answer, I won't accept it for a while, in hope that someone appears who can give a complete answer. Sorry for the long read.