Backtracking – Solving Puzzles and Mazes with Recursion

Greedy algorithms are fast, but sometimes they hit dead ends. When you need to explore all possibilities and undo decisions, it’s time to bring in backtracking.

Backtracking is a strategy for solving problems incrementally, trying options and backtracking (undoing) when a decision leads to a dead end. It’s a natural fit for recursive(1,2) thinking and is used in puzzles, constraint solvers, and pathfinding.

What is Backtracking?

Backtracking is a refined brute-force method that uses recursion to:

  1. Make a choice
  2. Explore further
  3. If it fails, back up and try a different path

This allows us to explore the entire solution space in a structured way.

Classic Examples

  • Solving mazes – Try moving in each direction recursively until you hit the exit.
  • N-Queens Problem – Place queens on a chessboard so no two attack each other.
  • Sudoku Solver – Try placing a number in each cell, backtrack if invalid.
  • Word Search – Find words by exploring all directions from each letter.

Maze Solving Example

Here’s a recursive backtracking approach to find a path through a maze:

def solve_maze(x, y, maze, path):
    if (x, y) is goal:
        return True
    for direction in [up, down, left, right]:
        if move is valid and not visited:
            mark current cell
            if solve_maze(next_x, next_y, maze, path):
                return True
            unmark cell  # backtrack
    return False

The recursive function tries every path until it finds one that works.

How Backtracking Works

Backtracking is usually implemented with recursion and implicit stacks:

  • Each recursive call adds a new decision layer.
  • If the base case isn’t met, it tries the next option.
  • If no options work, it “backs out” and tries something else.

This is exponential in the worst case (O(b^d), where b is branching factor and d is depth), but often pruned quickly when invalid paths are discarded early.

Real-World Use Cases

  • Puzzle solving – Sudoku, crosswords, word ladders
  • Combinatorics – Permutations, subsets, combinations
  • Constraint satisfaction – Scheduling, resource allocation
  • Game AI – Exploring possible moves in board games (e.g., chess, checkers)

Backtracking vs Other Approaches

Strategy Can Undo? Tries All Paths Optimal? Fast?
Greedy ❌ ❌ Sometimes ✅
Dynamic Prog. ❌ No (caches instead) ✅ ✅
Backtracking ✅ ✅ ✅ ❌ (but thorough)

Backtracking is complete—it will find a solution if one exists. But it’s often slow unless combined with heuristics or pruning strategies. We used backtracking in our Train Track Solver, combining it with heuristics and pruning sped it up and made our solution much faster!

Challenge Time! 🧩

  • Solve the N-Queens problem for n = 8 using recursion and backtracking.
  • Build a maze solver that prints the path from start to finish.
  • Modify a Sudoku solver to count all valid solutions.

In our next post: Real-World Applications – where we’ll see how everything we’ve learned in CQH103 powers modern software, from search engines to smart assistants.