Does a conflict set always contain the last assigned variable?

No. The last variable may be irrelevant to the failure, which is why backjumping can skip it.

Is a conflict set necessarily minimal?

No. A correct explanation can include more reasons than strictly necessary, depending on how the solver records and combines them.

Is tracking conflict sets the same as constraint learning?

No. Tracking reasons guides search. Constraint learning additionally stores derived restrictions that can prevent repeated incompatible choices.

AI Glossary / Graphs and symbolic AI / Intermediate

Conflict set

Definition

A conflict set records earlier assignments implicated in a failure during constraint-satisfaction search. It helps a solver identify which decisions may need revision when a variable has no acceptable value or a branch has no solution. In conflict-directed backjumping, this information guides the search past irrelevant recent decisions toward an earlier decision responsible for the failure.

What it means

A constraint-satisfaction problem assigns values to variables while respecting stated relationships. A search can reach a point where every candidate value for the next variable conflicts with earlier choices.

Ordinary chronological backtracking revisits the most recent choice, even when changing it cannot address the failure. A conflict set provides a reason to revisit a more relevant decision. Its entries refer to the current search context; the same variable with another value may not cause the same problem.

The term also appears in rule-based systems for a set of eligible rule activations. This entry uses the constraint-search meaning associated with the supplied AI glossary, rather than that different rule-engine sense.

How it works

While checking candidate values, the solver tracks which earlier assignments rule them out. If all candidates fail, their recorded reasons can form a conflict set for the current variable.

Simple backjumping returns to the most recently assigned variable in that set. The relevant meaning of recent is the search's decision order, not the alphabetical order of variable names.

Conflict-directed backjumping can carry reasons backward from deeper failures. When a variable exhausts its alternatives, its accumulated conflict information is combined with that of the earlier variable selected for revision, excluding the selected variable itself from the transferred reasons.

The exact bookkeeping depends on the solver and its propagation scheme. Reasons must remain sound when assignments are undone or domains are restored. A conflict set need not be the smallest possible explanation, and recording a failure reason is distinct from permanently learning a reusable constraint.

Three practical examples

1. A scheduling solver identifies earlier slot choices that leave a later task with no permitted slot, avoiding revision of an unrelated task first.

2. A configuration tool records which selected options eliminate all values of another component, making the relevant combination of decisions visible.

3. A search implementation uses failure explanations to compare chronological backtracking with conflict-directed methods on the same constraint problem.

Think of it this way

Think of a conflict set as a short list of earlier decisions implicated in a blocked choice. If an unrelated decision was made last, revisiting it first is unlikely to remove the block.

The analogy has limits: the set is a formal search explanation under particular assignments, not a judgment of human blame. Its validity depends on the encoded constraints and the solver's reasoning.

Worked example

Consider variables A, B, U, and X, each with domain {1, 2}. The only constraints are X different from A and X different from B. Variable U is unrelated to the others.

Use decision order A, B, U, X. Suppose the current assignments are A = 1, B = 2, and U = 1. When trying X, value 1 fails because of A, and value 2 fails because of B. Thus X has no legal value, with conflict set {A, B}.

Chronological backtracking would revisit U, but changing U from 1 to 2 cannot make either value of X legal. Backjumping instead targets B, the most recent decision in the conflict set.

If B changes to 1, X can take 2. U can take either value because it is unconstrained. Assignments after the backjump target may be undone and reconsidered according to the solver's implementation; the point is to avoid treating U as the cause of this failure.

The conflict concerns A = 1 together with B = 2 in this search context. It does not mean that variables A and B are inherently incompatible or that the full problem has no solution.

Illustrative case study

Fictional case: Spruce Scheduling uses the four-variable problem as a debugging exercise. Its trace repeatedly changes U after X fails, and the team initially interprets the repeated failures as evidence that the whole problem is impossible.

A reviewer traces both rejections and identifies {A, B}. The revised trace returns to B and finds the compatible assignment described above. The explanation accompanies the test case to support future review.

This case illustrates targeted search, not measured performance gains for a production scheduler.

Common misconceptions and mistakes

Do not interpret a conflict set as proof that the entire constraint problem is unsatisfiable. It may only explain failure under the current partial assignment.

Do not assume every recorded member is indispensable. A solver can use a sound but nonminimal set of reasons.

Do not retain stale reasons blindly after backtracking. Changes in assignments and restored domain values affect which explanations remain applicable. Also distinguish a set of implicated variables from a learned nogood that explicitly records an incompatible combination of values.

Business use

For business teams, conflict information can help explain why a proposed configuration or schedule cannot be extended. It can focus a review on relevant decisions instead of presenting only a generic no-solution message.

The explanation must be interpreted at the right scope. A local search failure, a globally infeasible model, and a computation that stopped before finding a solution are different outcomes. If explanations are shown to users, include the affected assignments and constraints so a variable name alone does not imply an overly broad restriction.

Check your understanding

X has no legal value because of A and B, while the most recent variable U has no relevant constraints. What does the conflict set suggest?

Answer: Revisit the most recent implicated decision, B in the stated order, rather than expecting a change to U to resolve X's failure.

Related terms

Learn next

Trace the worked example using chronological backtracking and then backjumping. Next, study how deeper failure reasons are merged in conflict-directed backjumping and how learned nogoods preserve useful information across different search branches.

Sources

Russell and Norvig, Artificial Intelligence: A Modern Approach, author-hosted chapter on Constraint Satisfaction Problems: https://aima.cs.berkeley.edu/2nd-ed/newchap05.pdf . The conflict-set and backjumping discussion was consulted. The four-variable example and fictional trace are original, with the constraint-search scope stated explicitly.

Previous: Conflict-directed backjumping Next: Conformal prediction