Constraint satisfaction

Backtracking Search

Fill in one variable at a time, undo when you hit a wall.

Interactive demo coming soon — read the theory below

The idea

Backtracking Search solves a Constraint Satisfaction Problem (CSP) by assigning values to variables one at a time. After each assignment it checks the rules (constraints). If everything still fits, it moves on to the next variable; if a variable has no legal value left, it "backtracks" — undoes the last choice and tries a different one. It is really just a smart depth-first search over partial solutions, and it's the standard backbone for CSP solving.

How it works

A CSP has three parts: variables (the blanks to fill), domains (the allowed values for each blank), and constraints (the rules that say which combinations are legal).
Pick one unassigned variable to work on next.
Try one value from its domain and tentatively assign it.
Check the constraints: does this value clash with any variable already assigned?
If it's legal, recurse — move on and assign the next variable the same way.
If the whole recursion below eventually succeeds, you're done: a complete, valid assignment is found.
If the value is illegal, or the recursion below fails, undo it and try the next value in the domain.
If no value in the domain works, return failure to the caller — that caller then backtracks and tries a different value for the previous variable.

OPEN, CLOSED & the data structures

An assignment: a partial map of variable to chosen value, grown and shrunk as the search goes. A domain per variable: the set of values still allowed. The recursion stack itself acts as the memory of past choices, so undoing a choice is just returning from a recursive call. Ordering heuristics add small bits of bookkeeping (e.g. counts of remaining legal values) to decide which variable and value to try next.

Pseudocode

function BACKTRACK(assignment, csp):
    if assignment is complete:          # every variable has a value
        return assignment               # success

    var = SELECT-UNASSIGNED-VARIABLE(csp, assignment)   # e.g. MRV heuristic
    for value in ORDER-DOMAIN-VALUES(var, csp, assignment):  # e.g. LCV
        if value is CONSISTENT with assignment (no constraint broken):
            add {var = value} to assignment
            result = BACKTRACK(assignment, csp)   # recurse to next variable
            if result != failure:
                return result
            remove {var = value} from assignment  # undo: backtrack

    return failure          # no value worked -> caller backtracks

At a glance

Complete?Yes — complete. Because it systematically tries every value for every variable and only abandons a branch when it provably breaks a rule, it will find a valid assignment whenever one exists (and report failure only when none does), given finite domains.

Optimal?For a plain CSP the goal is a valid, complete assignment, and backtracking guarantees it finds one if it exists — so it is "optimal" in the sense of correctness. It does NOT rank solutions by quality; for best-cost solutions you need a constraint-optimization variant (e.g. branch-and-bound).

TimeO(d^n) worst case — n variables each with up to d values. Exponential in theory, but good ordering heuristics and constraint checks prune huge chunks in practice.

SpaceO(n) — it only stores the current partial assignment plus the recursion stack, one frame per variable. Light on memory, just like depth-first search.

👍 When to use it

You have a puzzle-like problem with variables, allowed values, and rules to satisfy: Sudoku, map/graph coloring, N-Queens, timetabling, seating charts.
You need any valid solution, not the single cheapest one.
The problem is discrete and finite, so each variable has a listable set of choices.
You want a memory-light method that a heuristic can dramatically speed up.

⚠️ Watch out for

Bad ordering wastes enormous time. Use heuristics: MRV (Minimum Remaining Values) picks the most-constrained variable — the blank with the fewest legal options left, i.e. the one most likely to fail fast; the degree heuristic breaks ties by choosing the variable involved in the most constraints; least-constraining-value (LCV) tries the value that rules out the fewest options for its neighbors.
Plain backtracking only checks constraints against already-assigned variables, so it can wander far before noticing a doomed branch. Constraint propagation (forward checking / arc consistency) catches dead ends earlier.
It finds a valid assignment, not the best one — don't expect optimization for free.
Infinite or continuous domains break it; each variable needs a finite, enumerable set of values.
Undo carefully: when you backtrack you must restore both the assignment and any domain values you trimmed, or later branches get corrupted.