Does backtracking always use recursion?

No. An explicit stack can implement the same exploration and return process.

Can it find every solution?

Yes, if configured to continue after success and systematically explore the finite search space without unsafe pruning.

How is it related to depth-first search?

Basic backtracking usually explores one sequence of choices deeply before returning to alternatives, making it a form of depth-first exploration with problem-specific feasibility checks.

AI Glossary / Graphs and symbolic AI / Beginner

Backtracking search

Definition

Backtracking search builds a candidate solution through a sequence of tentative choices. When a choice cannot lead to a valid completion, the search undoes it and tries an alternative. In constraint satisfaction, it commonly assigns values to variables one at a time while checking requirements.

What it means

Some problems are easier to solve incrementally than by listing every complete possibility. A room allocation, for example, can be built one meeting at a time. If two meetings already require the same room at the same time, there is no need to finish that particular allocation before recognizing the problem.

Backtracking organizes this process as a search tree. A node represents a partial assignment, and a branch represents another choice. Descending explores an extension; returning upward removes a choice that has failed or been fully explored.

The method can find one solution or enumerate several, depending on its stopping rule. Finding the first feasible solution does not establish that it is the cheapest or otherwise best unless the search also addresses an optimization objective.

How it works

Start with an empty assignment. Choose an unassigned variable and consider its possible values. For each value, check whether adding it violates the relevant constraints. A consistent choice is retained while the procedure recursively tries to assign another variable.

If all variables are assigned consistently, a solution has been found. If a variable has no remaining legal value, return to an earlier decision and try its next alternative. Changes to domains or other temporary state must be restored correctly when the search retreats.

Variable ordering, value ordering and constraint propagation can reduce work substantially. For a finite problem, a systematic exhaustive implementation can eventually find a solution or establish that none exists. The search can still be expensive, and an imposed timeout does not establish impossibility. Practical reporting must distinguish completed exhaustion from interrupted exploration.

Three practical examples

A workshop assigns participants to sessions while respecting capacity and avoiding timetable clashes.
A product builder selects compatible components and revises earlier choices when later requirements cannot be met.
A puzzle application fills cells under explicit rules, undoing tentative values when they make a valid completion impossible.

Think of it this way

Think of assembling an outfit under several requirements. You choose shoes, trousers and a jacket, then discover that the jacket conflicts with the event's dress rule. You reconsider the jacket and, if necessary, an earlier choice.

The analogy is limited because a formal solver needs explicit domains and constraints. Human preferences may be vague or change during selection, while the search algorithm operates on the problem actually represented.

Worked example

A small allocation that needs a return step

Three tasks, A, B and C, must receive different time slots numbered 1, 2 and 3. A may use slots 1 or 2. B may use slots 1 or 2. C may use only slot 1.

Suppose search assigns A = 1 first. B cannot use 1, so it takes 2. C then has no legal slot because its only choice, 1, is already occupied. Search retreats. B has no alternative under A = 1, so it returns to A and tries A = 2.

B then takes 1, again blocking C. Returning to B reveals no remaining alternative because slot 2 is occupied by A. Exhausting these branches shows that this particular problem has no solution: all three tasks are restricted to only two slots.

If B's domain is extended to include slot 3, the assignment A = 2, B = 3, C = 1 becomes feasible. Backtracking does not invent that extra option; the problem definition must provide it.

Illustrative case study

Fictional case: Cedar Workshops introduces automatic room assignments. The first implementation works on simple bookings but sometimes returns an invalid result after exploring a failed branch.

Developers find that a room-capacity adjustment was not restored when the solver undid a tentative assignment. They repair the state restoration and compare small cases against an independent enumeration of all allocations. They also separate “no allocation exists” from “search stopped after its time limit.”

The lesson is that backtracking involves both exploration and careful reversal of temporary changes. A correct high-level search idea can still be undermined by inconsistent bookkeeping.

Common misconceptions and mistakes

Backtracking is random guessing. It can be fully systematic and deterministic.
A partial assignment that passes current checks must have a completion. A conflict may only become visible later.
The first solution is automatically optimal. Feasibility and optimization are different goals.
A timeout proves there is no solution. Only sufficiently complete search or another sound argument can establish that.
Undoing the latest variable is enough. Any related temporary domain or resource changes must also be restored.

Business use

Backtracking is a foundation of many practical configuration and allocation systems. It works especially well when constraints reject bad partial choices early, rather than only after a complete candidate has been built.

For operational use, define the objective, search limits and response to unresolved cases. Test scenarios with no solution as well as easy successful ones. Report which constraints caused difficulty in a form users can understand, while avoiding claims of impossibility when the solver merely ran out of time. Consider ordering and propagation improvements before assuming that a larger machine is the only route to faster search.

Check your understanding

A solver finds one valid seating arrangement and stops. What has it established, and what has it not established?

Answer: It has established that at least one feasible arrangement exists under its model. It has not necessarily found all arrangements or the best arrangement according to a separate preference measure.

Related terms

Learn next

Choose three small variables and list their allowed values and constraints. Draw the first few branches of a backtracking tree, marking where each conflict becomes visible. Then change the variable order and compare the number of choices explored. Study forward checking next to see how future conflicts can be detected earlier.

Forward checking

Sources

Russell and Norvig, Constraint Satisfaction Problems chapter, presents systematic backtracking and improvements: https://aima.cs.berkeley.edu/newchap05.pdf

AIMA Python, constraint-satisfaction implementation, provides a concrete reference for assignment and search operations: https://aima.cs.berkeley.edu/python/csp.html

The task-allocation example and fictional workshop case are original teaching illustrations.

Previous: Backtracking line search Next: Backtranslation