Skip to Content

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.

Posted by grwgreg 14 days ago

Related Problems

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

Every adjacent pair of words differs by a single letter.

Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.

sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return all the shortest transformation sequences from beginWord to endWord, or an empty list if no such sequence exists. Each sequence should be returned as a list of the words [beginWord, s1, s2, ..., sk].

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.