Check Knight Tour Configuration Solution in C++

Navigate to Other Solutions

Problem Description

So, you think you can just plop a knight on a chessboard and expect it to dance around like it’s auditioning for “Dancing with the Stars”? Well, think again! The Check Knight Tour Configuration problem is here to remind you that even knights have rules. The task is to determine if a given configuration of a knight’s moves on an n x n chessboard is valid.

Imagine your knight is trying to impress its friends by showing off its moves, but it can only jump in an “L” shape. If it starts at the top-left corner (0,0) and ends up at every other square exactly once, then it’s a successful knight! If not, well, it’s just a knight who can’t follow directions—much like that friend who always gets lost on the way to the party.

Code Solution

Here’s the knight’s code to prove it can follow the rules:


class Solution {
 public:
  bool checkValidGrid(vector>& grid) {
    if (grid[0][0] != 0)
      return false;

    const int n = grid.size();
    int i = 0;
    int j = 0;

    for (int target = 1; target < n * n; ++target) {
      const auto [x, y] = nextGrid(grid, i, j, target);
      if (x == -1 && y == -1)
        return false;
      // Move (x, y) to (i, j).
      i = x;
      j = y;
    }

    return true;
  }

 private:
  static constexpr int dirs[8][2] = {{-2, 1}, {-1, 2}, {1, 2},   {2, 1},
                                     {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};

  // Returns (x, y), where grid[x][y] == target if (i, j) can reach target.
  pair nextGrid(const vector>& grid, int i, int j,
                          int target) {
    const int n = grid.size();
    for (const auto& [dx, dy] : dirs) {
      const int x = i + dx;
      const int y = j + dy;
      if (x < 0 || x >= n || y < 0 || y >= n)
        continue;
      if (grid[x][y] == target)
        return {x, y};
    }
    return {-1, -1};
  }
};

Approach

The code starts by checking if the knight is at the starting position (0,0). Then, it iterates through the expected positions of the knight (from 1 to n*n). For each target position, it checks if the knight can jump to that position using predefined knight moves. If it can’t reach the target, it returns false. If it successfully visits all positions, it returns true.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n^2)
Space Complexity	O(1)

Real-World Example

Imagine a knight trying to navigate through a crowded party, where each guest represents a square on the chessboard. The knight can only jump over people in an “L” shape. If it can visit every guest exactly once without getting lost or stuck, it’s a successful knight! If it ends up in a corner, well, it’s just another knight who couldn’t handle the social scene.