The Knight’s Tour Solution in Python

Ah, the Knight’s Tour problem! It’s like trying to convince your cat to stop chasing the laser pointer. You know it’s possible, but it just seems to go in circles (or squares, in this case). Imagine a chessboard where a knight (the horsey piece, not the medieval hero) has to visit every square exactly once. Sounds easy, right? Well, it’s not! It’s like trying to find a parking spot in a crowded mall during the holiday season—good luck with that!

In this problem, you’re tasked with finding a way for a knight to traverse an m x n chessboard starting from a specific position (r, c). The knight can move in an “L” shape, which means it can jump two squares in one direction and then one square perpendicular to that. Your goal is to fill the board with the knight’s path, ensuring that every square is visited exactly once.

Solution Links

Code Solution


class Solution:
    def tourOfKnight(self, m: int, n: int, r: int, c: int) -> list[list[int]]:
        dirs = ((1, 2), (2, 1), (2, -1), (1, -2),
                (-1, -2), (-2, -1), (-2, 1), (-1, 2))
        ans = [[-1] * n for _ in range(m)]

        def dfs(i: int, j: int, step: int) -> bool:
            if step == m * n:
                return True
            if i < 0 or i >= m or j < 0 or j >= n:
                return False
            if ans[i][j] != -1:
                return False
            ans[i][j] = step
            for dx, dy in dirs:
                if dfs(i + dx, j + dy, step + 1):
                    return True
            ans[i][j] = -1
            return False

        dfs(r, c, 0)
        return ans

Approach Explanation

The code uses a Depth-First Search (DFS) approach to explore all possible moves of the knight. It starts from the given position (r, c) and attempts to fill the board step by step. If it reaches a point where all squares are filled, it returns True. If it hits a dead end, it backtracks and tries a different path. The knight’s possible moves are defined in the dirs tuple, which contains all the “L” shaped moves.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(8^(m*n))
Space Complexity	O(m*n)

Real-World Example

Think of the Knight’s Tour as a game of hopscotch, where the knight is trying to hop on every square without stepping on the same one twice. Just like how you might strategize your hops to avoid stepping on cracks (because we all know that’s bad luck), the knight must carefully plan its moves to cover the entire board.