Knight's Tour: Backtracking with Warnsdorff Heuristic

Problem Statement#

Place a knight on an n x n chessboard at a given starting square. Find a sequence of legal knight moves that visits every square exactly once. This is the classic Knight's Tour, an instance of finding a Hamiltonian path on the knight-move graph.

Variants include:

• Open tour: the knight ends at any square.
• Closed tour: the knight ends one move away from the start (forming a cycle).
• Maze path: find any path from corner to corner (a simpler grid version).

For n = 5 the open tour is solvable; for n = 4 it is not. For n >= 5, both open and closed tours exist for most starting squares.

Why This Problem Matters#

The Knight's Tour is a textbook example interviewers reach for when they want to test heuristic-guided backtracking. Naive recursion has worst case O(8^(n^2)) and dies on n = 8. Adding Warnsdorff's rule — always move to the square with the fewest onward moves — turns it into a near-linear algorithm in practice. Candidates who can articulate why the heuristic works (it greedily commits to "bottleneck" squares before they get stranded) signal mature algorithmic thinking.

This problem also shows up in maze and pathfinding interviews at Google, Amazon, and Meta in the form of "find a Hamiltonian path on a small graph" or "tour every cell of a grid."

The Core Insight (decision tree / state space)#

State: (x, y, move_number, visited_board). Decision: which of the up to 8 knight moves to take next. Goal: move_number == n*n - 1 with every square marked visited.

Brute backtracking explores up to 8 children per node and n^2 levels deep, giving the awful 8^(n^2) bound. Warnsdorff's heuristic reorders the children by their degree — the number of unvisited squares each child can reach. The lowest-degree child goes first because it has the fewest future options; if we do not commit to it now, it might become unreachable.

Intuitively: corner-adjacent squares have only 2 knight moves and become traps if we leave them for last. The heuristic respects gravity — fill the squares with the fewest exits first.

Visual Dry Run (recursion tree)#

For a knight at the corner of a 5x5 board, the eight possible moves are filtered down to two on-board, unvisited squares. Each of those squares has its own degree (number of onward unvisited moves). Warnsdorff sorts them ascending and tries the smaller-degree square first.

start (0,0) move=0
  candidates (1,2) deg=3 and (2,1) deg=3
  pick (1,2) (tie-break by index)
    move=1 at (1,2)
      candidates filtered, sorted by degree
      pick min-degree -> commit
      ... recursion proceeds, each level greedy

Without backtracking the heuristic alone solves most boards. Backtracking is a safety net for the rare cases where the greedy choice paints us into a corner.

Solution (Optimal) — Python + JavaScript with backtracking template, complexity#

def knights_tour(n, start=(0, 0)):
    moves = [(2, 1), (2, -1), (-2, 1), (-2, -1),
             (1, 2), (1, -2), (-1, 2), (-1, -2)]
    board = [[-1] * n for _ in range(n)]
 
    def degree(x, y):
        count = 0
        for dx, dy in moves:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == -1:
                count += 1
        return count
 
    def backtrack(x, y, move_num):
        board[x][y] = move_num
        if move_num == n * n - 1:
            return True
        neighbors = []
        for dx, dy in moves:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == -1:
                neighbors.append((degree(nx, ny), nx, ny))
        neighbors.sort()
        for _, nx, ny in neighbors:
            if backtrack(nx, ny, move_num + 1):
                return True
        board[x][y] = -1
        return False
 
    return board if backtrack(*start, 0) else None

function knightsTour(n, startX = 0, startY = 0) {
  const moves = [[2,1],[2,-1],[-2,1],[-2,-1],[1,2],[1,-2],[-1,2],[-1,-2]];
  const board = Array.from({ length: n }, () => Array(n).fill(-1));
 
  const degree = (x, y) => {
    let count = 0;
    for (const [dx, dy] of moves) {
      const nx = x + dx, ny = y + dy;
      if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] === -1) count++;
    }
    return count;
  };
 
  const backtrack = (x, y, moveNum) => {
    board[x][y] = moveNum;
    if (moveNum === n * n - 1) return true;
    const neighbors = [];
    for (const [dx, dy] of moves) {
      const nx = x + dx, ny = y + dy;
      if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] === -1) {
        neighbors.push([degree(nx, ny), nx, ny]);
      }
    }
    neighbors.sort((a, b) => a[0] - b[0]);
    for (const [, nx, ny] of neighbors) {
      if (backtrack(nx, ny, moveNum + 1)) return true;
    }
    board[x][y] = -1;
    return false;
  };
 
  return backtrack(startX, startY, 0) ? board : null;
}

Complexity: brute backtracking is O(8^(n^2)). With Warnsdorff the practical complexity is closer to O(n^2) for most boards, though worst-case bounds remain exponential. Space is O(n^2) for the board plus O(n^2) for recursion depth.

Common Mistakes#

• Implementing Warnsdorff without backtracking. The heuristic alone fails on certain start squares; always keep the backtrack as a fallback.
• Computing degree against the original board instead of the current visited state. Always count only unvisited squares.
• Forgetting to undo board[x][y] = -1 on backtrack — leaves the board in an inconsistent state.
• Mixing up the 8 move offsets. A typo here silently breaks everything.

Interview Tips#

• Lead with "I will use backtracking guided by Warnsdorff's heuristic." This signals you know the named technique.
• Justify the heuristic with the "trap squares get stranded" argument.
• Mention the connection to Hamiltonian path and acknowledge the NP-completeness in general graphs.
• Walk through the move offsets carefully — interviewers often pause here.

Follow-up Questions#

• Closed tour: the knight must return to a square one move from start.
• Generalize to other piece moves (queen, camel, fairy chess pieces).
• Maze pathfinding (rat in a maze): same backtracking template, fewer move options.
• Grid Hamiltonian path: shows up in LeetCode 980 (Unique Paths III).

Key Takeaways#

• Knight's Tour is a Hamiltonian-path classic; brute backtracking is O(8^(n^2)).
• Warnsdorff's heuristic — always move to the lowest-degree unvisited square — turns the practical runtime near-linear.
• Always combine the heuristic with backtracking; the heuristic alone is not provably complete.
• The "trap squares" intuition makes the heuristic memorable: handle bottlenecks early.
• The same backtracking-with-ordering pattern reappears in Sudoku, n-Queens, and graph coloring.
• A great interview prep problem because it forces you to combine recursion, heuristics, and grid manipulation.

Sources:

• Warnsdorff's algorithm for Knight's tour problem - GeeksforGeeks
• The Knight's Tour - GeeksforGeeks