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.