Problem statement
Starting at the supplied square of a rectangular board, visit every square exactly once with knight moves. Return a board where 0 marks the starting visit, 1 the next, and so on through rows×cols−1. Any valid tour is accepted; it need not match a sample board exactly.
The supplied task allows 1–5 rows/columns, a valid zero-based start and guarantees at least one solution. LeetCode The Knight’s Tour may require Premium. This is not Minimum Knight Moves: we need a path covering every square, not a shortest path to one target.
For exploratory unsolvable boards, the teaching method returns an empty board instead of a partially numbered board. That is a defensive extension, not an expected official input.
Constraints & requirements
- CONTRACT
- Original task: 1–5 rows/columns, valid zero-based start, and at least one tour guaranteed. The teaching method also returns an empty board for an unsolvable valid-size input. LeetCode may require Premium.
Examples 3 test cases
Example 1 Case 1
- Input
rows=3; cols=4; start=(0,0)- Output
Any complete tour; one is [[0,3,6,9],[7,10,1,4],[2,5,8,11]]
Verify successive squares form an L move; a different valid board is equally correct.
Example 2 Case 2
- Input
rows=1; cols=1; start=(0,0)- Output
[[0]]
The initial visit already covers the entire board.
Example 3 Case 3
- Input
rows=3; cols=4; start=(0,3)- Output
Any complete tour; one is [[9,6,3,0],[4,1,10,7],[11,8,5,2]]
The starting square must contain zero, not a fixed corner.
Hints Optional
01Hint 1
Mark a chosen square so this path cannot revisit it.
02Hint 2
Try only in-bounds, unvisited L-shaped moves.
03Hint 3
Undo a mark only after failure; preserve the successful complete path.
How to think before coding
The board stores visit order; −1 means unused, not visit zero. The starting square is already marked 0. A call asks whether the next move number can finish the tour. Mark a valid destination, recurse with move+1, and restore −1 only after failure. If all V squares are numbered, return true and retain the successful board.
Brute force and the improvement
Enumerate sequences of V−1 knight moves after the starting visit, where V is the number of squares, and validate each full sequence for bounds, repeats and full coverage. At most eight choices per move give a loose O(V·8^V) checking bound and O(V) sequence storage. The backtracker rejects an illegal or visited destination BEFORE extending it and stops after one complete tour. Trying promising moves first can speed the search, but neither the baseline nor this backtracking method has a polynomial worst-case guarantee.
Intuition: a visit blocks the square only on this path
A knight moves two squares in one direction and one perpendicular: offsets (±2,±1) or (±1,±2). Some offsets leave the board; others reach a square already used on the current path. Reject them before recursion.
Marking a square makes it unavailable to descendants. If that continuation fails, clear its mark so a different route can use it. This temporary-state restoration is why ordinary visited-once graph DFS is not enough.
Algorithm
- Fill the board with −1 for unvisited squares.
- Mark the supplied start 0 and recurse with next move number 1.
- Return true when the next number equals the total square count.
- For each legal unvisited destination, mark it and recurse.
- If the child succeeds, return immediately without undoing the successful tour.
- If it fails, reset that destination to −1 and try the next move.
Java solution
An unsuccessful search returns an empty board, not an unfinished board presented as a tour. A successful path retains its move numbers.
import java.util.*;
class Solution {
private static final int[] KNIGHT_DR = {2, 2, -2, -2, 1, -1, 1, -1};
private static final int[] KNIGHT_DC = {1, -1, 1, -1, 2, 2, -2, -2};
public static int[][] knightTour(int rows, int cols, int row, int col) {
int[][] board = new int[rows][cols];
for (int[] line : board) Arrays.fill(line, -1); // -1 means not yet visited.
board[row][col] = 0; // Starting square is the first visit, numbered zero.
return visitKnight(board, row, col, 1) ? board : new int[0][0]; // Defensive failure, never a partial tour.
}
private static boolean visitKnight(int[][] board, int row, int col, int move) {
if (move == board.length * board[0].length) return true; // All squares already have visit numbers.
for (int i = 0; i < 8; i++) {
int nr = row + KNIGHT_DR[i], nc = col + KNIGHT_DC[i]; // Offset the POSITION, not dimensions.
if (nr < 0 || nr >= board.length || nc < 0 || nc >= board[0].length) continue;
if (board[nr][nc] != -1) continue; // Never revisit a square on the active path.
board[nr][nc] = move; // Choose the square and record its visit order.
if (visitKnight(board, nr, nc, move + 1)) return true; // Preserve a successful complete tour.
board[nr][nc] = -1; // Failed continuation: undo this visit before trying another move.
}
return false; // None of the eight moves completed the remaining tour.
}
public static void main(String[] args) {
System.out.println(Arrays.deepToString(knightTour(3, 4, 0, 0))); // Any valid complete numbered tour.
}
}The driver prints one complete 3×4 tour. Its exact numbers depend on move order. To verify a tour, check every number appears once, zero is at the supplied start, and successive positions satisfy the knight rule.
Choice branches and dry run

Read the text transcript
Follow the Java, step by step
Example: rows = 2, cols = 3, start = (0,0)
What to track: This small failure example traces the whole search. board holds move numbers; -1 means unused. move is the number to write into the next cell, not the current cell’s number.
-
Reserve the start
Java operationboard[row][col] = 0;Stateboard = [[0,-1,-1],[-1,-1,-1]]; call at (0,0), move = 1Only one of six cells has been visited. move == rows × cols is still false.
-
Reject off-board offsets
Java operationif (nr < 0 || nr >= board.length || nc < 0 || nc >= board[0].length) continue;Stateat (0,0), offset indices 0–3 are outside this 2×3 boardNo cell is written for a rejected coordinate. These are checks, not child calls.
-
Try the only legal first move
Java operationboard[nr][nc] = move;Statei = 4 gives (1,2); board = [[0,-1,-1],[-1,-1,1]]The destination is in bounds and unused. Its child receives move = 2.
-
Find the dead end
Java operationif (board[nr][nc] != -1) continue;Stateat (1,2), the only in-bounds knight destination is (0,0), already numbered 0The other seven destinations are outside the board. Reusing the start is forbidden, so this call returns false.
-
Undo the failed move
Java operationboard[nr][nc] = -1;Stateresumed (0,0) frame restores board[1][2] = -1; move is still 1The parent releases exactly the cell it chose, then checks its remaining offsets.
-
Return failure, not a partial solution
Java operationreturn visitKnight(board, row, col, 1) ? board : new int[0][0];Statethe root’s remaining offsets are invalid; root returns false; wrapper returns an empty matrixA successful full tour would return true without undo. This failed search never pretends that its partial path is a tour.
Final result: []: no complete tour exists for this start. The wrapper does not return a partially numbered board.
One valid 3×4 example is:
0 3 6 9 7 10 1 4 2 5 8 11
Its first moves are (0,0)→(1,2)→(2,0)→(0,1). Every move changes one coordinate by 2 and the other by 1. This is one valid example, not a claim that the code’s first explored branch produces this exact matrix.
At (0,0), the two possible destinations are (2,1) and (1,2) when those coordinates exist. The code’s move order tries (2,1) first. If a descendant runs out of moves before visiting all squares, false returns through that branch; each resumed parent removes the mark it placed. When a complete tour returns true, those marks stay.
Why it works
The board records exactly the active simple path, with distinct visit numbers. Each child adds one legal unvisited destination, preserving that invariant. A success means the active path has visited all squares. On failure, undo restores the parent’s exact state, so alternatives remain available. Trying all legal continuations therefore finds a tour whenever one exists, within the search’s runtime limits.
Complexity and alternative approaches
Let B=rows×cols. There are at most eight choices per level and at most B visited squares. A loose worst-case search bound is O(8^B); legal-move and visited checks reduce real branching but do not make plain backtracking polynomial. Initialization/output cost O(B). Board and recursive auxiliary storage are O(B).
Warnsdorff’s heuristic tries destinations with fewer onward legal moves first. It can greatly reduce practical search. Using it only as an ordering heuristic while still backtracking preserves completeness; taking one greedy choice without backtracking is not guaranteed to find a tour.
BFS for shortest paths is not a substitute: its state would need to include the entire visited subset, not only a square. Exhaustively enumerating all tours is also a different task from finding one.
Common mistakes
- Adding offsets to board dimensions rather than the current position.
- Using 0 to mean unvisited when 0 is the starting visit number.
- Undoing before returning a successful board.
- Returning a partial board after failure.
- Comparing output to a single sample instead of validating the tour.