Problem

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.

Examples

Example 1:

1
2
3

Input: m = 1, n = 1, r = 0, c = 0
Output: [[0]]
Explanation: There is only 1 cell and the knight is initially on it so there is only a 0 inside the 1x1 grid.

Example 2:

1
2
3
4

Input: m = 3, n = 4, r = 0, c = 0
Output: [[0,3,6,9],[11,8,1,4],[2,5,10,7]]
Explanation: By the following order of movements we can visit the entire board.
(0,0)->(1,2)->(2,0)->(0,1)->(1,3)->(2,1)->(0,2)->(2,3)->(1,1)->(0,3)->(2,2)->(1,0)

Constraints:

  • 1 <= m, n <= 5
  • 0 <= r <= m - 1
  • 0 <= c <= n - 1
  • The inputs will be generated such that there exists at least one possible order of movements with the given condition

Solution

Method 1 - Backtracking

We use backtracking to try all possible knight moves, filling the board in the order of the knight’s tour. Since the board is small (max 5x5), this is efficient enough.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <vector>
using namespace std;
vector<vector<int>> tour;
bool dfs(int m, int n, int r, int c, int step, vector<vector<int>>& board, vector<pair<int,int>>& moves) {
    if (step == m * n) return true;
    for (auto [dr, dc] : moves) {
        int nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] == -1) {
            board[nr][nc] = step;
            if (dfs(m, n, nr, nc, step + 1, board, moves)) return true;
            board[nr][nc] = -1;
        }
    }
    return false;
}
vector<vector<int>> knightsTour(int m, int n, int r, int c) {
    vector<vector<int>> board(m, vector<int>(n, -1));
    vector<pair<int,int>> moves = {{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};
    board[r][c] = 0;
    dfs(m, n, r, c, 1, board, moves);
    return board;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import java.util.*;
class Solution {
    private final int[][] dirs = {{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};
    public int[][] knightsTour(int m, int n, int r, int c) {
        int[][] board = new int[m][n];
        for (int[] row : board) Arrays.fill(row, -1);
        board[r][c] = 0;
        dfs(m, n, r, c, 1, board);
        return board;
    }
    private boolean dfs(int m, int n, int r, int c, int step, int[][] board) {
        if (step == m * n) return true;
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] == -1) {
                board[nr][nc] = step;
                if (dfs(m, n, nr, nc, step + 1, board)) return true;
                board[nr][nc] = -1;
            }
        }
        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

from typing import List
def knightsTour(m: int, n: int, r: int, c: int) -> List[List[int]]:
    board = [[-1]*n for _ in range(m)]
    moves = [(2,1),(1,2),(-1,2),(-2,1),(-2,-1),(-1,-2),(1,-2),(2,-1)]
    def dfs(x, y, step):
        if step == m*n:
            return True
        for dx, dy in moves:
            nx, ny = x+dx, y+dy
            if 0<=nx<m and 0<=ny<n and board[nx][ny]==-1:
                board[nx][ny] = step
                if dfs(nx, ny, step+1):
                    return True
                board[nx][ny] = -1
        return False
    board[r][c] = 0
    dfs(r, c, 1)
    return board
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

pub fn knights_tour(m: i32, n: i32, r: i32, c: i32) -> Vec<Vec<i32>> {
    let (m, n) = (m as usize, n as usize);
    let mut board = vec![vec![-1; n]; m];
    let moves = [(2,1),(1,2),(-1,2),(-2,1),(-2,-1),(-1,-2),(1,-2),(2,-1)];
    fn dfs(m: usize, n: usize, x: usize, y: usize, step: i32, board: &mut Vec<Vec<i32>>, moves: &[(i32,i32)]) -> bool {
        if step == (m * n) as i32 { return true; }
        for &(dx, dy) in moves {
            let nx = x as i32 + dx;
            let ny = y as i32 + dy;
            if nx >= 0 && nx < m as i32 && ny >= 0 && ny < n as i32 && board[nx as usize][ny as usize] == -1 {
                board[nx as usize][ny as usize] = step;
                if dfs(m, n, nx as usize, ny as usize, step+1, board, moves) { return true; }
                board[nx as usize][ny as usize] = -1;
            }
        }
        false
    }
    board[r as usize][c as usize] = 0;
    dfs(m, n, r as usize, c as usize, 1, &mut board, &moves);
    board
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

function knightsTour(m: number, n: number, r: number, c: number): number[][] {
    const board = Array.from({length: m}, () => Array(n).fill(-1));
    const moves = [[2,1],[1,2],[-1,2],[-2,1],[-2,-1],[-1,-2],[1,-2],[2,-1]];
    function dfs(x: number, y: number, step: number): boolean {
        if (step === m * n) return true;
        for (const [dx, dy] of moves) {
            const nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && board[nx][ny] === -1) {
                board[nx][ny] = step;
                if (dfs(nx, ny, step + 1)) return true;
                board[nx][ny] = -1;
            }
        }
        return false;
    }
    board[r][c] = 0;
    dfs(r, c, 1);
    return board;
}

Complexity

  • ⏰ Time complexity: O((m*n)!) in the worst case (but feasible for m,n ≤ 5).
  • 🧺 Space complexity: O(m*n) for the board and recursion stack.