The knights tour

Given two positive integers m and n which are the height and width of a 0-indexed 2D-array board, a pair of positive integers (r, c) which is the starting position of the knight on the board.

Your task is to find an order of movements for the knight, in a manner that every cell of the board gets visited exactly once (the starting cell is considered visited and you shouldn't visit it again).

Return the array board in which the cells' values show the order of visiting the cell starting from 0 (the initial place of the knight).

Note that a knight can move from cell (r1, c1) to cell (r2, c2) if 0 <= r2 <= m - 1 and 0 <= c2 <= n - 1 and min(abs(r1 - r2), abs(c1 - c2)) = 1 and max(abs(r1 - r2), abs(c1 - c2)) = 2.

class Solution {
    private int[][] g;
    private int m;
    private int n;
    private boolean ok;

    public int[][] tourOfKnight(int m, int n, int r, int c) {
        this.m = m;
        this.n = n;
        this.g = new int[m][n];
        for (var row : g) {
            Arrays.fill(row, -1);
        }
        g[r][c] = 0;
        dfs(r, c);
        return g;
    }

    private void dfs(int i, int j) {
        if (g[i][j] == m * n - 1) {
            ok = true;
            return;
        }
        int[] dirs = {-2, -1, 2, 1, -2, 1, 2, -1, -2};
        for (int k = 0; k < 8; ++k) {
            int x = i + dirs[k], y = j + dirs[k + 1];
            if (x >= 0 && x < m && y >= 0 && y < n && g[x][y] == -1) {
                g[x][y] = g[i][j] + 1;
                dfs(x, y);
                if (ok) {
                    return;
                }
                g[x][y] = -1;
            }
        }
    }
}

class Solution:
  def tourOfKnight(self, m: int, n: int, r: int, c: int) -> list[list[int]]:
    dirs = ((1, 2), (2, 1), (2, -1), (1, -2),
            (-1, -2), (-2, -1), (-2, 1), (-1, 2))
    ans = [[-1] * n for _ in range(m)]

    def dfs(i: int, j: int, step: int) -> bool:
      if step == m * n:
        return True
      if i < 0 or i >= m or j < 0 or j >= n:
        return False
      if ans[i][j] != -1:
        return False
      ans[i][j] = step
      for dx, dy in dirs:
        if dfs(i + dx, j + dy, step + 1):
          return True
      ans[i][j] = -1
      return False

    dfs(r, c, 0)
    return ans

The Knight's Tour problem is a classic in algorithms and combinatorics, (also leetcode 2664) where the challenge is to find a sequence of moves for a knight on a chessboard that visits every square exactly once. The knight moves in an L-shape: two squares in one direction and then one square perpendicular to it, or vice versa. Solving this problem efficiently usually requires backtracking or a heuristic such as Warnsdorff's rule, which suggests moving the knight to the square that has the fewest onward moves. This minimizes the risk of getting stuck before visiting all the cells.

The goal in this problem is to populate the board with the order in which the knight visits each square, starting from the initial position. You’ll need to recursively explore all possible moves, marking each cell as visited in a specific order, while ensuring that no cell is revisited. If a move leads to a dead-end, the algorithm should backtrack and try different moves until all cells are covered. The complexity increases with the size of the board, making optimization techniques crucial for larger grids.

Related Problems