Check Knight Tour Configuration — LeetCode 2596 Python Solution

The problem

There is a knight on an n x n chessboard. In a valid configuration, the knight starts at the top-left cell of the board and visits every cell on the board exactly once.

Example

Input

grid = [[0,11,16,5,20],[17,4,19,10,15],[12,1,8,21,6],[3,18,23,14,9],[24,13,2,7,22]]

Output

true

Explanation

The above diagram represents the grid. It can be shown that it is a valid configuration.

Python solution

class Solution:
    def checkValidGrid(self, grid: List[List[int]]) -> bool:
        if grid[0][0]:
            return False
        n = len(grid)
        pos = [None] * (n * n)
        for i in range(n):
            for j in range(n):
                pos[grid[i][j]] = (i, j)
        for (x1, y1), (x2, y2) in pairwise(pos):
            dx, dy = abs(x1 - x2), abs(y1 - y2)
            ok = (dx == 1 and dy == 2) or (dx == 2 and dy == 1)
            if not ok:
                return False
        return True

Complexity

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 2596. Check Knight Tour Configuration is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Related problems