Check Knight Tour Configuration

Check Knight Tour Configuration

What is this problem about?

In chess, a "Knight's Tour" is a sequence of moves where a knight visits every square on an $n imes n$ board exactly once. You are given an $n imes n$ grid where each cell contains a number from 0 to $n^2-1$, representing the order in which the knight visited that square. You need to determine if the given grid represents a valid knight's tour, starting from $(0, 0)$.

Why is this asked in interviews?

Microsoft, Meta, and Google use this to test your ability to perform Simulation and Matrix traversal. It’s a test of whether you can correctly implement the move rules of a specific game (the L-shape move of a knight) and verify a sequence of events. It evaluation your attention to grid boundaries and movement logic.

Algorithmic pattern used

The pattern is Simulation. You start at the cell containing 0 (which must be $(0, 0)$). Then, you find the location of the next number (1, 2, 3...) and check if the move from the current cell to the next cell is a valid knight's move. A knight move is valid if the absolute difference in rows is 1 and columns is 2, or vice versa ($|r1-r2| imes |c1-c2| = 2$).

Example explanation

$3 imes 3$ Grid: 0 3 6 5 8 1 2 7 4

1. Start at 0 (0,0).
2. Find 1 at (1,2). Is (0,0) to (1,2) a knight move? Yes ($1^2 + 2^2$ logic).
3. Find 2 at (2,0). Is (1,2) to (2,0) a knight move? Yes.
4. Continue until $n^2-1$. If all moves are valid, the configuration is valid.

Common mistakes candidates make

A common error is not checking if the tour starts at $(0, 0)$. Another is inefficiently searching for the next number in every step ($O(N^2)$ search for each of $N^2$ numbers results in $O(N^4)$). Instead, you should pre-store the coordinates of each number in an array to make the checks $O(1)$ each, leading to a total time of $O(N^2)$.

Interview preparation tip

For simulation problems where you need to visit elements in a specific order, always consider "preprocessing" the locations. Storing pos[value] = (row, col) turns a search problem into a simple iteration, which is much more efficient.