Check Knight Tour Configuration

What does it ask?

You're given an n×n grid and a 2D array grid where grid[i][j] is the step number at which a knight visits cell (i, j).

Return true if the sequence represents a valid knight's tour: every cell is visited exactly once, the knight starts at cell labelled 0, and each consecutive pair of moves is a valid L-shaped knight jump.

The algorithm

// Build position lookup: step → (row,col)
pos[0..n²-1] = build from grid

// Verify step 0 is at (0,0)
if pos[0] ≠ (0, 0): return false

// Validate each consecutive jump
for k = 1 to n²−1:
  dr = |pos[k].r − pos[k−1].r|
  dc = |pos[k].c − pos[k−1].c|
  if {dr,dc} ≠ {1,2}: return false
return true

💡 Key insight: A knight's L-shape means the absolute row and column deltas between consecutive positions must always be {1, 2} (one is 1, the other is 2 — in either order). So the check is just: |Δrow| + |Δcol| = 3 AND |Δrow| ≠ |Δcol|. That's it — no BFS, no visited set at runtime. Two numbers, one condition, per step.

Knight move patterns

All 8 valid L-shaped jumps from any cell

(−2, −1)
(−2, +1)
(−1, −2)
(−1, +2)
(+1, −2)
(+1, +2)
(+2, −1)
(+2, +1)

Complexity

Time

O(n²)

One pass to build the pos array, one pass to verify n²−1 moves.

Space

O(n²)

The pos lookup array stores one (row,col) pair per cell.

Check condition

{1,2}

|Δrow| and |Δcol| must be exactly {1, 2} in some order — no other sets pass.

Examples & edge cases

Live animation — Knight Tour Validator

Unvisited cell Board (dark/light) Visited path Current knight ♞ Valid move ✓ Invalid move ✗

⏸ Waiting to start

Step sequence (step# → position)

Checking move

From (step k−1)

—

♞

To (step k)

—

Move validation

|Δrow| = —

|Δcol| = —

Pending…

Step

of —

Valid moves

Invalid moves

Result

—

Step — of —

Select an example above and press Play to begin.

✓ true — Valid Tour! ✗ false — Invalid Tour

Speed Medium

Step-by-step verification table

Check #	Step k−1	Step k	From (r,c)	To (r,c)	\|Δrow\|	\|Δcol\|	Valid knight?

C++ implementation

check_knight_tour.cpp · LeetCode 2596

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool checkValidGrid(vector<vector<int>>& grid) {
        int n = grid.size();
        int total = n * n;

        // Step 1: build position lookup — step number → (row, col)
        vector<pair<int,int>> pos(total);
        for (int r = 0; r < n; r++)
            for (int c = 0; c < n; c++)
                pos[grid[r][c]] = {r, c};

        // Step 2: knight must start at (0,0)
        if (pos[0] != make_pair(0, 0))
            return false;

        // Step 3: each consecutive pair must be a valid knight jump
        for (int k = 1; k < total; k++) {
            int dr = abs(pos[k].first  - pos[k-1].first);
            int dc = abs(pos[k].second - pos[k-1].second);

            // Valid iff deltas are {1, 2} in some order
            if (!((dr == 1 && dc == 2) || (dr == 2 && dc == 1)))
                return false;
        }

        return true;
    }
};

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars