Must the constraints change while the solver runs?

No. The dynamic aspect can be the internal ordering of assignments in a fixed problem.

Can every later assignment be retained?

No. Retention and explanation updates must respect the dependencies and rules of the algorithm.

Does keeping useful work guarantee an optimal solution?

No. The basic discussion concerns satisfying constraints; optimization requires an additional objective and an appropriate search method.

AI Glossary / Graphs and symbolic AI / Intermediate

Dynamic backtracking

Definition

Dynamic backtracking is a constraint-search method that revises a decision responsible for a conflict while preserving other assignments that need not be discarded. It uses explanations of rejected values and changes the effective ordering of decisions during search. The aim is to avoid erasing useful progress merely because an earlier choice must be reconsidered.

What it means

Ordinary chronological backtracking follows the decision stack backward. Returning to an earlier variable can remove several later assignments, including choices unrelated to the failure. Dynamic backtracking tries to retain such work where the dependency information permits it.
The term names a particular family of dependency-aware search ideas associated with Ginsberg's original algorithm. Dynamic does not mean the external problem itself changes, nor does it refer to dynamic programming. A fixed constraint problem can be solved with dynamic backtracking because the search's decision ordering changes internally.

How it works

The solver records why particular values are unavailable under current assignments. When a variable has no remaining value, those explanations identify earlier choices involved in the failure. A relevant assignment is withdrawn, while other assignments can remain. The withdrawn variable is reconsidered later in the resulting ordering.
Explanation maintenance is essential. A reason that depended on a removed assignment may no longer justify rejecting a value, so the solver must update its records. The original method establishes completeness under its specified rules while controlling storage. Arbitrarily keeping assignments and forgetting explanations would not inherit those guarantees.

Three practical examples

A scheduling solver retains unrelated room choices when a conflict forces revision of an earlier time-slot decision.
A configuration experiment compares chronological backtracking with a method that preserves independent component choices after a failure.
A teaching CSP solver displays conflict explanations so learners can see why one assignment changes while another remains.

Think of it this way

Think of correcting one item in a checklist without crossing out every later item that remains valid. This captures preservation of independent progress. The analogy is limited because a solver needs explicit dependency information and disciplined explanation updates; human intuition that a later choice seems unrelated is not a correctness argument.

Worked example

Consider variables X, Y, and Z, each initially with domain {1,2}. Constraints require X = Z and Z = 2. Y is independent. Imagine the solver currently holds X = 1 and Y = 1, then attempts Z without having propagated these consequences earlier.
Value Z = 1 fails the constraint Z = 2. Value Z = 2 fails equality with X = 1. The dead end therefore depends on X's choice, while Y's choice plays no role. A dependency-aware revision can withdraw X = 1 and retain Y = 1. Reconsidering X with value 2 permits Z = 2, producing the valid assignment (X,Y,Z) = (2,1,2).
Chronological search with the fixed order X,Y,Z can instead revisit Y before changing X, unless additional pruning prevents that work. This is a conceptual trace showing why retaining Y is reasonable, not a complete step-by-step implementation of Ginsberg's algorithm. A production implementation must also maintain the value-elimination explanations that justify revisiting X and prevent unsound or repetitive search.

Illustrative case study

At fictional Moss Scheduling, a prototype repeatedly recomputes a set of independent room assignments whenever a remote equipment conflict appears. The team instruments decision dependencies and tests whether a dynamic-backtracking approach can preserve those room choices.
It also checks impossible instances and cases where a supposedly independent assignment actually shares a constraint. This fictional case illustrates an evaluation plan rather than a reported speedup. Preserving more assignments is useful only if the solver still finds correct solutions or correctly establishes that none exists.

Common misconceptions and mistakes

Dynamic backtracking is not simply jumping farther up a fixed stack. Backjumping can skip irrelevant decision levels but still discard later work; dynamic backtracking emphasizes retaining suitable assignments while altering the decision order.
Do not confuse retained assignments with a guarantee that they will never change later. New conflicts can require further revision. Explanation records also cannot be treated as permanent truths independent of their supporting assignments. Finally, the method is not automatically faster on every problem. Dependency tracking has costs, and tightly connected constraints may leave little unrelated work to preserve.

Business use

Businesses evaluating constraint solvers should compare solution validity, time, memory, and repeated work on representative instances. Record the solver's actual propagation and ordering settings, since these can affect comparisons with simple chronological search. Include unsatisfiable cases and cases with substantial constraint overlap. A custom implementation needs careful explanation maintenance and termination checks; the name dynamic backtracking alone does not confer the theoretical guarantees of the published algorithm.

Check your understanding

In the worked example, why can Y = 1 remain while X = 1 is withdrawn?

Answer: No constraint links Y to the failure. Z's rejected values are explained by its fixed-value requirement and the conflicting X assignment. Retaining Y preserves unrelated progress in this model.

Related terms

Learn next

Add the constraint Y = X to the worked example. Recheck whether keeping Y = 1 remains compatible with the eventual X = 2 solution. Explain how a newly introduced dependency changes which assignments can be preserved and what further revision is needed.

Sources

Ginsberg, Dynamic Backtracking, original research abstract: https://arxiv.org/abs/cs/9308101 Ginsberg, original Journal of Artificial Intelligence Research paper: https://people.csail.mit.edu/ruijie/6834/ginsberg93a.pdf

Previous: Dyna-Q with exploration bonus (Dyna-Q+) Next: Dynamic Bayesian network