Abstract / Summary

Check if a chessboard arrangement matches a valid knight's tour path where each move follows knight rules and visits every cell once

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 62% (90k+ submissions).

Typical patterns to solve this problem:

• Array
• Breadth First Search
• Depth First Search
• Matrix
• Simulation

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution.checkValidGrid method determines whether a square matrix of integers represents a valid sequence of moves for a knight on a chessboard. The grid must contain every integer from 0 up to size*size-1 exactly once, start with 0 in the upper-left corner, and each successive pair of positions must correspond to a legal knight move (two squares in one direction and one square in the orthogonal direction). The function returns True only when all these constraints are satisfied.

Input Validation

The first logical gate checks that the grid is not empty and that the required starting condition holds. The code accesses grid[0][0] and immediately returns False if the value is not 0. This guards against malformed inputs where the tour does not begin at the prescribed origin.

size = len(grid)

# start in upper-left corner
if grid[0][0] != 0:
    return False

Collecting Moves

The algorithm iterates over every cell, extracting the move number together with its coordinates. Each entry is stored as a three-element tuple (move_number, x, y). By appending directly to a list, the code builds a flat representation of the board that can later be sorted.

moves = []
for y in range(size):
    for x in range(size):
        moves.append((grid[y][x], x, y))

Ordering by Move Number

After the full collection, the list is sorted in ascending order of the move number. Because the first element of each tuple is the move identifier, Python’s default tuple comparison yields the desired ordering without additional key functions. This single sort operation establishes the exact sequence in which the knight is supposed to travel.

moves.sort()  # ordered by move number

Verifying Sequential Numbers

The core loop starts at the second element (index 1) and checks that each move number is exactly one greater than its predecessor. If any gap or duplicate appears, the function aborts with False. This ensures that the grid contains a complete, uninterrupted series from 0 to size*size-1.

for i in range(1, len(moves)):
    # verify move number
    if moves[i][0] != moves[i - 1][0] + 1:
        return False

Validating Knight Geometry

For each consecutive pair, the code computes the absolute differences in the x- and y-coordinates. A legal knight move satisfies two conditions simultaneously: the Manhattan distance (dx + dy) must equal 3, and the product (dx * dy) must equal 2. The first condition guarantees that the total displacement is three squares, while the second confirms that the move is split 2-plus-1 rather than 3-plus-0. If either condition fails, the sequence is invalid.

    # 2 step into one direction and 1 in another
    dx = abs(moves[i][1] - moves[i - 1][1])
    dy = abs(moves[i][2] - moves[i - 1][2])
    if dx + dy != 3 or dx * dy != 2:
        return False

Final Result

If the loop completes without triggering any early return, every cell has been visited in the correct order and each transition respects the knight’s movement rules. The method then returns True, signalling a valid tour.

return True

Edge Cases Handled

The implementation explicitly addresses several boundary conditions. An empty grid would cause size to be zero; attempting to read grid[0][0] would raise an exception, but the problem constraints guarantee a non-empty square, so the check for the starting cell suffices. Grids where the initial cell is not 0 are rejected immediately, covering the case where the tour does not begin at the required corner. Gaps in the numbering sequence, duplicate numbers, or out-of-range values are caught by the sequential number verification step. Finally, any move that does not conform to the 2-plus-1 pattern-whether because the knight jumps too far, moves straight, or stays in place-is detected by the geometric test.

Performance Optimizations

The algorithm achieves efficiency through a few deliberate choices. By flattening the board into a list of tuples and sorting once, it avoids repeated lookups or auxiliary data structures such as hash maps. The sorting step runs in O(n log n) time where n is the number of cells, but it is the only non-linear operation; subsequent checks are linear scans. The use of simple arithmetic (abs, addition, multiplication) for the knight-move validation eliminates the need for more complex conditional branches or pre-computed move tables. Early returns on the first failure prevent unnecessary processing of the remainder of the grid, which is especially beneficial for large boards with early violations.

Imagine a giant square board filled with many little numbered squares. This game is all about following a special knight piece that jumps around on the board. The goal is to see if the knight has made a perfect trip where every number from zero to the end is touched in the right order.

First, the code looks at the very top corner of the board to make sure the number zero is sitting right there. If the zero is not in the corner, then the game did not start correctly. After that, the code gathers up all the numbers and where they are sitting on the board. It sorts them into a neat line so that zero is first, then one is next, then two, and so on.

Now it is time to check the jumps. The code looks at each pair of numbers in the line one by one. It confirms that the next number is exactly one higher than the one before it. If someone tried to skip a number, the game would stop.

Finally, the code checks the shape of the jumps. A knight piece moves in a very specific L-shape. It has to move two squares in one direction and one square in the other. The code calculates how far across and how far up or down the knight traveled between each jump. If those numbers do not add up to the special L-shape movement, it means the knight took a silly path that is not allowed. If all the steps and jumps are perfect until the end, then the move path is valid.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster		Java	C++		Python	TS
	WalkCCC		Java	C++		Python
	leetcode.ca		Java	C++	Go	Python	TS
	Progiez		Java	C++		Python
github	charles-wangkai		Java
	fsq			C++
	JoshCrozier	JS
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality