knights tour brute force

possible_move_distances = \
[
    (2, 1),
    (-2, 1),
    (2, -1),
    (-2, -1),
    (1, 2),
    (-1, 2),
    (1, -2),
    (-1, -2),
]

class Square:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.visited = False

    @staticmethod
    def in_bounds(x, y, m, n):
        return 0 <= x <= m - 1 and 0 <= y <= n-1

    def moves(self, m, n):
        return [(self.x + dx, self.y + dy) for (dx, dy) in possible_move_distances if self.in_bounds(self.x + dx, self.y + dy, m, n)]    

class Board:
    def __init__(self, m, n, current_x, current_y):
        self.board={}
        self.m = m
        self.n = n
        for i in range(m):
            for j in range(n):
                self.board[(i,j)] = Square(i, j)
        self.solution = []
        self.num_visited = 0
        self.attempts = 0
        self.visit(self.board[(current_x, current_y)])
    
    def solved(self):
        return self.num_visited == self.m * self.n
    
    def backtrack(self):
        self.num_visited -= 1
        removed = self.solution.pop()
        removed.visited = False        
        if self.solution:
            self.current_square = self.solution[-1]
    
    def visit(self, square):
        self.num_visited += 1
        square.visited = True
        self.solution.append(square)
        self.current_square = square
        
    def dfs(self):
        self.attempts += 1  
        print(self.attempts)      
        # for each current nodes' children
        for square_coord in self.current_square.moves(self.m,self.n):
            square = self.board[square_coord]                        
            # if not visited
            if not square.visited:  
                self.visit(square)          
                if self.dfs(): return True            
        
        # check if solved
        if self.solved():
            return True
        
        # if not, backtrack and return False
        self.backtrack()        
        return False

    def print(self):
        for x in range(self.m):
            for y in range(self.n):
                print('X' if self.board[(x, y)].visited else 'O', end ='')
            print()
        print([(square.x, square.y) for square in self.solution])
        # print(f'visited = {self.num_visited}')

board = Board(5, 5, 0, 0)
if board.dfs():
    board.print()
    print ('Found a solution!')
else:
    print('Could not solve board')