Does the method always jump over several variables?

No. If the most recent decision is implicated, the backjump may be the same step that ordinary backtracking would take.

Why combine conflict sets?

A failure deeper in the search can explain why a locally acceptable value has no successful continuation. Combining reasons preserves that information.

Does backjumping prove the entire problem impossible?

A particular jump only addresses a failed branch. Global infeasibility requires an appropriately complete search or another valid proof.

AI Glossary / Graphs and symbolic AI / Intermediate

Conflict-directed backjumping

Definition

Conflict-directed backjumping is a constraint-search method that uses explanations of failure to choose where to backtrack. When all values for a variable fail, it returns to the most recent earlier decision implicated in those failures, potentially skipping unrelated decisions. It also carries conflict information backward so failures discovered deeper in the search influence later backtracking choices.

What it means

Ordinary backtracking revisits decisions in reverse chronological order. That policy is simple, but the last decision may have nothing to do with the current failure.

Conflict-directed backjumping records earlier variables whose current assignments explain why a branch cannot be completed. It uses these conflict sets to identify a more relevant decision to change.

The directed part matters because explanations can include failures beyond the current variable's immediate constraints. A value may be locally acceptable yet lead to an impossible continuation. Accumulating the reasons for those deeper failures lets the search recognize that changing an unrelated intervening variable would not help.

How it works

The solver tries values for a variable and records why rejected values cannot work. A direct rejection can come from a constraint with an earlier assignment. A deeper rejection can return a conflict explanation from a later variable.

Once every value has failed, the solver selects the latest assigned variable in the accumulated conflict set as the backjump target. It transfers the remaining relevant reasons to the target's conflict information, excluding the target itself from the transferred set.

Assignments made after the target are undone as required by the algorithm, and their domain changes must be restored consistently. The target then tries another alternative. If it also exhausts its values, the process repeats using its accumulated explanation.

Correct bookkeeping is essential: skipping decisions is justified by a sound reason for failure, not by a guess that they look unimportant. The method changes search order and avoids some repeated work; it does not remove the underlying difficulty of constraint satisfaction.

Three practical examples

1. A timetable search returns past an unrelated elective allocation when a later conflict is explained by earlier room and time choices.

2. A product-configuration solver propagates reasons from an impossible downstream component choice to the earlier options that created the incompatibility.

3. A solver developer compares search traces to determine whether recorded explanations permit useful backjumps beyond immediate constraint neighbors.

Think of it this way

Think of troubleshooting a sequence of choices by following the explanation of the blockage back to the relevant decision. If a later failure reveals that an earlier combination is impossible, revisiting every unrelated choice between them wastes effort.

The analogy is limited because a solver needs formal reasons tied to the current assignments. Human intuition that a decision is irrelevant is not enough to justify pruning a search branch.

Worked example

Consider variables A, B, U, C, and D, all with domain {1, 2}, assigned in that order. The only constraints are C different from A, D different from B, and D different from C. U is unrelated.

Suppose A = 1, B = 1, and U = 1. At C, value 1 is rejected because of A, so try C = 2. Now D has no legal value: 1 conflicts with B and 2 conflicts with C. Its conflict set is {B, C}.

The search returns to C, the more recent implicated variable. C's direct reason already includes A. Adding D's reasons except C gives the accumulated set {A, B}. Since C has exhausted its values, the search backjumps to B and skips U as a revision target.

Changing B to 2 allows C = 2 and D = 1, with U arbitrary. The interesting point is that B has no direct constraint with C, yet it belongs in C's accumulated explanation because of the failed continuation through D.

This example assumes the stated search order and value trials. Other propagation methods may detect the same incompatibility earlier.

Illustrative case study

Fictional case: Linden Scheduling builds a small solver demonstration using the five-variable problem. Its first implementation records only the immediate neighbors of a failed variable and loses the reason passed back from D.

The reviewers trace each rejected value and compare the accumulated set at C with the expected {A, B}. They correct the explanation transfer and verify that U is no longer treated as the next decision requiring revision.

The case illustrates the difference between direct and propagated reasons. It does not report measured speedups or suggest that this method is always the best solver strategy.

Common misconceptions and mistakes

Do not confuse conflict-directed backjumping with simply returning to an arbitrary earlier variable. A sound conflict explanation must justify the jump.

Do not limit every explanation to immediate constraint neighbors. Failures below a variable can introduce earlier decisions that are relevant through a longer chain of constraints.

Do not confuse explanation transfer with permanent constraint learning. The latter stores derived restrictions for reuse across search branches. Also avoid keeping explanations tied to assignments that have already been changed without the algorithm's required updates.

Business use

For business teams, the technique helps explain why a solver may revise an earlier choice instead of the most recent one. This helps when decisions involve independent subproblems or delayed consequences.

Performance still depends on variable ordering, propagation, problem structure, and explanation overhead. Evaluate the complete solver on representative cases. If explanations are exposed to users, show the implicated values and constraints so a context-specific failed combination is not mistaken for a universal prohibition.

Check your understanding

C has no direct constraint with B, but every continuation from a tried C value fails because of B. Can B enter C's conflict information?

Answer: Yes. Propagated explanations capture deeper failures, which is a central feature of conflict-directed backjumping.

Related terms

Conflict set
Chronological backtracking
Constraint satisfaction
Constraint learning
propagation
domain restoration
nogood
search ordering

Learn next

Trace every rejected value in the worked example and record its reason before combining sets. Then compare conflict-directed backjumping with forward checking and learned nogoods to separate earlier failure detection, targeted revision, and reusable knowledge.

Forward checking

Sources

Russell and Norvig, Artificial Intelligence: A Modern Approach, Constraint Satisfaction Problems: https://aima.cs.berkeley.edu/2nd-ed/newchap05.pdf . The primary chapter's accumulated-conflict and backjump-update discussion was consulted. The trace and fictional case are original; no universal performance advantage is claimed.

Previous: Confirmation bias Next: Conflict set