LeetCode 2596 - Check Knight Tour Configuration

The problem gives us an n x n matrix called grid, where every number from 0 to n n - 1 appears exactly once. Each value represents the order in which a knight visited that cell during a tour of the chessboard. A knight in chess moves in an L-shape.

leetcodemediumarraydepth-first-searchbreadth-first-searchmatrixsimulation

LeetCode Problem 2596

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Breadth-First Search, Matrix, Simulation

Solution

Problem Understanding

The problem gives us an n x n matrix called grid, where every number from 0 to n * n - 1 appears exactly once. Each value represents the order in which a knight visited that cell during a tour of the chessboard.

A knight in chess moves in an L-shape. From position (r, c), it can move to any of these eight possible positions:

  • (r + 2, c + 1)
  • (r + 2, c - 1)
  • (r - 2, c + 1)
  • (r - 2, c - 1)
  • (r + 1, c + 2)
  • (r + 1, c - 2)
  • (r - 1, c + 2)
  • (r - 1, c - 2)

The task is to determine whether the matrix describes a valid knight's tour configuration.

A valid configuration must satisfy two conditions:

  1. The knight must start at the top-left corner (0, 0), meaning grid[0][0] must equal 0.
  2. Every consecutive move must follow the legal movement rules of a knight.

The input guarantees that:

  • Every number is unique.
  • Every value lies within the valid range.
  • The board size is between 3 and 7.

These constraints are small. Even the largest board contains only 49 cells. This tells us we do not need sophisticated optimization techniques. A direct simulation approach is sufficient.

Several edge cases are important:

  • If grid[0][0] != 0, the answer is immediately false because the knight must start at the top-left cell.
  • Consecutive positions may not form a legal knight move.
  • Small boards such as 3 x 3 often contain invalid tours because a full knight tour is impossible on many small dimensions.
  • Even though all numbers are unique and valid, the ordering itself may still violate knight movement rules.

Approaches

Brute Force Approach

A brute-force strategy would attempt to reconstruct the knight's movement sequence step by step by repeatedly searching the entire board for the next move number.

For example, to find where move 0 occurred, we scan the matrix. Then we scan again for move 1, again for move 2, and so on until n * n - 1.

After locating each consecutive pair of positions, we verify whether the knight can legally move between them.

This approach works because it explicitly checks every move in the sequence. If all consecutive moves are valid and the starting position is correct, then the configuration is valid.

However, this method is inefficient because every lookup requires scanning the whole board. Since there are n^2 moves and each search costs O(n^2), the total complexity becomes O(n^4).

Although the constraints are small enough that this still passes, it is unnecessarily slow.

Optimal Approach

The key observation is that each number uniquely identifies a board position. Instead of repeatedly searching for positions, we can preprocess the board once and directly map each move number to its coordinates.

We create an array where:

position[k] = (row, col)

This allows us to instantly retrieve the coordinates of move k.

Then we simply iterate through all consecutive moves:

0 -> 1
1 -> 2
2 -> 3
...

For each pair, we compute the row difference and column difference. A knight move is valid if:

(abs(dr), abs(dc)) == (2, 1) or (1, 2)

This reduces the overall complexity to O(n^2).

Approach Time Complexity Space Complexity Notes
Brute Force O(n^4) O(1) Repeatedly scans the board to find each move
Optimal O(n^2) O(n^2) Stores positions for direct lookup of each move

Algorithm Walkthrough

  1. First, verify that the knight starts at the required position.

The problem explicitly states that the knight must start at the top-left cell. Therefore, if grid[0][0] != 0, we immediately return False. 2. Create a position mapping array.

We allocate an array of size n * n, where each index represents a move number. The value stored at that index will be the coordinates of that move.

Example:

positions[5] = (0, 3)

means the knight visited cell (0, 3) during move number 5. 3. Traverse the board once to populate the mapping.

For every cell (r, c):

  • Read move_number = grid[r][c]
  • Store:
positions[move_number] = (r, c)

After this step, every move number can be accessed in constant time. 4. Validate every consecutive knight move.

Iterate from 0 to n * n - 2.

For each move k:

  • Retrieve current position (r1, c1)
  • Retrieve next position (r2, c2)

Compute:

dr = abs(r1 - r2)
dc = abs(c1 - c2)

A move is valid only if:

(dr == 2 and dc == 1)
or
(dr == 1 and dc == 2)

If neither condition holds, return False. 5. If all moves are valid, return True.

Why it works

The algorithm works because every move number uniquely identifies exactly one board position. By storing all positions in advance, we can directly verify every consecutive move in the tour.

A knight's tour is valid if and only if:

  • The knight starts at (0, 0)
  • Every consecutive move follows knight movement rules

The algorithm checks both conditions exactly once, so the result is correct.

Python Solution

from typing import List

class Solution:
    def checkValidGrid(self, grid: List[List[int]]) -> bool:
        n = len(grid)

        # The knight must start at the top-left corner
        if grid[0][0] != 0:
            return False

        # positions[k] = (row, col) of move k
        positions = [None] * (n * n)

        for row in range(n):
            for col in range(n):
                move_number = grid[row][col]
                positions[move_number] = (row, col)

        # Check every consecutive move
        for move in range(n * n - 1):
            r1, c1 = positions[move]
            r2, c2 = positions[move + 1]

            row_diff = abs(r1 - r2)
            col_diff = abs(c1 - c2)

            if not (
                (row_diff == 2 and col_diff == 1)
                or
                (row_diff == 1 and col_diff == 2)
            ):
                return False

        return True

The implementation begins by checking whether the starting cell contains 0. If not, the function immediately returns False.

Next, the code creates a positions array where each index corresponds to a move number. By traversing the board once, we store the coordinates of every move.

After preprocessing, the algorithm iterates through all consecutive move numbers. For each pair, it computes the absolute row and column differences. A move is valid only if the differences match one of the two legal knight movement patterns.

If any move fails validation, the function returns False immediately. Otherwise, after all checks succeed, the function returns True.

Go Solution

func checkValidGrid(grid [][]int) bool {
	n := len(grid)

	// The knight must start at the top-left corner
	if grid[0][0] != 0 {
		return false
	}

	// positions[k] = {row, col}
	positions := make([][2]int, n*n)

	for row := 0; row < n; row++ {
		for col := 0; col < n; col++ {
			moveNumber := grid[row][col]
			positions[moveNumber] = [2]int{row, col}
		}
	}

	// Check every consecutive move
	for move := 0; move < n*n-1; move++ {
		r1, c1 := positions[move][0], positions[move][1]
		r2, c2 := positions[move+1][0], positions[move+1][1]

		rowDiff := abs(r1 - r2)
		colDiff := abs(c1 - c2)

		valid :=
			(rowDiff == 2 && colDiff == 1) ||
				(rowDiff == 1 && colDiff == 2)

		if !valid {
			return false
		}
	}

	return true
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

The Go implementation follows the same logic as the Python version. Since Go does not provide a built-in integer abs function for plain integers, we define a small helper function.

The position mapping uses a slice of fixed-size arrays:

[][2]int

This efficiently stores coordinate pairs without additional allocation overhead.

Go slices are initialized with zero values automatically, so no explicit initialization is required beyond make.

Worked Examples

Example 1

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]
]

Step 1: Build Position Mapping

Move Position
0 (0, 0)
1 (2, 1)
2 (4, 2)
3 (3, 0)
4 (1, 1)
5 (0, 3)
... ...

Step 2: Validate Consecutive Moves

From To Row Diff Col Diff Valid
(0,0) (2,1) 2 1 Yes
(2,1) (4,2) 2 1 Yes
(4,2) (3,0) 1 2 Yes
(3,0) (1,1) 2 1 Yes
(1,1) (0,3) 1 2 Yes

All moves satisfy knight movement rules, so the answer is:

true

Example 2

grid =
[
 [0,3,6],
 [5,8,1],
 [2,7,4]
]

Step 1: Build Position Mapping

Move Position
0 (0, 0)
1 (1, 2)
2 (2, 0)
3 (0, 1)
4 (2, 2)
5 (1, 0)
6 (0, 2)
7 (2, 1)
8 (1, 1)

Step 2: Validate Consecutive Moves

From To Row Diff Col Diff Valid
(0,0) (1,2) 1 2 Yes
(1,2) (2,0) 1 2 Yes
(2,0) (0,1) 2 1 Yes
(0,1) (2,2) 2 1 Yes
(2,2) (1,0) 1 2 Yes
(1,0) (0,2) 1 2 Yes
(0,2) (2,1) 2 1 Yes
(2,1) (1,1) 1 0 No

The final move is not a legal knight move, so the answer is:

false

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) We traverse the board once and validate all moves once
Space O(n^2) The position mapping stores every cell coordinate

The board contains n^2 cells. Constructing the position mapping requires visiting each cell exactly once. The validation loop also processes each move exactly once. Therefore, the total running time is linear in the number of cells.

The extra space comes from storing the coordinate mapping for every move number.

Test Cases

from typing import List

class Solution:
    def checkValidGrid(self, grid: List[List[int]]) -> bool:
        n = len(grid)

        if grid[0][0] != 0:
            return False

        positions = [None] * (n * n)

        for r in range(n):
            for c in range(n):
                positions[grid[r][c]] = (r, c)

        for move in range(n * n - 1):
            r1, c1 = positions[move]
            r2, c2 = positions[move + 1]

            dr = abs(r1 - r2)
            dc = abs(c1 - c2)

            if not ((dr == 2 and dc == 1) or (dr == 1 and dc == 2)):
                return False

        return True

sol = Solution()

# Example 1, valid knight tour
assert sol.checkValidGrid([
    [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]
]) == True

# Example 2, invalid final move
assert sol.checkValidGrid([
    [0,3,6],
    [5,8,1],
    [2,7,4]
]) == False

# Invalid because starting position is not 0
assert sol.checkValidGrid([
    [1,0,2],
    [3,4,5],
    [6,7,8]
]) == False

# Invalid because consecutive move is impossible
assert sol.checkValidGrid([
    [0,1,2],
    [3,4,5],
    [6,7,8]
]) == False

# Small valid configuration
assert sol.checkValidGrid([
    [0,7,2],
    [5,4,1],
    [8,3,6]
]) == False  # still invalid due to knight movement

# Larger invalid board with one broken transition
assert sol.checkValidGrid([
    [0,11,16,5,20],
    [17,4,19,10,15],
    [12,1,8,21,6],
    [3,18,23,14,9],
    [24,13,7,2,22]
]) == False
Test Why
Valid 5x5 tour Confirms correct handling of a proper knight tour
Invalid 3x3 example Verifies rejection of illegal move sequences
Starting cell not zero Checks required starting condition
Sequential numbers board Ensures simple invalid movement is detected
Small tricky configuration Tests movement validation on small boards
Larger board with broken transition Verifies failure detection in later moves

Edge Cases

Starting Cell Is Not Zero

One common mistake is forgetting that the knight must start at the top-left corner. Even if all knight moves are otherwise valid, the configuration must still be rejected if grid[0][0] != 0.

The implementation handles this immediately with an early return before any additional processing.

Invalid Move Appears Late in the Sequence

A board may contain many valid knight moves before eventually failing near the end of the sequence. Naive implementations that stop checking too early or incorrectly assume validity after partial verification may produce incorrect answers.

The algorithm explicitly checks every consecutive move from 0 through n * n - 2, ensuring that even the final transition is validated.

Small Board Sizes

Small boards such as 3 x 3 are especially tricky because many configurations appear structured but do not represent valid knight tours.

The implementation does not rely on assumptions about board size or known tour existence properties. Instead, it directly validates the actual move sequence, which guarantees correctness for all valid constraints.