The knights tour

Array Backtracking Matrix

72.7% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn tour_of_knight(m: i32, n: i32, r: i32, c: i32) -> Vec<Vec<i32>> {
    let m = m as usize;
    let n = n as usize;
    let mut board = vec![vec![-1i32; n]; m];
    board[r as usize][c as usize] = 0;
    let moves: [(i32, i32); 8] = [(-2,-1),(-2,1),(-1,-2),(-1,2),(1,-2),(1,2),(2,-1),(2,1)];
    fn degree(board: &[Vec<i32>], r: usize, c: usize, m: usize, n: usize, mv: &[(i32,i32);8]) -> i32 {
      let mut cnt = 0;
      for &(dr, dc) in mv {
        let nr = r as i32 + dr;
        let nc = c as i32 + dc;
        if nr >= 0 && nr < m as i32 && nc >= 0 && nc < n as i32 && board[nr as usize][nc as usize] == -1 {
          cnt += 1;
        }
      }
      cnt
    }
    fn solve(board: &mut Vec<Vec<i32>>, r: usize, c: usize, step: i32, total: i32, m: usize, n: usize, mv: &[(i32,i32);8]) -> bool {
      if step == total { return true; }
      let mut nexts: Vec<(i32, usize, usize)> = Vec::new();
      for &(dr, dc) in mv.iter() {
        let nr = r as i32 + dr;
        let nc = c as i32 + dc;
        if nr >= 0 && nr < m as i32 && nc >= 0 && nc < n as i32 && board[nr as usize][nc as usize] == -1 {
          nexts.push((degree(board, nr as usize, nc as usize, m, n, mv), nr as usize, nc as usize));
        }
      }
      nexts.sort();
      for (_, nr, nc) in nexts {
        board[nr][nc] = step;
        if solve(board, nr, nc, step + 1, total, m, n, mv) { return true; }
        board[nr][nc] = -1;
      }
      false
    }
    solve(&mut board, r as usize, c as usize, 1, (m * n) as i32, m, n, &moves);
    board
  }
}