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:

[[0, 1], [2, 0], [4, 1], [3, 3], [1, 4], [0, 2], [1, 0], [3, 1], [4, 3], [2, 2], [0, 3], [2, 4], [1, 2], [0, 0], [2, 1], [4, 0], [3, 2], [1, 3], [3, 4], [4, 2], [3, 0], [1, 1], [2, 3], [2, 3], [4, 4]]

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?

def rule(start , size):
    moves = [start ,]
    plus = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]
    while 1 == 1 :
        d = 7
        for x in plus:
            s = list(plus)
            c = 0
            q = [ start[0]+x[0] , start[1]+x[1] ]
            if valid(q , size , moves):
                    if len(moves) == size ** 2 -1 :
                        moves.append(q)
                        return moves
                    s.remove((-x[0] , -x[1]))
                    for y in s :
                        p = [ q[0]+y[0] , q[1]+y[1] ]
                        if valid(p , size , moves):
                            c = c+1
                    if 0 < c <= d :
                        l = q
                        d = c
        start = l
        moves.append(start)
        
def valid(q , size , moves):
    if 0 <= q[0] < size  and 0 <= q[1] < size :
        if q not in moves:
            return True
    return False

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.