Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
A knight's tour visits every cell of an n×n board exactly once using knight moves. Backtrack from a start cell: number cells as you visit them, try each of the 8 knight moves, recurse, and unmark on the way back. To find one tour, return as soon as all n² cells are numbered; to count tours, keep searching after each success. Raw backtracking is enormous, so Warnsdorff's heuristic — always move to the neighbor with the fewest onward moves — prunes it to near-linear for finding a single tour.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can structure Hamiltonian-path backtracking on a grid, enumerate the 8 knight moves correctly, and know that a degree-based heuristic (Warnsdorff) makes finding one tour tractable.
Where candidates slip
Getting the 8 move offsets wrong, forgetting to unmark on backtrack, or believing raw backtracking can find a tour on larger boards without the heuristic.
How to stand out
Write clean mark/unmark backtracking, then introduce Warnsdorff's rule and explain why visiting the least-flexible cell first avoids painting yourself into dead ends.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewKnight visits every cell onceFind one tour or count all?Count allOne tourExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Plain Backtracking (Counts All Tours)
1Hint 1Explore hintHide hint
How do you guarantee 'every cell exactly once'? Number cells as you visit them and require the count to reach n².
2Hint 2Explore hintHide hint
From the current cell, try all 8 knight moves; recurse into any in-bounds, unvisited target.
3Hint 3Explore hintHide hint
Mark the cell with its visit number before recursing and reset it to 0 when you back out, so other branches can use it. To count tours, don't stop at the first success — tally it and keep going.
A · Core idea
Search every possible move sequence, numbering cells and undoing dead ends.
Visit numbering enforces the constraint. Store the visit index in board[r][c] (using a sentinel like 0 for unvisited, and offsetting visit numbers by 1, or a separate visited grid). When the visit count reaches n², every cell has been used exactly once — that's a complete tour.
The 8 knight moves. From (r, c) the knight can reach (r±1, c±2) and (r±2, c±1). Encode these as eight (dr, dc) offset pairs and iterate them.
Choose, explore, un-choose. Mark the current cell with its visit number, then recurse into each legal neighbor (in bounds and unvisited). After trying all moves, unmark the cell. The unmark is essential: a cell that led to a dead end on one path must be free for a different path.
Counting vs finding. For a single tour, return true the instant count == n². To count all tours, treat reaching count == n² as one success — increment a counter and continue exploring siblings rather than returning. Either way the mark/unmark discipline keeps the board consistent.
Why it doesn't scale. Without guidance the knight wanders into dead ends constantly, and the tree is astronomically large for boards beyond a handful of cells. That motivates the heuristic next.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 5, start (0,0)Interactive diagram
The 8 knight moves
visit (0,0)From the center K, a knight reaches up to 8 cells; edge and corner cells reach fewer.
a valid tour (count incremented)C · Code with teaching comments
Reference implementation previewprivate static final int[] DR = {-2, -2, -1, -1, 1, 1, 2, 2}; private static final int[] DC = {-1, 1, -2, 2, -2, 2, -1, 1}; private int n; private int[][] board; private int tours;Explore the full codeHide the full code
D · Why it works and complexityO(8^(n²)) timeO(n²) spaceOpen the invariant and proofExplore the proofHide the proof
A knight's tour is a Hamiltonian path on the knight-move graph, and Hamiltonian-path search is hard in general. Plain backtracking is correct and fine for counting on small boards, but its blind move ordering is exactly what the next approach fixes.
ComplexityO(8^(n²)) time, O(n²) space — Each cell offers up to 8 moves and a tour has n² steps, so the unpruned search tree is O(8^(n²)) in the worst case. The board and recursion stack are O(n²). In practice the visited check and dead ends prune enormously, but counting still only finishes for small n.
E · Edge cases and pitfalls3Wrong knight offsets — e.g. (±1,±1) (that's a king) instead of the L-shape.Explore edge casesHide edge cases
Pitfalls
- Wrong knight offsets — e.g. (±1,±1) (that's a king) instead of the L-shape.
- Forgetting to unmark on backtrack, permanently blocking cells.
- Early-returning on the first tour when the task is to COUNT all tours.
Approach 2 of 2 · Optimal
Backtracking + Warnsdorff's Heuristic (Finds One Tour Fast)
1Hint 1Explore hintHide hint
Dead ends happen when you leave a cell with few exits stranded. Which cell should you visit first to avoid trapping it?
2Hint 2Explore hintHide hint
Order the 8 candidate moves by the number of unvisited onward moves each target has — fewest first (lowest degree).
3Hint 3Explore hintHide hint
Visit the most constrained neighbor first. Keep backtracking as a safety net for ties/edge cases, but the heuristic usually drives straight to a full tour.
A · Core idea
Guide the search to the least flexible cell first so you never strand a hard-to-reach square.
The dead-end intuition. A cell with only one remaining entrance must be visited while that entrance is still open; if you wander past it, it becomes unreachable and the tour fails. So the smart move is to head toward cells that are running out of options.
Warnsdorff's rule. Among the legal next moves, pick the neighbor whose own count of unvisited onward moves (its degree in the remaining graph) is smallest. Intuitively you 'use up' the most constrained cells early, while the flexible cells stay available to patch the path together later.
How it plugs into backtracking. Compute, for each of the up-to-8 legal targets, how many unvisited moves it would have. Sort the targets by that degree, ascending, and recurse in that order. Keep the mark/unmark structure so that on the rare occasion the heuristic mis-steps (ties can mislead), the search can still back out and try the next candidate.
Why it's so effective. Greedy degree ordering turns an astronomically branchy search into one that usually walks straight to a solution, because it continually resolves the tightest constraints first. It's the classic 'most-constrained-variable' heuristic from constraint satisfaction, specialized to the knight graph.
Caveat. Warnsdorff finds a tour; it isn't a way to count all tours. Tie-breaking choices affect which tour you get, and there are constructed boards where naive tie-breaking needs the backtracking fallback. For counting, use the exhaustive approach on small n.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 5, start (0,0)Interactive diagram
Warnsdorff picks the lowest-degree neighbor
(0,0)Two legal moves; the heuristic visits the degree-2 corner-ish cell before the degree-5 central one.
a complete 5×5 tourC · Code with teaching comments
D · Why it works and complexitynear-linear O(n²) in practice (no proof of always succeeding) timeO(n²) spaceOpen the invariant and proofExplore the proofHide the proof
Warnsdorff is the 'most-constrained-first' principle: resolve the cell with the fewest escape routes before it gets cut off. The same heuristic — pick the variable with the smallest remaining domain — speeds up Sudoku solvers and general CSP backtracking.
Complexitynear-linear O(n²) in practice (no proof of always succeeding) time, O(n²) space — At each of n² steps you score up to 8 neighbors, each by counting up to 8 onward moves — O(64) per step, so O(n²) overall when the heuristic avoids backtracking. Worst case it can still backtrack, but in practice Warnsdorff finds a tour in near-linear time. Space is O(n²) for the board.
E · Edge cases and pitfalls7n = 1 — count == n*n already at the start cell → trivial tour returned.Explore edge casesHide edge cases
Edge cases handled
n = 1count == n*n already at the start cell → trivial tour returned.n = 3No open tour exists; heuristic dead-ends and backtracking exhausts options → returns null.tie in degreesA stable tie-break is needed; the sort order resolves ties deterministically, with backtracking as a fallback.start at a cornerCorners have only 2 moves; the heuristic naturally drains them early.
Pitfalls
- Computing degree using already-visited cells — must count only unvisited onward moves.
- Assuming Warnsdorff never backtracks — keep the fallback for safety and odd boards.
- Using the heuristic to COUNT tours — it finds one, not all.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewprivate static final int[] DR = {-2, -2, -1, -1, 1, 1, 2, 2}; private static final int[] DC = {-1, 1, -2, 2, -2, 2, -1, 1}; private int n; private int[][] board; Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Degree counts visited cells
Warnsdorff must rank a cell by its remaining (unvisited) onward moves. Counting visited cells inflates the degree and breaks the most-constrained-first ordering.
Explore the code comparisonHide the code comparison
Degree counts visited cells
Warnsdorff must rank a cell by its remaining (unvisited) onward moves. Counting visited cells inflates the degree and breaks the most-constrained-first ordering.
Don't write this
def degree(r, c):
cnt = 0
for dr, dc in zip(DR, DC):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n:
cnt += 1 # WRONG: ignores whether the cell is visited
return cntWrite this instead
def degree(r, c):
cnt = 0
for dr, dc in zip(DR, DC):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and board[nr][nc] == 0:
cnt += 1 # only unvisited onward moves
return cnt2Missing backtrack reset
If a cell tried on a failed branch isn't reset to 0, every later branch sees it as visited, making most tours unreachable and counts wrong.
Explore the code comparisonHide the code comparison
Missing backtrack reset
If a cell tried on a failed branch isn't reset to 0, every later branch sees it as visited, making most tours unreachable and counts wrong.
Don't write this
board[nr][nc] = count + 1;
if (solve(nr, nc, count + 1)) return true;
// WRONG: board[nr][nc] left setWrite this instead
board[nr][nc] = count + 1;
if (solve(nr, nc, count + 1)) return true;
board[nr][nc] = 0; // reset on backtrackRevise
Carry the pattern into the interview
Pattern to remember
Grid backtracking over 8 knight moves, pruned by Warnsdorff's rule
Code pattern to memorize
solve(r, c, count):
board[r][c] = count
if count == n*n: record / return true
for each of 8 knight moves (dr, dc):
nr, nc = r+dr, c+dc
if in bounds and board[nr][nc] == 0:
if solve(nr, nc, count + 1): return true
board[r][c] = 0 # backtrackRules to remember
- 1There are exactly 8 knight moves: (±1, ±2) and (±2, ±1).
- 2Mark a cell with its visit number before recursing; reset it to 0 on backtrack.
- 3Success is
count == n*n— every cell visited exactly once. - 4For finding ONE tour, apply Warnsdorff's heuristic: visit the neighbor with the fewest unvisited onward moves first — it slashes the search.
- 5To COUNT all tours you must explore exhaustively (no early return); this is feasible only for small n.
Use this pattern when
- Hamiltonian-path-style 'visit every cell once' on a board with fixed move shapes
- Constraint search where greedy ordering (most-constrained-first) prunes hard
- Small boards where exhaustive backtracking is acceptable
- Demonstrating Warnsdorff's degree heuristic
Choose another pattern when
- Just need shortest knight path between two squares → BFS, not a full tour
- Large n with a count requirement → exponential, infeasible; counts are studied combinatorially
- Reachability only → BFS/DFS without the visit-everything constraint
- Closed tour with parity obstacles (e.g. odd n×n) → no closed tour exists; know the parity facts
Interview takeaway
Knight's Tour is Hamiltonian-path backtracking with a killer pruning rule: Warnsdorff's 'go to the most constrained cell next'. The mark/unmark skeleton is standard; the heuristic is what makes a single tour findable on bigger boards.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternKnight's Tour is Hamiltonian-path backtracking on the knight-move graph, supercharged by Warnsdorff's most-constrained-first heuristic. The mark/unmark skeleton matches Rat in a Maze and N-Queens; the degree heuristic matches Sudoku-style CSP solving.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Closed Knight's TourComing soonRequire the final cell to be a knight move from the start; parity rules out closed tours on odd n×n boards.
- Knight Probability in ChessboardComing soonDP over knight moves for probabilities — not a tour, but the same 8-move model.
- Minimum Knight MovesComing soonShortest knight path between two cells — BFS, since you don't need to visit everything.
- Sudoku SolverComing soonSame most-constrained-first heuristic: fill the cell with the fewest candidates next to prune backtracking.