Python Recursive Knight Tour

I’m trying to solve the knight tour algorithms with recursive backtracking method in python.

The solution should be a matrix with 24 documented steps, but it only count up-to 5 steps. It doesn’t enter the recursive if statement.

JUMP_POS = [ (2,1),
             (2,-1),
             (1,2),
             (1,-2),
             (-1,2),
             (-1,-2),
             (-2,1),
             (-2,-1)
           ]

def springen(x, y, nr, matrix):
    matrix_len = len(matrix)
    matrix[x][y] = nr
    if nr == ( (matrix_len*matrix_len) -1 ):
        print("good", matrix)
        return True
    else:
        for pos in JUMP_POS:
            xNeu = x + pos[0]
            yNeu = x + pos[1]

            if xNeu >= 0 and xNeu < matrix_len and yNeu >= 0 and yNeu < matrix_len:
                if matrix[xNeu][yNeu] == 0: #check, if position is empty
                    if springen(xNeu, yNeu, nr+1, matrix):
                        #this section is not passing
                        return True

        matrix[x][y] = 0
        return False

matrix = [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]
print(springen(0,0,0,matrix))

Answer

The problem I see is that you set yNeu = x + pos[1] when you probably meant yNeu = y + pos[1].

Another potential problem is that since you use 0 both for the first step and to mark unvisited squares, you can revisit the starting square later, so consider using -1 or None to mark unvisited locations.

Advertisement

Answer