An $n \times n$ integer matrix grid represents the sequential path of a knight on a chessboard. The value at grid[row][col] represents the step order at which the cell (row, col) is visited, starting from step $0$.

A valid knight tour must satisfy the following conditions:

• The knight must start at the top left cell (0, 0) at step $0$.

• For every step from $k$ to $k + 1$ (where $0 \leq k < n \times n - 1$), the move must be a valid knight move. A knight moves two cells in one cardinal direction and one cell in the perpendicular direction.

Return true if grid represents a valid knight tour configuration, or false otherwise.

Constraints:

• n $==$ grid.length $==$ grid[i].length

• $3 \leq$ n $\leq 7$

• $0 \leq$ grid[row][col] $< n \times n$

• All integers in grid are unique.

Input: grid = [[0, 4, 1], [2, 7, 5], [8, 3, 6]]-List[List[int]]
Output: false-bool
Explanation: Although the tour starts at step 0 in the top-left cell, the move from step 0 at (0, 0) to step 1 at (0, 2) is not a valid knight move.

Input: grid = [[1, 0, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11], [12, 13, 14, 15]]-List[List[int]]
Output: false-bool
Explanation: The top-left cell contains step 1 instead of the required starting step 0, so the configuration is invalid.

Input: grid = [[0, 2, 3, 4, 5, 6], [7, 8, 9, 10, 11, 12], [13, 1, 14, 15, 16, 17], [18, 19, 20, 21, 22, 23], [24, 25, 26, 27, 28, 29], [30, 31, 32, 33, 34, 35]]-List[List[int]]
Output: false-bool
Explanation: The move from step 0 at (0, 0) to step 1 at (2, 1) is valid, but the move from step 1 at (2, 1) to step 2 at (0, 4) is not a valid knight move.

Input: grid = [[0, 11, 22, 17, 2], [21, 6, 1, 10, 15], [12, 23, 16, 3, 18], [7, 20, 5, 14, 9], [24, 13, 8, 19, 4]]-List[List[int]]
Output: true-bool
Explanation: The tour starts at step 0 in the top-left cell, and every consecutive pair of steps forms a valid knight move.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.