Skip to content

Backtracking

Task: Place four queens on a 4x4 board so none can attack another

00112233CALL STACKplace(0)col 1place(1)col 3place(2)col 0place(3)col 2DECISIONS 31 / 31

Why we need Backtracking

Analogy

  • Imagine you're trying to escape a maze.
  • You walk forward until you hit a dead end.
  • Then you step back to the last decision point and try a different path.
  • That's exactly how Backtracking works: undoing choices when they don't lead to a solution.

What is Backtracking?

Definition

  • Backtracking is an algorithmic technique for solving problems by exploring all possible options.
  • If a chosen path fails, the algorithm reverts (backtracks) and tries another.
  • It's often used in search and optimization problems.

Key idea

  1. Make a choice

  2. Explore further

  3. If it leads to a dead end, undo the choice and try another

  4. Continue until a solution is found or all options are exhausted

Classic examples

  • N-Queens Problem → placing queens on a chessboard without attacking each other.
  • Sudoku Solver → filling numbers while checking constraints.
  • Maze Solving → finding a path to the exit.

Code skeleton

Python
def backtrack(path, options):  if solution_found(path):      return path  for option in options:      if is_valid(option, path):          path.append(option)          result = backtrack(path, options)          if result: return result          path.pop()  # undo choice  return None

Advantages

  • Finds all possible solutions.
  • Elegant way to handle complex problems.
  • Works well with constraints (like Sudoku rules).

Limitations

  • Can be slow for large problems (explores many paths).
  • May require optimization techniques like pruning to skip impossible paths.

🎯 Quick recap

  • Backtracking = trial and error with undo.
  • Analogy: escaping a maze.
  • Used in puzzles, constraint problems, and optimization.

Recursion vs Backtracking

RecursionBacktracking
DefinitionA function calling itself to solve smaller subproblems.A problem-solving technique that explores choices and undoes them if they fail.
Key ideaBreak problem into smaller versions until a base case is reached.Try a path, and if it fails, step back and try another.
AnalogyRussian dolls: open each until the smallest is reached.Maze escape: backtrack when hitting a dead end.
Use casesFactorials, Fibonacci, Tower of Hanoi, divide-and-conquer algorithms.N-Queens, Sudoku solver, maze solving, constraint satisfaction problems.
EfficiencyCan be elegant but may repeat work if not optimized (use memoization).Can be slow for large problems; often improved with pruning.
TerminationStops at a base case.Stops when all possible paths are explored or a solution is found.

Key takeaway

  • Recursion = breaking problems into smaller versions.
  • Backtracking = exploring paths and undoing wrong choices.
  • Backtracking often uses recursion internally to explore possibilities.