The Knight’s Tour — LeetCode 2664 Python Solution

The problem

Given two positive integers m and n which are the height and width of a 0-indexed 2D-array board, a pair of positive integers (r, c) which is the starting position of the knight on the board. Your task is to find an order of movements for the knight, in a manner that every cell of the board gets visited exactly once (the starting cell is considered visited and you shouldn't visit it again).

Example

Input

m = 1, n = 1, r = 0, c = 0

Output

[[0]]

Explanation

There is only 1 cell and the knight is initially on it so there is only a 0 inside the 1x1 grid.

Python solution

class Solution:
    def tourOfKnight(self, m: int, n: int, r: int, c: int) -> List[List[int]]:
        def dfs(i: int, j: int):
            nonlocal ok
            if g[i][j] == m * n - 1:
                ok = True
                return
            for a, b in pairwise((-2, -1, 2, 1, -2, 1, 2, -1, -2)):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and g[x][y] == -1:
                    g[x][y] = g[i][j] + 1
                    dfs(x, y)
                    if ok:
                        return
                    g[x][y] = -1

        g = [[-1] * n for _ in range(m)]
        g[r][c] = 0
        ok = False
        dfs(r, c)
        return g

Complexity

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 2664. The Knight’s Tour is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Related problems