LeetCode Problem 2664

Difficulty: 🟡 Medium
Topics: Array, Backtracking, Matrix

Solution

LeetCode 2664 - The Knight’s Tour

Problem Understanding

This problem asks us to construct a complete knight’s tour on an m x n chessboard. A knight’s tour is a sequence of knight moves such that every cell on the board is visited exactly once.

We are given:

• m, the number of rows
• n, the number of columns
• (r, c), the starting position of the knight

We must return a 2D matrix where each cell stores the order in which the knight visits that position. The starting cell must contain 0, the next visited cell must contain 1, and so on until all m * n cells have been assigned.

A knight moves in an L-shape. From position (x, y), the knight can move to any of these eight relative positions:

• (x + 2, y + 1)
• (x + 2, y - 1)
• (x - 2, y + 1)
• (x - 2, y - 1)
• (x + 1, y + 2)
• (x + 1, y - 2)
• (x - 1, y + 2)
• (x - 1, y - 2)

The move is valid only if the destination remains inside the board.

The constraints are extremely important here:

• 1 <= m, n <= 5
• The total number of cells is at most 25
• The problem guarantees that at least one valid tour exists

These small constraints strongly suggest that a backtracking solution is feasible. In larger knight’s tour problems, naive backtracking becomes prohibitively expensive, but with at most 25 cells, exhaustive search with pruning works comfortably.

There are several edge cases worth considering:

• A 1 x 1 board, where the knight never moves
• Very narrow boards, where the number of legal knight moves is limited
• Boards where the knight has only one valid continuation at some step
• Situations where an incorrect early move leads to a dead end later

The guarantee that a solution exists simplifies the implementation because we do not need to handle impossible inputs.

Approaches

Brute Force Backtracking

The most direct approach is to try every possible knight move recursively.

Starting from (r, c), we mark the current cell with the current move number. Then we attempt all valid knight moves that lead to unvisited cells. For each move, we recursively continue building the tour.

If at any point we reach a state where no further moves are possible before visiting all cells, we backtrack by unmarking the current cell and trying a different path.

This approach is correct because it systematically explores every possible valid sequence of knight moves. Eventually, if a solution exists, the recursion will find it.

However, the search space grows exponentially. Each position can branch into several possible moves, producing an enormous number of candidate paths.

Optimized Backtracking with Warnsdorff-style Heuristic

The key observation is that many recursive branches fail because they trap the knight in a region with no future exits.

A classic heuristic for knight’s tour problems is to prioritize moves that have the fewest onward options. This is inspired by Warnsdorff’s Rule.

The reasoning is intuitive:

• Cells with very limited mobility are dangerous
• If we postpone visiting them, they may become unreachable later
• Visiting constrained cells earlier reduces the chance of dead ends

So before exploring next moves, we sort candidate positions by how many onward moves they have.

This dramatically reduces unnecessary branching and makes the search extremely efficient for the given constraints.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(m × n)	Explores all possible tours recursively
Optimal	Much smaller practical exponential search	O(m × n)	Uses move ordering heuristic to prune failures early

Algorithm Walkthrough

1. Create an m x n board initialized with -1.

The value -1 indicates an unvisited cell. Once a cell is visited, we store the move number in it. 2. Mark the starting position (r, c) with 0.

This represents the first move of the knight. 3. Define the eight possible knight moves.

These represent all legal relative knight displacements. 4. Create a recursive DFS function.

The function receives:

• current row
• current column
• current move index

The move index indicates how many cells have already been visited. 5. Check whether all cells have been visited.

If move_index == m * n, then every cell has been assigned successfully, so we return True. 6. Generate all valid next moves.

For each knight direction:

• compute the new position
• ensure it remains inside bounds
• ensure the destination is unvisited

7. Compute the degree of each candidate move.

For every candidate cell, count how many future valid moves it has available.

This implements the heuristic:

• smaller degree means more constrained
• more constrained cells should be visited earlier

8. Sort candidate moves by degree.

This ordering greatly improves search efficiency. 9. Try each candidate recursively.

For each move:

• assign the current move index
• recurse
• if recursion succeeds, return True
• otherwise undo the move and continue

10. Return the completed board once recursion succeeds.

Why it works

The algorithm maintains the invariant that every visited cell contains a unique move number and no cell is visited more than once.

Backtracking guarantees correctness because every legal continuation is eventually explored unless a valid tour is found earlier. The heuristic does not remove valid solutions, it only changes exploration order. Therefore, if a valid tour exists, the algorithm will find one.

Python Solution

from typing import List

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

        directions = [
            (2, 1),
            (2, -1),
            (-2, 1),
            (-2, -1),
            (1, 2),
            (1, -2),
            (-1, 2),
            (-1, -2),
        ]

        def is_valid(row: int, col: int) -> bool:
            return (
                0 <= row < m
                and 0 <= col < n
                and board[row][col] == -1
            )

        def count_onward_moves(row: int, col: int) -> int:
            count = 0

            for dr, dc in directions:
                nr = row + dr
                nc = col + dc

                if is_valid(nr, nc):
                    count += 1

            return count

        def dfs(row: int, col: int, move_index: int) -> bool:
            if move_index == m * n:
                return True

            candidates = []

            for dr, dc in directions:
                nr = row + dr
                nc = col + dc

                if is_valid(nr, nc):
                    degree = count_onward_moves(nr, nc)
                    candidates.append((degree, nr, nc))

            candidates.sort()

            for _, nr, nc in candidates:
                board[nr][nc] = move_index

                if dfs(nr, nc, move_index + 1):
                    return True

                board[nr][nc] = -1

            return False

        board[r][c] = 0
        dfs(r, c, 1)

        return board

The implementation begins by initializing the board with -1, representing unvisited cells.

The directions array stores all eight knight movements. Using a predefined list keeps the move generation concise and avoids repetitive code.

The is_valid helper checks both board boundaries and visitation status. This centralizes validation logic and prevents duplicated conditions throughout the recursion.

The count_onward_moves helper implements the heuristic. For a candidate position, it counts how many future legal moves remain available. This value acts as the node degree used for move ordering.

The dfs function performs recursive backtracking. The base case occurs when the move index equals the total number of cells, meaning the tour is complete.

Inside the recursion, we collect all legal next moves together with their degrees. Sorting the candidates ensures that the most constrained positions are attempted first.

For each candidate:

• mark the move number
• recurse deeper
• undo the move if recursion fails

Once a successful path is found, the recursion immediately propagates True upward.

Go Solution

package main

import "sort"

func tourOfKnight(m int, n int, r int, c int) [][]int {
	board := make([][]int, m)

	for i := 0; i < m; i++ {
		board[i] = make([]int, n)

		for j := 0; j < n; j++ {
			board[i][j] = -1
		}
	}

	directions := [][]int{
		{2, 1},
		{2, -1},
		{-2, 1},
		{-2, -1},
		{1, 2},
		{1, -2},
		{-1, 2},
		{-1, -2},
	}

	isValid := func(row int, col int) bool {
		return row >= 0 &&
			row < m &&
			col >= 0 &&
			col < n &&
			board[row][col] == -1
	}

	var countOnwardMoves func(int, int) int

	countOnwardMoves = func(row int, col int) int {
		count := 0

		for _, d := range directions {
			nr := row + d[0]
			nc := col + d[1]

			if isValid(nr, nc) {
				count++
			}
		}

		return count
	}

	type Candidate struct {
		degree int
		row    int
		col    int
	}

	var dfs func(int, int, int) bool

	dfs = func(row int, col int, moveIndex int) bool {
		if moveIndex == m*n {
			return true
		}

		candidates := []Candidate{}

		for _, d := range directions {
			nr := row + d[0]
			nc := col + d[1]

			if isValid(nr, nc) {
				degree := countOnwardMoves(nr, nc)

				candidates = append(candidates, Candidate{
					degree: degree,
					row:    nr,
					col:    nc,
				})
			}
		}

		sort.Slice(candidates, func(i, j int) bool {
			return candidates[i].degree < candidates[j].degree
		})

		for _, candidate := range candidates {
			board[candidate.row][candidate.col] = moveIndex

			if dfs(candidate.row, candidate.col, moveIndex+1) {
				return true
			}

			board[candidate.row][candidate.col] = -1
		}

		return false
	}

	board[r][c] = 0
	dfs(r, c, 1)

	return board
}

The Go implementation mirrors the Python logic closely.

A custom Candidate struct stores the degree and coordinates for sorting purposes. Go does not support tuple sorting as conveniently as Python, so using a struct keeps the implementation clean.

The board is initialized manually with nested loops because Go slices default to zero values rather than -1.

The recursive DFS uses closures for helper functions. Since the maximum board size is only 25 cells, recursion depth is completely safe.

Worked Examples

Example 1

Input:

m = 1, n = 1, r = 0, c = 0

Initial board:

0

The knight has already visited the only cell.

The DFS immediately satisfies:

move_index == m * n
1 == 1

Final board:

[[0]]

Example 2

Input:

m = 3, n = 4, r = 0, c = 0

Initial board:

0	-1	-1	-1
-1	-1	-1	-1
-1	-1	-1	-1

From (0,0) the knight can move to:

Candidate	Degree
(1,2)	2
(2,1)	2

Suppose the algorithm selects (1,2) first.

Board after move 1:

0	-1	-1	-1
-1	-1	1	-1
-1	-1	-1	-1

The recursion continues similarly, always prioritizing cells with fewer onward moves.

One valid final configuration is:

0	3	6	9
11	8	1	4
2	5	10	7

Each number differs from the next by a legal knight move.

Example 3

Input:

m = 1, n = 5, r = 0, c = 0

This case is impossible for a knight tour, but the problem guarantees valid inputs, so such a case will never appear in the actual test set.

This guarantee allows the implementation to terminate as soon as a valid tour is found without needing special failure handling.

Complexity Analysis

Measure	Complexity	Explanation
Time	Exponential in worst case	Backtracking may explore many candidate paths
Space	O(m × n)	Board storage plus recursion stack

The theoretical worst-case complexity remains exponential because knight tour search is fundamentally combinatorial.

However, the practical runtime is dramatically improved by move ordering. Since the board contains at most 25 cells, the optimized DFS completes efficiently within constraints.

The space complexity comes primarily from:

• the board itself
• recursive call stack depth up to m * n

Test Cases

from typing import List

def validate_knight_tour(board: List[List[int]]) -> bool:
    m = len(board)
    n = len(board[0])

    positions = [None] * (m * n)

    for i in range(m):
        for j in range(n):
            positions[board[i][j]] = (i, j)

    for k in range(m * n - 1):
        r1, c1 = positions[k]
        r2, c2 = positions[k + 1]

        dr = abs(r1 - r2)
        dc = abs(c1 - c2)

        if not ((dr == 1 and dc == 2) or (dr == 2 and dc == 1)):
            return False

    return True

solver = Solution()

# Example 1, single cell board
board = solver.tourOfKnight(1, 1, 0, 0)
assert board == [[0]]

# Example 2, standard valid board
board = solver.tourOfKnight(3, 4, 0, 0)
assert validate_knight_tour(board)

# Small square board
board = solver.tourOfKnight(5, 5, 0, 0)
assert validate_knight_tour(board)

# Different starting position
board = solver.tourOfKnight(5, 5, 2, 2)
assert validate_knight_tour(board)

# Rectangular board
board = solver.tourOfKnight(4, 5, 1, 2)
assert validate_knight_tour(board)

# Minimal valid movement board
board = solver.tourOfKnight(3, 4, 1, 1)
assert validate_knight_tour(board)

# Ensure all numbers appear exactly once
board = solver.tourOfKnight(5, 5, 0, 0)
values = sorted(num for row in board for num in row)
assert values == list(range(25))

Test Summary

Test	Why
1x1 board	Validates smallest possible input
3x4 example	Validates standard tour generation
5x5 board	Stresses deeper recursion
Different start position	Ensures algorithm works from arbitrary cells
Rectangular board	Confirms non-square handling
Central starting point	Tests branching-heavy positions
Uniqueness validation	Ensures every number appears exactly once

Edge Cases

Single Cell Board

A 1 x 1 board is the smallest possible input. There are no knight moves available, but the tour is already complete because the starting cell counts as visited.

This can easily cause bugs if the implementation assumes at least one recursive move must occur. Our solution handles it naturally because the DFS base case succeeds immediately after assigning 0.

Highly Constrained Boards

Small boards often give the knight very limited movement options. A poor early choice can quickly trap the knight and make the remaining cells unreachable.

This is exactly why naive backtracking can become inefficient. The degree-based heuristic addresses this by prioritizing constrained cells first, significantly reducing dead-end exploration.

Arbitrary Starting Positions

The knight may start anywhere on the board, including corners, edges, or center cells.

Corner positions usually have fewer legal moves, while center positions have more branching possibilities. Incorrect boundary checks can easily cause index errors in these cases.

The is_valid helper centralizes all boundary and visitation checks, ensuring every generated move is safe before recursion proceeds.