Skip to main content
Talentd

The Knight’s Tour - Solution & Explanation

MediumPremiumFree on FleetCodeArrayBacktrackingMatrix13 min readAsked at: Microsoft
Practice this problem

Problem Statement

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.

 

Example 1:

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:

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

Approach Overview

Problem Overview: You are given an m x n chessboard and a starting cell. A knight moves in L-shapes (8 possible moves). The task is to fill the board so the knight visits every cell exactly once and record the visit order. The result is a matrix where each cell stores the step index of the knight’s visit.

Approach 1: Classic Backtracking (DFS) (Time: O((m*n)!), Space: O(m*n))

This problem maps directly to backtracking. Treat the board as a search tree where each state represents the knight standing on a cell at a specific step. From any position, you try all 8 possible knight moves. If a move lands inside the board and the cell has not been visited, mark it with the next step number and continue the recursion.

If the recursion reaches step m * n, every cell has been visited and the board represents a valid tour. If a path fails, undo the move (set the cell back to unvisited) and try the next candidate. This systematic exploration guarantees correctness but can explore many branches in the worst case.

The board itself acts as the visited structure, so no additional set is needed. The recursion depth is at most m * n, giving O(m*n) space complexity. This approach demonstrates strong understanding of backtracking and grid traversal on a matrix.

Approach 2: Backtracking with Move Ordering (Warnsdorff-style Heuristic) (Time: ~O(m*n) average, Space: O(m*n))

The main inefficiency in naive backtracking is exploring moves in arbitrary order. A well-known optimization is to try moves that lead to the fewest onward options first. This heuristic reduces branching dramatically because it avoids early dead ends.

For each candidate knight move, compute how many valid moves remain from that position. Sort or prioritize moves with the smallest degree and explore those first. The search still uses recursion and backtracking, but the ordering guides the algorithm toward valid tours much faster.

In practice, this heuristic solves most boards close to linear exploration relative to the number of cells, though the theoretical worst case remains exponential. It still relies on grid traversal over an array representation of the board.

Recommended for interviews: Start with the classic backtracking formulation. It clearly models the knight moves, visited tracking, and recursion structure interviewers expect. Once that works, mention move-ordering heuristics as an optimization to reduce branching. Showing the brute-force search proves you understand the constraint exploration, while the heuristic demonstrates deeper algorithmic thinking.

Solution

We create a two-dimensional array g, used to record the knight's movement order, initially g[r][c] = -1, and all other positions are set to -1 as well. Additionally, we need a variable ok to record whether a solution has been found.

Next, we start depth-first search from (r, c). Each time we search position (i, j), we first check if g[i][j] equals m times n - 1. If so, it means we have found a solution, then we set ok to true and return. Otherwise, we enumerate the knight's eight possible movement directions to position (x, y). If 0 leq x < m, 0 leq y < n, and g[x][y]=-1, then we update g[x][y] to g[i][j]+1, and recursively search position (x, y). If after the search, the variable ok is true, we return directly. Otherwise, we reset g[x][y] to -1 and continue searching in other directions.

Finally, return the two-dimensional array g.

The time complexity is O(8^{m times n}), and the space complexity is O(m times n). Here, m and n are the integers given in the problem.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Backtracking (DFS)O((m*n)!)O(m*n)When implementing the straightforward recursive search for all knight moves.
Backtracking with Move Ordering (Warnsdorff Heuristic)~O(m*n) averageO(m*n)Preferred for faster solutions by prioritizing moves with fewer onward options.

Video Solution

2664. The Knight’s Tour - Week 4/5 Leetcode October Challenge • Programming Live with Larry • 392 views views

Frequently Asked Questions

Is The Knight’s Tour easy or hard?
The Knight’s Tour is typically considered a medium-to-hard backtracking problem. The recursion logic itself is straightforward, but handling move validation, visited tracking, and pruning the search efficiently requires solid understanding of backtracking and matrix traversal.
The Knight’s Tour Python/Java solution
Implement the solution using recursive backtracking. Maintain an m x n board initialized with -1, place the starting cell as step 0, and recursively try all 8 knight moves while marking and unmarking cells during exploration. The same logic works across Python, Java, C++, Go, TypeScript, and Rust.
How to solve The Knight’s Tour in O(n)?
A strict O(n) algorithm does not generally exist for constructing arbitrary knight tours. Most solutions rely on backtracking with pruning. However, heuristic strategies such as Warnsdorff’s rule often behave close to linear relative to the number of cells in practical cases.
What is the best approach for The Knight’s Tour?
Backtracking with smart move ordering is the most effective approach. The algorithm recursively tries all valid knight moves while marking visited cells in the board. Adding heuristics such as prioritizing moves with fewer onward options significantly reduces branching and makes the solution practical.
Is The Knight’s Tour asked at Google/Amazon/Meta?
Knight traversal and grid backtracking problems appear in interviews at companies like Google, Amazon, and Meta in various forms. While the exact LeetCode problem may not appear verbatim, the underlying techniques—backtracking, matrix traversal, and constraint exploration—are common interview topics.
What data structure is used in The Knight’s Tour?
The primary data structure is a 2D matrix representing the chessboard. Each cell stores the step number of the knight’s visit. The algorithm also uses recursion (DFS) and predefined arrays of knight move offsets to explore valid positions.
What is the time complexity of The Knight’s Tour?
The theoretical worst-case time complexity of the backtracking solution is O((m*n)!) because the algorithm may explore many permutations of moves. In practice, heuristics such as Warnsdorff’s rule reduce the exploration dramatically. Space complexity remains O(m*n) due to recursion depth and the board storage.

Ready to solve this problem?

Practice The Knight’s Tour with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays