vizlearn

Modules / Algorithms / Backtracking

Backtracking

Algorithms & Data StructuresBy Ashish JangraUpdated 26 October 2026

Visualizing the Backtracking algorithm solving a randomly generated maze.

Controls

Legend

Visited Path

Solution

Dead End

Current Head

LIVE PREVIEW

Ready

Initializing system...

Overview

At each step, select a candidate, check the constraints, and continue only if the partial solution is still possible. When the branch finishes, restore the previous state before trying the next candidate. Pruning is the main advantage over generating every complete candidate and checking it afterward.

The choose, explore, undo pattern

def search(state):
    if complete(state):
        record(state.copy())
        return

    for choice in candidates(state):
        if valid(choice, state):
            apply(choice, state)
            search(state)
            undo(choice, state)

The copy matters when recording answers: if the mutable state itself is stored, later undo steps can change the saved solution.

Worked example: find a path through a grid

From the start cell, choose an unvisited open neighbour and continue. If the route reaches a wall or a cell with no available neighbour, return to the previous cell and try another direction. Rejecting a route at the first dead end avoids exploring paths that cannot reach the goal.

Use Step in the visualizer to follow one branch. When it reaches a dead end, watch it unmark cells and return to the previous choice. The undo restores the shared grid for another route.

Cost and when to use it

Backtracking can still take exponential time in the worst case: if few partial candidates can be rejected, it approaches exhaustive search. Its actual cost depends on the branching factor, search depth, and how early constraints prune branches. It fits puzzles, scheduling, combinations, and other problems where a partial answer can be tested cheaply.

Order choices to expose contradictions early, and maintain constraint state so validity checks are inexpensive. For large search spaces, stronger methods such as constraint propagation, dynamic programming, or specialized solvers may be needed.

Common mistakes with Backtracking Search

Forgetting to undo state: later branches inherit choices from earlier ones.
Checking constraints only at the end: invalid branches waste work.
Saving a reference instead of a copy: recorded solutions mutate during backtracking.
Assuming pruning guarantees speed: worst-case search can remain exponential.

Sources and next steps

Princeton Algorithms: Backtracking introduces recursive search and pruning.
Continue with recursion and the call stack and depth-first search.

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.

Predict, then reveal

About to run: press Step. Before it does — what happens to the readout?

Committing to an answer first is the point — the reveal runs the experiment on the visualisation above and reads the real value back, so nothing here is scripted.

Check yourself

0 of 3

Answer without scrolling back up.

What is the 'backtrack' in the N-queens program?
Why is state stored as one column per row rather than as a board?
Backtracking beats brute force because it:

Cheat sheet

Backtracking Search Method

Watch backtracking commit to a path, hit a dead end, and unwind to the last decision point until the puzzle resolves.

ALGORITHMS · vizlearn.in/dsa/backtracking.html

About the author

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.

About VizLearn GitHub LinkedIn Contact