Check Knight Tour Configuration — Medium Problem & Solution

An n × n chessboard is given as a grid where grid[row][col] is the step at which a knight visited that cell, numbered 0 … n·n - 1.

Difficulty: Medium
Topics: Arrays, Matrix, Simulation, Depth-First Search
Asked at: Amazon, Google, Oracle
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

An n × n chessboard is given as a grid where grid[row][col] is the step at which a knight visited that cell, numbered 0 … n·n - 1.

Return true if the grid really is a valid knight's tour: the knight starts at the top-left cell and every consecutive pair of steps is one legal knight move (two squares one way and one square the other).

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

Example 2

Input: grid = [[0,3,6],[5,8,1],[2,7,4]]
Output: false
Explanation: Step 0 to step 1 is not a knight move.

Example 3

Input: grid = [[2,0],[1,3]]
Output: false
Explanation: The tour must start at the top-left cell.

Constraints

n == grid.length == grid[i].length
3 <= n <= 7
0 <= grid[row][col] < n * n
All values in grid are unique

How to solve Check Knight Tour Configuration

The grid maps cell → step; invert it to step → cell, which turns the check into a simple walk over n·n - 1 consecutive pairs.

Approach

Reject immediately unless grid[0][0] == 0.
Fill pos[grid[i][j]] = i * n + j in one scan.
For k from 1 upward, compare pos[k] with pos[k-1].
The hop is legal when {|dr|, |dc|} == {1, 2}; otherwise return false.

Why it works

Because the values are distinct and inside [0, n·n), the inversion is a bijection and the tour is fully described by the sequence pos[0], pos[1], …. Checking each adjacent pair is therefore necessary and sufficient — nothing about the tour is left unverified once the start cell and every hop have been confirmed.

Complexity

Time — O(n²)
Space — O(n²)

Pitfalls

Forgetting the start check accepts tours that begin elsewhere.
Only the two {1,2} shapes are legal; |dr| == |dc| never is.
Storing the cell as i * n + j keeps the inversion a flat array.

Reference solution

Python

from typing import List

def checkValidGrid(grid: List[List[int]]) -> bool:
    n = len(grid)
    if grid[0][0] != 0:
        return False
    pos = [0] * (n * n)
    for i in range(n):
        for j in range(n):
            pos[grid[i][j]] = (i, j)
    for k in range(1, n * n):
        dr = abs(pos[k][0] - pos[k - 1][0])
        dc = abs(pos[k][1] - pos[k - 1][1])
        if not ((dr == 1 and dc == 2) or (dr == 2 and dc == 1)):
            return False
    return True

JavaScript

var checkValidGrid = function(grid) {
    var n = grid.length, i, j;
    if (grid[0][0] !== 0) return false;
    var pos = new Array(n * n);
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) pos[grid[i][j]] = i * n + j;
    }
    for (var k = 1; k < n * n; k++) {
        var dr = Math.abs(Math.floor(pos[k] / n) - Math.floor(pos[k - 1] / n));
        var dc = Math.abs((pos[k] % n) - (pos[k - 1] % n));
        if (!((dr === 1 && dc === 2) || (dr === 2 && dc === 1))) return false;
    }
    return true;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue