The Knight’s Tour Solution in Java

Explore More Solutions:

Ah, the Knight’s Tour problem! It’s like trying to convince your cat to take a bath—challenging, perplexing, and often leads to chaos. Imagine a knight on a chessboard, galloping around like it’s a Saturday night out, trying to visit every square exactly once. Sounds easy, right? Well, it’s not! This problem is a classic example of backtracking, where our knight must navigate the board without stepping on the same square twice.

So, let’s dive into the code solution that will help our knight achieve this seemingly impossible feat!


class Solution {
  public int[][] tourOfKnight(int m, int n, int r, int c) {
    int[][] ans = new int[m][n];
    Arrays.stream(ans).forEach(A -> Arrays.fill(A, -1));
    dfs(m, n, r, c, 0, ans);
    return ans;
  }

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

  private boolean dfs(int m, int n, int i, int j, int step, int[][] ans) {
    if (step == m * n)
      return true;
    if (i < 0 || i >= m || j < 0 || j >= n)
      return false;
    if (ans[i][j] != -1)
      return false;
    ans[i][j] = step;
    for (int[] dir : dirs)
      if (dfs(m, n, i + dir[0], j + dir[1], step + 1, ans))
        return true;
    ans[i][j] = -1;
    return false;
  }
}

Code Explanation

The code above implements a depth-first search (DFS) algorithm to solve the Knight’s Tour problem. The knight starts at a given position (r, c) on an m x n chessboard and attempts to visit every square exactly once. The tourOfKnight method initializes the board and calls the dfs method to explore possible moves.

Approach

Initialization: Create a 2D array to store the knight’s path, initializing all squares to -1 (indicating unvisited).
DFS Exploration: The knight can move in eight possible directions. For each valid move, the algorithm recursively attempts to visit the next square.
Backtracking: If a move leads to a dead end (either out of bounds or revisiting a square), the algorithm backtracks by resetting the square to -1.

Time and Space Complexity

Time Complexity: O(8^(m*n)), where m and n are the dimensions of the chessboard. This is because the knight can make up to 8 moves from each square.

Space Complexity: O(m*n) for the recursion stack and the board storage.

Real-World Example

Imagine you’re a knight in a medieval chess tournament, and your goal is to impress the crowd by visiting every square on the board without stepping on the same square twice. You might think, “How hard can it be?” But as you start galloping around, you realize that some paths lead to nowhere, and you end up retracing your steps like a lost tourist in a foreign city. The Knight’s Tour problem captures this essence of exploration and backtracking perfectly!