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 <= 50 <= r <= m - 10 <= c <= n - 1Problem 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.
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.
| Approach | Time | Space | When 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) average | O(m*n) | Preferred for faster solutions by prioritizing moves with fewer onward options. |
2664. The Knight’s Tour - Week 4/5 Leetcode October Challenge • Programming Live with Larry • 388 views views
Practice The Knight’s Tour with our built-in code editor and test cases.
Practice on FleetCode