The Knight's Tour - Practice Coding Problems

The Knight's Tour - Problem

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

Your task is to find an order of movements for the knight such that every cell of the board gets visited exactly once (the starting cell is considered visited and shouldn't be visited again).

Return the 2D array board where each cell's value shows the order of visiting that cell, starting from 0 (the initial position of the knight).

Note: A knight can move from cell (r1, c1) to cell (r2, c2) if:

0 <= r2 <= m - 1 and 0 <= c2 <= n - 1
min(abs(r1 - r2), abs(c1 - c2)) = 1 and max(abs(r1 - r2), abs(c1 - c2)) = 2

Input & Output

Example 1 — Small 3×3 Board

$ Input: m = 3, n = 3, r = 1, c = 0

› Output: [[0,7,2],[5,2,1],[6,3,8]]

💡 Note: Knight starts at (1,0) with move 0, then follows L-shaped moves to visit all 9 cells exactly once, ending at (2,2) with move 8

Example 2 — Corner Start

$ Input: m = 3, n = 4, r = 0, c = 0

› Output: [[0,3,8,5],[9,6,1,4],[2,11,10,7]]

💡 Note: Knight starts at corner (0,0), visits all 12 cells in order, demonstrating tour from corner position

Example 3 — Minimum 2×2

$ Input: m = 2, n = 2, r = 0, c = 0

› Output: [[-1,-1],[-1,-1]]

💡 Note: No valid knight's tour exists on 2×2 board since knight needs L-shaped moves which require at least 3×3 space

Constraints

1 ≤ m, n ≤ 10
0 ≤ r < m
0 ≤ c < n

Visualization

Tap to expand

Understanding the Visualization

Input Board

3×3 board with knight starting at position (1,0)

Knight Moves

Knight makes L-shaped moves visiting each cell once

Complete Tour

Final board shows visit order from 0 to 8

Key Takeaway

🎯 Key Insight: Backtracking with Warnsdorff's heuristic efficiently finds valid knight tours by choosing moves with minimum onward options

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is using backtracking with Warnsdorff's heuristic to efficiently find knight tours. The optimal approach prioritizes moves with fewer onward options, dramatically reducing search space. Time: O(8^k), Space: O(m×n) where k << m×n due to smart pruning.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Backtracking	O(8^(m×n))	O(m×n)	Try all possible knight moves recursively until finding a complete tour
Optimized Backtracking with Warnsdorff's Rule	O(8^k)	O(m×n)	Use Warnsdorff's heuristic to prioritize moves with fewer onward options

Brute Force Backtracking — Algorithm Steps

Start from given position, mark as visited with order 0
Try each of 8 possible knight moves
Recursively continue from valid unvisited cells
Backtrack if no valid moves remain
Return solution when all cells visited

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Position

Knight starts at (1,0) marked as move 0

Try Moves

Recursively try all 8 possible knight moves

Backtrack

Undo moves that lead to dead ends

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int moves[8][2] = {{2,1}, {1,2}, {-1,2}, {-2,1}, {-2,-1}, {-1,-2}, {1,-2}, {2,-1}};

bool isValid(int** board, int m, int n, int x, int y) {
    return x >= 0 && x < m && y >= 0 && y < n && board[x][y] == -1;
}

bool backtrack(int** board, int m, int n, int x, int y, int moveCount) {
    board[x][y] = moveCount;
    
    if (moveCount == m * n - 1) {
        return true;
    }
    
    for (int i = 0; i < 8; i++) {
        int nx = x + moves[i][0], ny = y + moves[i][1];
        if (isValid(board, m, n, nx, ny)) {
            if (backtrack(board, m, n, nx, ny, moveCount + 1)) {
                return true;
            }
        }
    }
    
    board[x][y] = -1;
    return false;
}

int** solution(int m, int n, int r, int c) {
    int** board = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        board[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            board[i][j] = -1;
        }
    }
    
    backtrack(board, m, n, r, c, 0);
    return board;
}

int main() {
    int m, n, r, c;
    scanf("%d", &m);
    scanf("%d", &n);
    scanf("%d", &r);
    scanf("%d", &c);
    
    int** result = solution(m, n, r, c);
    printf("[");
    for (int i = 0; i < m; i++) {
        if (i > 0) printf(",");
        printf("[");
        for (int j = 0; j < n; j++) {
            if (j > 0) printf(",");
            printf("%d", result[i][j]);
        }
        printf("]");
    }
    printf("]\n");
    
    for (int i = 0; i < m; i++) {
        free(result[i]);
    }
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(8^(m×n))

Each cell has up to 8 moves, explored exponentially across m×n cells

✓ Linear Growth

Space Complexity

O(m×n)

Board storage plus recursion stack depth of m×n

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler