Why return to an irrelevant choice?

The chronological rule follows decision order rather than analyzing the cause of failure.

Does it always find a solution if one exists?

For a finite problem, systematic exhaustive search with correct checks can do so; stopping early or pruning incorrectly removes that assurance.

Can propagation accompany it?

Yes. Propagation and the choice of backtracking destination are different aspects of the solver.

AI Glossary / Graphs and symbolic AI / Intermediate

Chronological backtracking

Definition

Chronological backtracking is a search method that responds to a dead end by undoing the most recent decision that still has an untried alternative. It explores choices in depth-first order and retreats through its decision history one level at a time. In constraint satisfaction, those decisions usually assign values to variables.

What it means

The word chronological describes the order of decisions, not clock time or the dates in the data. Suppose a solver chooses a room, then a time, then a presenter. If no presenter works, it normally revisits the time choice before reconsidering the room. It does this even when the room is the real cause of the conflict.
The method is a clear baseline for systematic search. Its simplicity also exposes a weakness: the most recent decision is not necessarily the relevant decision. More advanced methods can analyze a conflict and jump back to an earlier choice that actually contributed to it.

How it works

Start with a partial assignment. Choose an unassigned variable and try an available value. If the resulting partial assignment violates a constraint that can already be checked, reject that value. Otherwise continue recursively. When a variable has no viable value left, remove its assignment and return to the previous decision level.
At that level, try the next value. If none remains, retreat again. Finding a complete consistent assignment succeeds; exhausting the first decision's alternatives establishes failure for a finite, fully explored problem. The variable order, value order, and optional constraint propagation affect how much work is done. They do not change the basic chronological rule for where to return after failure.

Three practical examples

A small scheduling tool assigns sessions one at a time and reverses its last assignment when the next session has no feasible slot.
A configuration solver tries compatible component choices, undoing recent choices when a complete configuration cannot be formed.
A puzzle solver fills a cell, continues to later cells, and retreats through those assignments after reaching a contradiction.

Think of it this way

Think of exploring a branching corridor while keeping a stack of junctions. A blocked passage sends you to the latest junction with an unexplored turn. The analogy explains the retreat order, but search decisions need not describe physical places. It also omits constraint propagation, which may detect a blocked route before the solver walks down it.

Worked example

Consider variables X, Y, and Z, each with values 1 and 2. Require X = Z and Z = 2; Y has no constraint. Use variable order X, Y, Z, try 1 before 2, and check constraints only when their variables are assigned. Do not use forward checking.
The solver first chooses X = 1 and Y = 1. Z = 1 violates Z = 2, while Z = 2 violates X = Z. Z therefore has no usable value. Chronological backtracking returns to Y and tries Y = 2. Both Z choices fail again, for exactly the same reasons. Only after exhausting Y does it return to X and try X = 2. Then Y = 1 and Z = 2 give a valid solution.
The unnecessary change to Y is the point: Y did not cause either failure. A different propagation or conflict-analysis strategy could avoid this repeated work. The trace describes this particular simple algorithm, not every solver that uses backtracking.

Illustrative case study

At fictional Cedar Workshops, a developer builds a small assignment checker with a visible decision trace. When a request fails, the trace shows repeated changes to an unrelated display preference before a resource choice is reconsidered. The developer uses that example to compare ordinary chronological retreat with a conflict-aware alternative.
The team keeps the simple version as a reference implementation and compares returned assignments against the same constraints. This fictional case illustrates diagnosis and algorithm comparison; it does not claim a measured speedup or suggest that a more elaborate search strategy always pays for its overhead.

Common misconceptions and mistakes

Backtracking does not mean restarting the entire search after every mistake. It normally retains the earlier part of the assignment and replaces a recent choice. Chronological backtracking also differs from backjumping, which can skip irrelevant decision levels.
A rejected partial assignment is not proof that the whole problem is impossible. Every relevant alternative must be excluded before reporting that conclusion. Another mistake is to assume that the first solution is cheapest or best: ordinary satisfaction search finds a valid assignment, unless an optimization mechanism is added. Finally, an incomplete constraint model can produce a formally consistent assignment that still fails the real task.

Business use

This method is useful when a business needs an understandable baseline for a modest configuration or scheduling problem. Record the variable order and the reasons for rejected values so repeated effort is visible. Evaluate performance on representative difficult cases as well as easy ones. When the search grows too large, consider propagation, better ordering, or conflict analysis before assuming that more computing capacity is the only remedy.

Check your understanding

In the worked example, why does changing Y fail to help?

Answer: Neither constraint mentions Y. With X fixed at 1, no value of Z can simultaneously satisfy X = Z and Z = 2, regardless of Y.

Related terms

Learn next

Learn forward checking next. Repeat the example while removing inconsistent values from future variables after each assignment, and compare when the contradiction becomes visible. Then study backjumping to separate earlier detection from a different choice of retreat destination.

Forward checking

Sources

Primary sources: Russell and Norvig, original constraint-satisfaction teaching slides, https://aima.cs.berkeley.edu/4th-ed/slides-pdf/chapter05.pdf ; Bacchus and van Run, original research on constraint-satisfaction search, https://cdn.aaai.org/AAAI/1994/AAAI94-046.pdf . The variable trace and fictional case are original teaching illustrations.

Previous: Chroma subsampling Next: Chunked transfer encoding