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.Problem Overview: You receive an n x n grid containing numbers from 0 to n²-1. Each number represents the order in which a chess knight visits that cell. The task is to verify whether the sequence forms a valid knight’s tour starting from the top-left cell (0,0).
Approach 1: Validate Each Move (Simulation) (Time: O(n²), Space: O(n²))
The simplest approach directly simulates the tour. First scan the grid and store the coordinates of every step k in an array indexed by the step number. This lets you quickly access the position of move k and move k+1. Then iterate through the sequence from 0 to n²-2 and verify that each transition follows a valid knight move: (±1, ±2) or (±2, ±1). If any consecutive pair violates the knight movement rule, the configuration is invalid. This solution relies on simple array indexing and a small set of move checks, making it both clean and efficient for interview settings.
Approach 2: Breadth-First Search for Connectivity (Time: O(n²), Space: O(n²))
Another way to reason about the tour is to treat the board as a graph where each cell is a node and edges represent valid knight moves. Starting from the cell labeled 0, perform a Breadth-First Search to explore reachable cells using valid knight moves. While traversing, ensure the next visited node corresponds to the next required step in the sequence. BFS ensures that movement rules are respected and that every step in the path is connected correctly. Although this works, it introduces extra traversal logic compared to the direct simulation approach.
The grid itself acts as a matrix representation of the knight’s tour. The key observation is that the order of numbers already defines the path, so validation only requires checking that each consecutive pair forms a legal knight move.
Recommended for interviews: The simulation approach is the expected solution. It runs in linear time relative to the number of cells and avoids unnecessary graph traversal. Mentioning the brute-force validation first shows understanding of the rules, while implementing the direct coordinate check demonstrates strong problem-solving efficiency.
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.
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.
Python
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.
We first use an array pos to record the coordinates of each cell visited by the knight, then traverse the pos array and check if the coordinate difference between two adjacent cells is (1, 2) or (2, 1). If not, return false.
Otherwise, after the traversal, return true.
The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the side length of the chessboard.
Python
Java
C++
Go
TypeScript
| 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. |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Validate Each Move (Simulation) | O(n²) | O(n²) | Best general solution; directly verifies sequential knight moves |
| Breadth-First Search Connectivity | O(n²) | O(n²) | Useful when modeling the board as a graph or explaining traversal logic |
KNIGHTS TOUR Problem - Backtracking | Leetcode 2596 • Shradha Khapra • 59,711 views views
Watch 9 more video solutions →Practice Check Knight Tour Configuration with our built-in code editor and test cases.
Practice on FleetCode