Check Knight Tour Configuration solution and explanation
Google
9 more videos on this problem
KNIGHTS TOUR Problem - Backtracking | Leetcode 2596Shradha Khapra · 22:32 · 71K views
2596. Check Knight Tour Configuration | Weekly Contest 337 | LeetCode 2596Bro Coders · 6:53 · 1K views
LeetCode 2596. Check Knight Tour Configuration - Interview Prep Ep 139Fisher Coder · 10:46 · 1K views
6322. Check Knight Tour Configuration - LEETCODE WEEKLY CONTEST 337 (Logic explained in details)Joyjit Codes · 4:03 · 868 views
2596. Check Knight Tour Configuration - JAVA (Weekly Contest 337)Sourin Majumdar · 10:37 · 745 views
D-587 | The Knight's tour problem | GFG POTD today 6 Oct 2025 |Leetcode 2596| Problem Of The DayAkshay Anil · 16:07 · 495 views
Leetcode Weekly contest 337 - Medium - Check Knight Tour ConfigurationPrakhar Agrawal · 6:33 · 408 views
2596. Check Knight Tour Configuration (Leetcode Medium)Programming Live with Larry · 11:05 · 325 views
Leetcode 2596: Check Knight Tour ConfigurationAlgorithms Casts · 15:37 · 264 views
Check Knight Tour Configuration| Leetcode 2596 | C++ | Weekly 337Tech Courses · 6:58 · 257 views
The problem
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 * n- All integers in
gridare unique.
Approach overview
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 1: Naive Approach: Validate Each Move
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.
def is_valid_knight_move(x1, y1, x2, y2):
dx = abs(x1 - x2)
dy = abs(y1 - y2)
return (dx == 2 and dy == 1) or (dx == 1 and dy == 2)
def check_valid_knight_tour(grid):
n = len(grid)
positions = [(0, 0) for _ in range(n * n)]
for i in range(n):
for j in range(n):
step = grid[i][j]
positions[step] = (i, j)
for i in range(n * n - 1):
x1, y1 = positions[i]
x2, y2 = positions[i + 1]
if not is_valid_knight_move(x1, y1, x2, y2):
return False
return Truepublic class KnightTour {
public boolean checkValidKnightTour(int[][] grid) {
int n = grid.length;
int[][] positions = new int[n * n][2];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int step = grid[i][j];
positions[step][0] = i;
positions[step][1] = j;
}
}
for (int i = 0; i < n * n - 1; i++) {
if (!isValidKnightMove(positions[i][0], positions[i][1], positions[i + 1][0], positions[i + 1][1])) {
return false;
}
}
return true;
}
private boolean isValidKnightMove(int x1, int y1, int x2, int y2) {
int dx = Math.abs(x1 - x2);
int dy = Math.abs(y1 - y2);
return (dx == 2 && dy == 1) || (dx == 1 && dy == 2);
}
}#include <vector>
#include <cmath>
using namespace std;
bool isValidKnightMove(int x1, int y1, int x2, int y2) {
int dx = abs(x1 - x2);
int dy = abs(y1 - y2);
return (dx == 2 && dy == 1) || (dx == 1 && dy == 2);
}
bool checkValidKnightTour(vector<vector<int>> &grid) {
int n = grid.size();
vector<pair<int, int>> positions(n * n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
positions[grid[i][j]] = {i, j};
}
}
for (int i = 0; i < n * n - 1; ++i) {
auto [x1, y1] = positions[i];
auto [x2, y2] = positions[i + 1];
if (!isValidKnightMove(x1, y1, x2, y2)) {
return false;
}
}
return true;
}function isValidKnightMove(x1, y1, x2, y2) {
const dx = Math.abs(x1 - x2);
const dy = Math.abs(y1 - y2);
return (dx === 2 && dy === 1) || (dx === 1 && dy === 2);
}
function checkValidKnightTour(grid) {
const n = grid.length;
const positions = new Array(n * n);
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
const step = grid[i][j];
positions[step] = [i, j];
}
}
for (let i = 0; i < n * n - 1; i++) {
const [x1, y1] = positions[i];
const [x2, y2] = positions[i + 1];
if (!isValidKnightMove(x1, y1, x2, y2)) {
return false;
}
}
return true;
}#include <stdbool.h>
bool isValidKnightMove(int x1, int y1, int x2, int y2) {
int dx = abs(x1 - x2);
int dy = abs(y1 - y2);
return (dx == 2 && dy == 1) || (dx == 1 && dy == 2);
}
bool checkValidKnightTour(int** grid, int n) {
int positions[n*n][2];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int step = grid[i][j];
positions[step][0] = i;
positions[step][1] = j;
}
}
for (int i = 0; i < n*n - 1; i++) {
if (!isValidKnightMove(positions[i][0], positions[i][1], positions[i+1][0], positions[i+1][1])) {
return false;
}
}
return true;
}public class KnightTourChecker {
public bool CheckValidKnightTour(int[][] grid) {
int n = grid.Length;
(int, int)[] positions = new (int, int)[n * n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int step = grid[i][j];
positions[step] = (i, j);
}
}
for (int i = 0; i < n * n - 1; i++) {
var (x1, y1) = positions[i];
var (x2, y2) = positions[i + 1];
if (!IsValidKnightMove(x1, y1, x2, y2)) {
return false;
}
}
return true;
}
private bool IsValidKnightMove(int x1, int y1, int x2, int y2) {
int dx = Math.Abs(x1 - x2);
int dy = Math.Abs(y1 - y2);
return (dx == 2 && dy == 1) || (dx == 1 && dy == 2);
}
}The Python approach maps every move number to its respective position and verifies each knight's move using a simple function to check the L-shaped move on a chessboard.
Time Complexity: O(n^2)
Space Complexity: O(n^2)
Approach 2: Breadth-First Search Approach for Connectivity
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.
from collections import deque
def is_valid_position(x, y, n):
return 0 <= x < n and 0 <= y < n
def bfs_knight_checker(grid):
n = len(grid)
directions = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]
visited = [[False] * n for _ in range(n)]
queue = deque([(0, 0)])
visited[0][0] = True
count = 1
while queue:
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if is_valid_position(nx, ny, n) and not visited[nx][ny] and grid[nx][ny] == count:
visited[nx][ny] = True
queue.append((nx, ny))
count += 1
break
return count == n * nThe 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 3: Simulation
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.
function checkValidGrid(grid: number[][]): boolean {
if (grid[0][0] !== 0) {
return false;
}
const n = grid.length;
const pos = Array.from(new Array(n * n), () => new Array(2).fill(0));
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
pos[grid[i][j]] = [i, j];
}
}
for (let i = 1; i < n * n; ++i) {
const p1 = pos[i - 1];
const p2 = pos[i];
const dx = Math.abs(p1[0] - p2[0]);
const dy = Math.abs(p1[1] - p2[1]);
const ok = (dx === 1 && dy === 2) || (dx === 2 && dy === 1);
if (!ok) {
return false;
}
}
return true;
}func checkValidGrid(grid [][]int) bool {
if grid[0][0] != 0 {
return false
}
n := len(grid)
type pair struct{ x, y int }
pos := make([]pair, n*n)
for i, row := range grid {
for j, x := range row {
pos[x] = pair{i, j}
}
}
for i := 1; i < n*n; i++ {
p1, p2 := pos[i-1], pos[i]
dx := abs(p1.x - p2.x)
dy := abs(p1.y - p2.y)
ok := (dx == 2 && dy == 1) || (dx == 1 && dy == 2)
if !ok {
return false
}
}
return true
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity comparison
| Approach | Complexity |
|---|---|
| Naive Approach: Validate Each Move | Time Complexity: O(n^2) |
| Breadth-First Search Approach for Connectivity | Time Complexity: O(n^2) since in the worst case, each cell is visited once through BFS. |
| Simulation | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Check Knight Tour Configuration easy or hard?
The problem is rated Medium because it requires understanding chess knight movement and validating a sequence efficiently. The algorithm itself is straightforward once you map step numbers to coordinates.
Check Knight Tour Configuration Python/Java solution
Most implementations build an array that stores the coordinates for each step number, then verify the knight move rule between consecutive steps. The same logic works across Python, Java, C++, and JavaScript with O(n²) complexity.
How to solve Check Knight Tour Configuration in O(n²)?
Scan the grid and record the position of each number from 0 to n²−1. Then iterate through the sequence and check whether the difference between consecutive positions matches a valid knight move (1,2) or (2,1). If all transitions are valid, the configuration represents a correct knight tour.
What is the best approach for Check Knight Tour Configuration?
The best approach is direct simulation. Store the coordinates of each step number and verify that every consecutive pair forms a valid knight move. This runs in O(n²) time and avoids unnecessary graph traversal.
Is Check Knight Tour Configuration asked at Google/Amazon/Meta?
Knight move and grid traversal problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants involving chess moves, graph traversal, or grid validation are common interview exercises.
What data structure is used in Check Knight Tour Configuration?
The solution primarily uses arrays to map step numbers to board coordinates. The grid itself is treated as a matrix, and some alternative explanations model the board as a graph for BFS traversal.
What is the time complexity of Check Knight Tour Configuration?
The optimal solution runs in O(n²) time because every cell in the grid must be processed once to map step numbers to coordinates and validate moves. Space complexity is also O(n²) to store positions of all steps.