Skip to content
Advertisement

Knight’ tour using Warnsdorff’s rule gives wrong output with odd sizes mostly

I wrote a code to solve the knight’s tour problem, the problem is that sometimes it gets the wrong output.

In particular, very frequently with odd sizes of the board: For example starting at position [0,1] and with a board 5X5 it gives me:

JavaScript

As you can see there’s a repetition of [2,3]. I checked out how many wrong outputs my algorithm gets given the size of board and I found that with odd sizes it gets right outputs just 50% of the times and with even sizes around 99% of the times. How can it be possible?

JavaScript

Advertisement

Answer

This happens when the selected path runs into a “dead end”.

In the example you mentioned, with starting point [0,1] and size 5×5, this happens when square [2, 3] is selected (the first time). At that point only 2 more squares need to be visited. They are [0,4] and [4,4]. But neither of those squares has any unvisited neighbors.

And so, c remains 0 for both these valid q moves. And that means the value for l will not be set — it keeps its previous value, which still is [2, 3]. And so this duplicate is added when you do start = l

Warnsdorff’s rule is no absolute guarantee of achieving the tour. At several points during the algorithm, there are ties — moves which have an equal c value. In that case you take the last one having this c value. But it could be that you need to pick another one from among those ties in order to get success.

So either you must implement a backtracking algorithm, that detects such “dead ends” and backtracks back to point where there was a tie, and then takes another path from there.

Or you should do something more sophisticated, as there seem to be methods to pick a “right” move from among the ties. See Wikipedia for references to two articles describing methods for breaking ties successfully.

User contributions licensed under: CC BY-SA
10 People found this is helpful
Advertisement