#2596

Check Knight Tour Configuration

specialist · 710 · lc medium +30 · verified · 60.7% accepted · 525 likes · top 60%

Description

A knight on an n x n chessboard starts at the top-left and must visit every cell exactly once. You are given an n x n integer matrix grid where grid[row][col] is the 0-indexed step at which the knight visited cell (row, col). Return true if grid encodes a valid knight's tour, false otherwise. A knight moves either two squares vertically and one horizontally, or two horizontally and one vertically.

Example 1:

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.

Example 2:

Input: grid = [[0,3,6],[5,8,1],[2,7,4]]

Output: false

Explanation: The above diagram represents the grid. The 8th move of the knight is not valid considering its position after the 7th move.

Code

1

2

3

class Solution:
    def checkValidGrid(self, grid: List[List[int]]) -> bool:

class Solution:
    def checkValidGrid(self, grid: List[List[int]]) -> bool: