Knight’s Tour Configuration Solution in Java

Navigate to Other Solutions

Problem Description

The Knight’s Tour problem is a classic puzzle where we determine if a knight can visit every square on a chessboard exactly once, starting from the top-left corner (0,0). Imagine a knight at a party, needing to greet every guest (square) without missing anyone. If it misses a guest, it’s like forgetting your best friend’s birthday—awkward and unacceptable!

Code Solution


class Solution {
  public boolean checkValidGrid(int[][] grid) {
    if (grid[0][0] != 0)
      return false;

    final int n = grid.length;
    int i = 0;
    int j = 0;

    for (int target = 1; target < n * n; ++target) {
      Pair pair = nextGrid(grid, i, j, target);
      final int x = pair.getKey();
      final int y = pair.getValue();
      if (x == -1 && y == -1)
        return false;
      i = x;
      j = y;
    }

    return true;
  }

  private static final int[][] dirs = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1},
                                       {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};

  private Pair nextGrid(int[][] grid, int i, int j, int target) {
    final int n = grid.length;
    for (int[] dir : dirs) {
      final int x = i + dir[0];
      final int y = j + dir[1];
      if (x < 0 || x >= n || y < 0 || y >= n)
        continue;
      if (grid[x][y] == target)
        return new Pair<>(x, y);
    }
    return new Pair<>(-1, -1);
  }
}

Approach Explanation

The code checks if the knight starts at the top-left corner of the grid. It iterates through the expected positions of the knight (from 1 to n*n) and checks if it can reach each target position using the knight’s unique movement pattern. If it can’t reach a target, it returns false. If it successfully visits all squares, it returns true.

Time and Space Complexity

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

Real-World Example

Think of the knight as a delivery person trying to deliver packages to every house in a neighborhood without retracing their steps. If they miss a house, they have to go back and start over, which is a hassle! The knight must navigate the chessboard efficiently, just like our delivery person must plan their route to avoid traffic jams and missed deliveries.