Backtracking is a powerful algorithmic technique for exploring all possible solutions to a problem by making choices, exploring the consequences, and undoing those choices when they don't lead to a solution. It's particularly useful for constraint satisfaction problems like puzzles, mazes, and search problems.
The key insight behind backtracking is that it combines exploration with systematic undoing. When you reach a dead end or determine that a path won't lead to a solution, you "backtrack" by undoing your most recent choice and trying a different option.
Backtracking typically follows this pattern:
This approach is often implemented using depth-first search (DFS) with recursion. The recursive structure naturally handles the "undo" operation when functions return, making the code clean and intuitive.
A classic example is finding paths in a maze where you mark cells as visited while exploring, then unmark them when backtracking. This prevents infinite loops while still allowing the same cell to be part of different solution paths.
1def find_path(maze, start_row, start_col, target, path, visited):
2 # Base case: reached target
3 if maze[start_row][start_col] == target:
4 return True
5
6 # Mark current position as visited
7 visited.add((start_row, start_col))
8 path.append((start_row, start_col))
9
10 # Try all 4 directions
11 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
12 for dr, dc in directions:
13 new_row, new_col = start_row + dr, start_col + dc
14
15 if (is_valid(maze, new_row, new_col) and
16 (new_row, new_col) not in visited):
17
18 if find_path(maze, new_row, new_col, target, path, visited):
19 return True
20
21 # Backtrack: undo our choice
22 visited.remove((start_row, start_col))
23 path.pop()
24 return False