Watch 10 video solutions for Check Knight Tour Configuration, a medium level problem involving Array, Depth-First Search, Breadth-First Search. This walkthrough by Shradha Khapra has 59,711 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |