# Check Knight Tour Configuration
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/check-knight-tour-configuration)
Canonical: https://scaleengineer.com/dsa/problems/check-knight-tour-configuration
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Matrix
---
## Problem
There is a knight on an `n x n` chessboard. In a valid configuration, the knight starts **at the top-left cell** of the board and visits every cell on the board **exactly once**.

You are given an `n x n` integer matrix `grid` consisting of distinct integers from the range `[0, n * n - 1]` where `grid[row][col]` indicates that the cell `(row, col)` is the `grid[row][col]th` cell that the knight visited. The moves are **0-indexed**.

Return `true` _if_ `grid` _represents a valid configuration of the knight's movements or_ `false` _otherwise_.

**Note** that a valid knight move consists of moving two squares vertically and one square horizontally, or two squares horizontally and one square vertically. The figure below illustrates all the possible eight moves of a knight from some cell.

![](https://assets.glich.co/dsa/check-knight-tour-configuration/image0.png) 

**Example 1:**

![](https://assets.glich.co/dsa/check-knight-tour-configuration/image1.png) 

**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
**Explanation:** The above diagram represents the grid. It can be shown that it is a valid configuration.

**Example 2:**

![](https://assets.glich.co/dsa/check-knight-tour-configuration/image2.png) 

**Input:** grid = [[0,3,6],[5,8,1],[2,7,4]]
**Output:** false
**Explanation:** The above diagram represents the grid. The 8th move of the knight is not valid considering its position after the 7th move.

**Constraints:**

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

# Approaches
## Brute-Force Simulation by Path Traversal
This method simulates the knight's journey step-by-step. Starting from move 0 at `(0,0)`, it iteratively finds the location of the next move (`1`, `2`, `3`, ...) by scanning the entire grid. At each step, it verifies if the jump from the previous location to the current one is a valid knight's move.
**Time:** O(n^4). The outer loop runs `n*n - 1` times. For each iteration, the inner nested loops scan the grid, taking `O(n^2)` time in the worst case. This results in a total time complexity of `O(n^2 * n^2) = O(n^4)`. · **Space:** O(1). Only a few variables are used to store the current position and loop counters.
**Pros:** Simple logic, easy to follow.; Requires no extra space, i.e., `O(1)` space complexity.
**Cons:** Inefficient time complexity of `O(n^4)` because for each of the `n*n` moves, it scans the entire `n*n` grid.; Will be very slow for larger grid sizes, though it passes for the given constraints.
### Explanation
First, it checks the starting condition: `grid[0][0]` must be `0`. If not, the tour is invalid.
It initializes the knight's current position to `(0, 0)`.
The algorithm then enters a loop that iterates from move `k = 1` to `n*n - 1`.
Inside the loop, it searches the entire `n x n` grid to find the coordinates `(nextR, nextC)` of the cell containing the value `k`.
Once found, it calculates the difference in rows and columns between the current position and the next position: `dr = abs(currR - nextR)` and `dc = abs(currC - nextC)`.
It validates the move using the knight's move rule: `(dr == 1 && dc == 2) || (dr == 2 && dc == 1)`.
If the move is invalid, the function returns `false`.
If the move is valid, it updates the current position to `(nextR, nextC)` and continues to the next iteration.
If the loop completes without returning `false`, it means all `n*n - 1` moves were valid, so the function returns `true`.
```java
class Solution {
    public boolean checkValidGrid(int[][] grid) {
        if (grid[0][0] != 0) {
            return false;
        }
        int n = grid.length;
        int currR = 0;
        int currC = 0;

        for (int k = 1; k < n * n; k++) {
            boolean foundNext = false;
            // Search for the cell with value k
            for (int r = 0; r < n; r++) {
                for (int c = 0; c < n; c++) {
                    if (grid[r][c] == k) {
                        int dr = Math.abs(currR - r);
                        int dc = Math.abs(currC - c);
                        if (!((dr == 2 && dc == 1) || (dr == 1 && dc == 2))) {
                            return false; // Invalid move
                        }
                        // Update current position for the next move
                        currR = r;
                        currC = c;
                        foundNext = true;
                        break;
                    }
                }
                if (foundNext) {
                    break;
                }
            }
        }
        return true;
    }
}
```
### Algorithm
- 1. Check if `grid[0][0]` is `0`. If not, return `false`.
- 2. Initialize the current position `(currR, currC)` to `(0, 0)`.
- 3. Loop through move numbers `k` from `1` to `n*n - 1`.
- 4. Inside the loop, perform a nested loop over the grid to find the cell `(nextR, nextC)` where `grid[nextR][nextC] == k`.
- 5. Validate the move from `(currR, currC)` to `(nextR, nextC)`. If invalid, return `false`.
- 6. Update `currR = nextR` and `currC = nextC`.
- 7. If the loop completes, return `true`.

## Optimized Simulation with Position Pre-computation
This approach significantly improves performance by avoiding repeated searches. It first creates a lookup table (an array) to store the coordinates of every move number. After this one-time setup, it can retrieve the position of any move in constant time. The algorithm then iterates through the moves sequentially, using the lookup table to get the current and next positions, and verifies each move's validity.
**Time:** O(n^2). Populating the `positions` array by iterating through the grid takes `O(n^2)`. Verifying the `n*n - 1` moves using the pre-computed positions takes another `O(n^2)`. The total complexity is dominated by these steps, resulting in `O(n^2)`. · **Space:** O(n^2). An auxiliary array of size `n*n` is used to store the coordinates of each move number.
**Pros:** Highly efficient with a time complexity of `O(n^2)`.; The logic is straightforward: build a map, then check the path.
**Cons:** Requires extra space of `O(n^2)` for the positions lookup table.
### Explanation
The algorithm begins with the mandatory check: `grid[0][0]` must be `0`.
It then creates an auxiliary 2D array, `positions`, of size `(n*n) x 2`. This array will act as a map where `positions[k]` stores the `(row, col)` coordinates of the cell with value `k`.
To populate this `positions` array, it iterates through the input `grid` once. For each cell `(r, c)`, it performs the assignment: `positions[grid[r][c]] = {r, c}`. This entire pre-computation step takes `O(n^2)` time.
With the `positions` map built, the algorithm verifies the tour. It loops from `k = 0` to `n*n - 2`.
In each iteration, it fetches the coordinates for the current move `k` and the next move `k+1` directly from the `positions` array in `O(1)` time.
- `(r1, c1) = positions[k]`
- `(r2, c2) = positions[k+1]`
It then checks if the move from `(r1, c1)` to `(r2, c2)` is a valid knight's move by checking if `abs(r1 - r2) * abs(c1 - c2) == 2`.
If an invalid move is detected, it returns `false`.
If the loop finishes, all moves are valid, and it returns `true`.
```java
class Solution {
    public boolean checkValidGrid(int[][] grid) {
        if (grid[0][0] != 0) {
            return false;
        }

        int n = grid.length;
        int[][] positions = new int[n * n][2];
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                positions[grid[r][c]][0] = r;
                positions[grid[r][c]][1] = c;
            }
        }

        for (int i = 0; i < n * n - 1; i++) {
            int r1 = positions[i][0];
            int c1 = positions[i][1];
            int r2 = positions[i + 1][0];
            int c2 = positions[i + 1][1];

            int dr = Math.abs(r1 - r2);
            int dc = Math.abs(c1 - c2);

            if (!((dr == 2 && dc == 1) || (dr == 1 && dc == 2))) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
- 1. Check if `grid[0][0]` is `0`. If not, return `false`.
- 2. Create a `positions` array of size `n*n` to store `(row, col)` coordinates.
- 3. Iterate through the `grid` to populate the `positions` array: `positions[grid[r][c]] = {r, c}`.
- 4. Loop through move numbers `i` from `0` to `n*n - 2`.
- 5. Get current position `(r1, c1)` from `positions[i]` and next position `(r2, c2)` from `positions[i+1]`.
- 6. Validate the move from `(r1, c1)` to `(r2, c2)`. If invalid, return `false`.
- 7. If the loop completes, return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean checkValidGrid(int[][] grid) {
    if (grid[0][0] != 0) {
      return false;
    }
    int n = grid.length;
    int[][] pos = new int[n * n][2];
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        pos[grid[i][j]] = new int[]{i, j};
      }
    }
    for (int i = 1; i < n * n; ++i) {
      int[] p1 = pos[i - 1];
      int[] p2 = pos[i];
      int dx = Math.abs(p1[0] - p2[0]);
      int dy = Math.abs(p1[1] - p2[1]);
      boolean ok = (dx == 1 && dy == 2) || (dx == 2 && dy == 1);
      if (!ok) {
        return false;
      }
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool checkValidGrid(vector<vector<int>> &grid) {
    if (grid[0][0] != 0) {
      return false;
    }
    int n = grid.size();
    vector<pair<int, int>> pos(n * n);
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        pos[grid[i][j]] = {i, j};
      }
    }
    for (int i = 1; i < n * n; ++i) {
      auto [x1, y1] = pos[i - 1];
      auto [x2, y2] = pos[i];
      int dx = abs(x1 - x2);
      int dy = abs(y1 - y2);
      bool ok = (dx == 1 && dy == 2) || (dx == 2 && dy == 1);
      if (!ok) {
        return false;
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def checkValidGrid(self, grid: List[List[int]]) -> bool: if grid[0][0]: return False n = len(grid) pos = [None] * (n * n) for i in range(n): for j in range(n): pos[grid[i][j]] = (i, j) for (x1, y1), (x2, y2) in pairwise(pos): dx, dy = abs(x1 - x2), abs(y1 - y2) ok = (dx == 1 and dy == 2) or (dx == 2 and dy == 1) if not ok: return False return True

```