Visualizing the Backtracking algorithm solving a randomly generated maze.
Overview
Systematic trial and error
Backtracking builds a solution one decision at a time. At each step it takes a candidate choice and recurses. If that eventually leads to a solution, done. If it leads to a dead end, the algorithm undoes the choice and tries the next candidate. If every candidate fails, it returns failure to the previous level, which then undoes its choice.
The undo step is what distinguishes backtracking from plain recursion, and it is where implementations usually go wrong. State that was mutated on the way down must be restored on the way back up, or later branches inherit the corruption.
LIVE PREVIEW
Ready
Initializing system...
Backtracking Search Method: A Practical Guide
Try a choice, follow it as far as it goes, and undo it the moment it fails. Backtracking is brute force with the dead ends pruned away - which is often the difference between impossible and instant.
The template
Nearly every backtracking problem fits this shape:
solve(state):
if state is complete: record it, return
for each candidate c:
if c is not valid here: continue ← pruning
apply c to state
solve(state)
undo c from state ← the backtrack
The validity check is the entire performance story. Without it you are enumerating every possibility; with it you discard whole subtrees before exploring them.
How much pruning buys you
The eight queens problem asks for eight queens on a chessboard with none attacking another. Placing eight pieces on 64 squares gives about 4.4 billion arrangements. Restricting to one queen per column cuts it to 88 = 16.7 million. Checking rows and diagonals as you place each queen — abandoning a branch the moment two queens conflict — brings the actual number of positions examined down to roughly 15,000.
Same search space, same guarantee of finding every solution, five orders of magnitude less work. The algorithm did not get cleverer about queens; it just stopped exploring branches that were already known to fail.
Try, recurse, undo
Backtracking explores a space of partial solutions. At each step it makes a choice, recurses, and then undoes the choice before trying the next one.
That undo step is what distinguishes it from plain recursion, and it is what makes exhaustive search possible with a single shared state rather than a copy per branch.
def permutations(items):
result, current, used = [], [], [False] * len(items)
def backtrack():
if len(current) == len(items):
result.append(current[:]) # copy - current keeps changing
return
for i, item in enumerate(items):
if used[i]:
continue
current.append(item); used[i] = True # choose
backtrack() # explore
current.pop(); used[i] = False # UNDO
return
backtrack()
return result
Three lines carry the whole pattern: choose, explore, undo. Every backtracking solution has that shape, and the current[:] copy on line 6 is the detail people miss — appending current itself stores a reference to a list that will keep changing.
Pruning is what makes it feasible
Without pruning, backtracking is brute force with a stack. With pruning, it is often practical on spaces that are astronomically large.
The n-queens problem places n queens on an n×n board with none attacking another. There are 64 choose 8 = 4.4 billion arrangements for n = 8. Backtracking with pruning examines about 15,000 positions.
The saving comes from abandoning a branch the moment it cannot succeed:
def solve_queens(n):
cols, diag1, diag2 = set(), set(), set()
board, out = [], []
def place(row):
if row == n:
out.append(board[:])
return
for col in range(n):
if col in cols or (row-col) in diag1 or (row+col) in diag2:
continue # PRUNE - cannot possibly work
cols.add(col); diag1.add(row-col); diag2.add(row+col)
board.append(col)
place(row + 1)
board.pop()
cols.discard(col); diag1.discard(row-col); diag2.discard(row+col)
place(0)
return out
The three sets are the pruning mechanism, and the diagonal encoding is the neat part: all squares on a descending diagonal share row - col, and all on an ascending diagonal share row + col. That turns an O(n) attack check into O(1).
Better pruning beats a faster machine. That is the practical lesson of this whole topic.
Recognising a backtracking problem
The signals:
The answer is a sequence of choices — a permutation, a subset, an assignment, a path.
Choices constrain later choices.
You need all solutions, or one satisfying constraints, rather than an optimum computed from subproblems.
The state can be undone cheaply.
Problem
Choice at each step
Permutations
Which unused item comes next
Subsets
Include this item or not
N-queens
Which column in this row
Sudoku
Which digit in this cell
Word search
Which adjacent cell to move to
Graph colouring
Which colour for this vertex
Combination sum
Which candidate to add next
If the problem instead asks for a maximum or a count computable from overlapping subproblems, dynamic programming is usually the better tool — it reuses work where backtracking re-derives it.
What pruning is worth, counted
Backtracking is brute force that gives up early, and "gives up early" is doing all the work. N-Queens is the standard example because the saving is enormous and easy to count: the same search, with and without the check that rejects a partial placement.
example_01.pyPython
def solve(n, prune=True):
stats = {"nodes": 0, "solutions": 0}
cols = []
def safe(row, col):
for r, c in enumerate(cols):
if c == col or abs(c - col) == row - r:
return False
return True
def place(row):
stats["nodes"] += 1
if row == n:
stats["solutions"] += 1
return
for col in range(n):
if prune and not safe(row, col):
continue # abandon this branch immediately
cols.append(col)
if not prune and row == n - 1:
# without pruning, only check at the very bottom
ok = all(cols[i] != cols[j] and
abs(cols[i] - cols[j]) != j - i
for i in range(n) for j in range(i + 1, n))
if ok:
stats["solutions"] += 1
stats["nodes"] += 1
else:
place(row + 1)
cols.pop()
place(0)
return stats
print("%5s %14s %18s %12s %10s" % (
"n", "with pruning", "without pruning", "solutions", "saved"))
for n in range(4, 9):
a = solve(n, True)
b = solve(n, False)
print("%5d %14d %18d %12d %9.0f%%" % (
n, a["nodes"], b["nodes"], a["solutions"],
100 * (1 - a["nodes"] / b["nodes"])))
# The solution counts agree, so both searches are correct. The node counts
# do not: without pruning the search builds every one of the n^n possible
# placements and tests each at the bottom. With pruning it abandons a
# branch the moment two queens attack, and by n = 8 it has skipped over
# 99% of the tree.
#
# The saving grows with n, which is the important part. Pruning is not a
# constant-factor optimisation here -- it changes the shape of the search.
print()
print("%5s %16s" % ("n", "n^n (all placements)"))
for n in range(4, 9):
print("%5d %16d" % (n, n ** n))
# Note what pruning does NOT do: this is still exponential. Backtracking
# makes an intractable search merely expensive, and the win comes entirely
# from testing the constraint as early as it can be tested. A check that
# can only run on a complete candidate prunes nothing.
#
# The template, which is the part worth carrying away:
#
# choose a candidate
# if it violates a constraint -> reject, try the next
# if the solution is complete -> record it
# otherwise recurse, then UNDO the choice and try the next
#
# The undo is the line people forget. Here it is cols.pop(), and without
# it the partial state leaks into sibling branches:
print()
print("one solution for n=6:", end=" ")
def first_solution(n):
cols = []
def safe(row, col):
return all(c != col and abs(c - col) != row - r
for r, c in enumerate(cols))
def place(row):
if row == n:
return list(cols)
for col in range(n):
if safe(row, col):
cols.append(col)
got = place(row + 1)
if got:
return got
cols.pop() # the undo
return None
return place(0)
sol = first_solution(6)
print(sol)
for row, col in enumerate(sol):
print(" " + " ".join("Q" if c == col else "." for c in range(6)))
Output
Things to try
Watch a path get committed. Press Step repeatedly. The search extends along a single route, taking the first available direction each time — the same depth-first commitment as DFS.
Catch the undo. Keep stepping until the path hits a dead end. Watch cells get unmarked as the search retreats. That erasure is the backtrack, and it is what frees those cells for a different attempt.
Watch it re-use a corridor. After a retreat, notice the search often re-enters territory it just abandoned, this time turning a different way. The state was properly restored, which is exactly why that is possible.
Compare mazes. Press New Maze a few times and Run each. Open mazes with many branches cause far more backtracking than corridor-like mazes, where there is rarely a choice to get wrong.
Where it is used
Constraint solvers — SAT solvers, scheduling, timetabling. Backtracking with sophisticated pruning is the core of DPLL, which underlies modern SAT solving.
Regular expression matching — backtracking regex engines try alternatives and undo, which is also why pathological patterns can take exponential time.
Parsing — recursive descent with backtracking for ambiguous grammars.
Compiler register allocation as graph colouring.
Test generation and combinatorial coverage.
The regex point is worth noting because it has real security implications: catastrophic backtracking on adversarial input is a denial-of-service vector, which is why some engines use non-backtracking automata instead.
What trips people up
Not undoing the state. The single most common bug. If you mark a cell, recurse, and forget to unmark it on failure, later branches see phantom occupied cells and valid solutions get missed.
Pruning too late. Checking validity only when the solution is complete turns backtracking back into brute force. Check at every step, as early as the constraint allows.
Passing mutable state by reference and recording it directly. When a solution is found, store a copy. Storing the live object means the backtracking that follows mutates your recorded answer.
Expecting it to be fast in the worst case. Pruning improves the typical case, not the bound — worst-case complexity is still exponential. If pruning is weak, so is the algorithm.
In one line
Backtracking explores the space of partial solutions depth-first, abandoning a branch as soon as it violates a constraint and undoing its state on the way back out. The undo is what makes it correct and the early constraint check is what makes it fast — without pruning it is exhaustive search, and with it, problems with billions of arrangements resolve in thousands of steps. The complexity remains exponential in the worst case; the art is in pruning hard enough that the worst case rarely arrives.
Avoiding duplicate results
A recurring difficulty: when the input contains duplicates, naive backtracking produces the same solution several times.
The standard fix is to sort the input and skip a candidate that equals its predecessor at the same recursion depth:
def subsets_with_dup(nums):
nums.sort()
out, cur = [], []
def go(start):
out.append(cur[:])
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]:
continue # skip duplicates at this level
cur.append(nums[i])
go(i + 1)
cur.pop()
go(0)
return out
The condition i > start is precise and easy to get wrong: it skips a repeated value only when it is a sibling choice at the same level, not when it is used deeper in the same branch. Writing i > 0 instead would incorrectly exclude legitimate solutions containing the value twice.
Complexity, and what to expect
Backtracking is exponential in general, and the exponent depends on the problem's shape.
Problem
Complexity
Permutations of n
O(n! × n)
Subsets of n
O(2ⁿ × n)
N-queens
O(n!) worst case, far less with pruning
Sudoku
Exponential; instant in practice with good pruning
Combination sum
Depends on the target and candidates
The gap between worst case and practice is the whole point. Sudoku's search space is enormous and a constraint-propagating solver finishes a newspaper puzzle in milliseconds, because most branches die immediately.
Two techniques beyond basic pruning:
Constraint propagation. After each choice, deduce forced consequences — a Sudoku cell with only one possible digit must take it. This can solve many puzzles with almost no search.
Ordering heuristics. Choose the most constrained variable next (the cell with fewest candidates), so failures are discovered early rather than deep in the tree.
Questions people ask
What is the difference from brute force? Backtracking prunes branches that cannot lead to a solution. Brute force enumerates everything.
How is it different from DFS? It is DFS over a state space, with explicit undo and pruning.
When should I use DP instead? When subproblems overlap and you want an optimum or a count. Backtracking enumerates; DP reuses.
Why do I need to copy the current state? Because it is mutated in place. Storing a reference gives you a list that changes underneath you.
How do I stop after the first solution? Return a boolean up the recursion and stop exploring once it is true.
Why is my solution too slow? Almost always insufficient pruning. Add constraints that fail earlier, and order choices so failures are found sooner.
Recap in one screen
Choose, explore, undo — the undo is what distinguishes backtracking from ordinary recursion.
Pruning is what makes it practical: n-queens goes from billions of arrangements to thousands of positions.
Copy the state when recording a solution, or you store a reference to something still changing.
Sort and skip equal siblings to avoid duplicate results on duplicate input.
Constraint propagation and choosing the most constrained variable next are the two upgrades that matter.
Run it in Python
Eight queens, solved by placing one and undoing it when it fails, with the number of positions actually examined printed against the number a brute-force search would have tried. The ratio is why backtracking exists.
backtracking.pyPython 3
# Backtracking: place, recurse, and undo the placement if it fails.
N = 8
nodes = 0
def safe(queens, row, col):
for r, c in enumerate(queens):
if c == col or abs(r - row) == abs(c - col): # same column or diagonal
return False
return True
def solve(queens, first_only=True, found=None):
global nodes
found = [] if found is None else found
row = len(queens)
if row == N: # all N placed: a solution
found.append(list(queens))
return found
for col in range(N):
nodes += 1
if safe(queens, row, col):
queens.append(col) # place
solve(queens, first_only, found)
queens.pop() # UNDO - this is the backtrack
if first_only and found:
return found
return found
solutions = solve([], first_only=True)
board = solutions[0]
print(f"first solution for {N} queens: {board}")
for row, col in enumerate(board):
print(" " + " ".join("Q" if c == col else "." for c in range(N)))
print()
print(f"positions examined : {nodes:,}")
brute = N ** N
print(f"brute force would try : {brute:,} (every column for every row)")
print(f"pruning removed : {100 * (1 - nodes / brute):.4f}% of the space")
nodes = 0
all_solutions = solve([], first_only=False)
print()
print(f"all solutions for {N} queens: {len(all_solutions)}")
print(f"positions examined : {nodes:,}")
Output
How the code works
row = len(queens)The state is just a list of column choices, one per row, so the depth of the recursion is the row being filled. Encoding one queen per row also removes the entire “two queens in a row” case for free.
if c == col or abs(r - row) == abs(c - col):The whole conflict test. Two squares are on a diagonal exactly when the row difference equals the column difference — no board array is needed at all.
queens.append(col) ... queens.pop()Place, explore, undo. The pop is the backtrack, and forgetting it is the classic bug: the state leaks into sibling branches and the search quietly explores nonsense.
if safe(queens, row, col):The pruning. A partial placement that already conflicts is abandoned before any of its N^(remaining rows) completions are generated — which is where the percentage printed at the end comes from.
nodes vs N ** N16.7 million positions in the naive space against a few thousand actually examined. Backtracking is still exponential in the worst case; it is simply exponential in a far smaller space.
Change one thing
Drop N to 4 and print the board at every placement. On a small board the place-and-undo rhythm is short enough to read in full.
Delete queens.pop(). The search finds nothing and examines far fewer nodes — a wrong answer that looks like an optimisation.
Raise N to 10 with first_only=False. 724 solutions, and the node count shows what one extra row costs.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
What is the 'backtrack' in the N-queens program?
Place, explore, undo. Delete the pop and the state leaks into sibling branches, so the search finds nothing while looking like an optimisation.
Why is state stored as one column per row rather than as a board?
Encoding removes an entire class of conflict for free, and the recursion depth becomes the row being filled.
Backtracking beats brute force because it:
It is still exponential in the worst case, just over a far smaller space - the program prints the percentage of positions pruned.
Cheat sheet
Backtracking Search Method
Backtracking builds a solution one decision at a time. At each step it takes a candidate choice and recurses. If that eventually leads to a solution, done. If it leads to a dead end, the algorithm undoes the choice and tries the next candidate. If every candidate fails, it returns failure to the previous level, which then undoes its choice.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.