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.
You are given an n x n integer matrix grid consisting of distinct integers from the range [0, n * n - 1] where grid[row][col] indicates that the cell (row, col) is the grid[row][col]th cell that the knight visited. The moves are 0-indexed.
Return true if grid represents a valid configuration of the knight's movements or false otherwise.
Note that a valid knight move consists of moving two squares vertically and one square horizontally, or two squares horizontally and one square vertically. The figure below illustrates all the possible eight moves of a knight from some cell.
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.
Constraints:
n == grid.length == grid[i].length3 <= n <= 70 <= grid[row][col] < n * ngrid are unique.The naive approach involves iterating over each number in the grid in the order of the knight's tour (from 0 to n*n-1) and checking if each subsequent move is a valid knight's move. A valid knight's move is defined by the set of permissible relative movements (±2, ±1) or (±1, ±2) on the chessboard. This approach directly checks the given paths in the order of tour numbers.
The C solution starts by mapping each cell in the grid to its corresponding tour number and storing the positions. It then iterates over each move, checking if the next move is a valid knight move using the helper function isValidKnightMove which checks for knight's L-shaped moves.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) as we need to visit each cell exactly once.
Space Complexity: O(n^2) for storing positions of each number.
We can use a graph-like view of the chessboard to verify the knight's tour using Breadth-First Search (BFS). Initialize a BFS starting from the top-left corner, and see if it's possible to visit all cells by only legal knight moves. Maintain a visited array to keep track of visited nodes (grid cells) and ensure connectivity in the tour.
The Python solution employs BFS, using a queue to explore potential knight moves from each current cell. Each time a valid move to a cell labeled as an increasing count is found, it is marked visited, ensuring we cover the full knight tour path while visiting each node (cell) only once.
Time Complexity: O(n^2) since in the worst case, each cell is visited once through BFS.
Space Complexity: O(n^2) due to the visited matrix.
| Approach | Complexity |
|---|---|
| Naive Approach: Validate Each Move | Time Complexity: O(n^2) as we need to visit each cell exactly once. |
| Breadth-First Search Approach for Connectivity | Time Complexity: O(n^2) since in the worst case, each cell is visited once through BFS. |
KNIGHTS TOUR Problem - Backtracking | Leetcode 2596 • Shradha Khapra • 19,179 views views
Watch 9 more video solutions →Practice Check Knight Tour Configuration with our built-in code editor and test cases.
Practice on FleetCode