AI Glossary / Graphs and symbolic AI / Intermediate
No-good
Definition
A no-good is a combination of variable assignments that cannot be extended into a valid solution of a constraint satisfaction problem. A solver can record this combination after discovering a conflict, then avoid repeating it elsewhere in the search. The term is also commonly written “nogood.”
What it means
The important information is the incompatible combination, not a judgment that every individual assignment is bad. Assigning a workshop to Monday may be acceptable, and assigning a particular room may also be acceptable, while choosing both under additional requirements may make the remaining schedule impossible.
A no-good can involve only a small part of a complete assignment. Once that combination is present, filling in unrelated variables cannot rescue it. Remembering the reason for failure therefore allows a solver to prune many future branches rather than rediscover the same contradiction repeatedly.
How it works
During search, a solver assigns values and propagates constraints. If it reaches a contradiction, it analyzes which assignments support the conflict. A soundly derived incompatible set can be stored as a no-good or represented by an equivalent constraint that forbids the combination.
For example, the no-good {X=1,Y=2} can be represented as X≠1 OR Y≠2. If X=1 is later selected, the learned constraint rules out Y=2. If both are already selected, it identifies an immediate conflict.
Learning may support nonchronological backtracking, often called backjumping, and future propagation. Not every no-good is minimal: a set may include unnecessary assignments. Smaller sound explanations can rule out more cases, but finding them and maintaining many learned constraints has a cost. More general forms can also express exclusions or domain restrictions rather than only equalities.
Three practical examples
- Timetabling: remember that a particular combination of room, instructor, and session assignments leaves no valid completion.
- Product configuration: exclude a component combination that violates compatibility requirements, regardless of unrelated options.
- SAT and constraint solving: retain conflict-derived information so that restarts or alternative search branches do not repeat the same impossible choices.
Think of it this way
Think of recording a recipe combination that can never satisfy a stated dietary requirement. The record concerns the combination under those requirements, not a claim that every ingredient is individually unusable.
The analogy has a strict boundary: a no-good requires a sound reason that no valid completion exists. A disappointing trial, slow search, or personal preference is not enough to prove impossibility.
Worked example
Let variables A and B each have domain {1,2}, and let C have domain {1,2}. The constraints are C≠A and C≠B. There is no direct inequality constraint between A and B.
Suppose search assigns A=1 and B=2. Constraint C≠A removes 1 from C's domain. Constraint C≠B removes 2. C now has no possible value, so {A=1,B=2} is a no-good: there is no completion for C.
Store the equivalent constraint A≠1 OR B≠2. Later, if A=1 is selected again, the solver can immediately exclude B=2 without repeating the reasoning through C. The combination {A=1,B=1} remains valid because C=2 satisfies both original constraints. Likewise, {A=2,B=2,C=1} is a solution.
This example shows why the individual assignments are not forbidden. A=1 appears in a valid solution, and B=2 appears in another valid solution. It is their stated combination that fails. Adding an unrelated variable D with any domain does not change that conclusion: choosing a different D cannot restore a value for C. The no-good safely summarizes the conflict across all such extensions.
Illustrative case study
Fictional case: a configurator repeatedly reaches the same incompatibility after customers choose different cosmetic options. The impossible combination concerns the power unit and chassis, while color has no role in the conflict.
The team records a no-good using only the relevant technical selections and provides an explanation identifying the violated requirement. It also ties the learned information to the version of the configuration rules. The fictional case illustrates reusable conflict knowledge, not a measured speedup or a claim about any actual product.
Common misconceptions and mistakes
A failed search attempt is not automatically a no-good. A timeout or incomplete exploration may simply mean the solver has not found a solution yet. Recording such an event as impossibility could incorrectly remove valid solutions.
Similarly, a no-good is not just a low-quality solution. Hard infeasibility differs from an undesirable cost or preference. Optimization solvers can learn information involving objective bounds, but those bounds and their scope need to remain explicit.
Do not confuse a no-good with an unsatisfiable core. A no-good usually describes incompatible assignments under a constraint model; an unsatisfiable core identifies an inconsistent subset of constraints or assumptions. They are related explanation objects with different roles.
Business use
No-good learning can improve repeated configuration, scheduling, and planning searches when similar conflicts arise across branches. Store sufficient provenance to explain why a combination is excluded, especially when business rules change.
Learning also consumes memory and propagation time. Solvers may manage or discard learned information according to their algorithms. For a sound solver, forgetting a redundant learned constraint need not remove valid solutions; it can simply cause repeated work. Retaining an invalid learned constraint is much more serious because it can suppress feasible answers.
People also ask
Must a no-good include every variable?
No. A partial assignment is enough if no complete solution can contain it.
Is every no-good minimal?
No. Removing unnecessary assignments may produce a smaller no-good, but minimality is an additional property.
What would an empty no-good mean?
It means the problem itself has no solution, because even the empty assignment cannot be extended to one.
Check your understanding
A solver proves {Room=A,Time=10} is a no-good. Does that prove Room=A can never be used?
Answer: No. It forbids that room-time combination; Room=A may be valid at another time.
Related terms
- Constraint satisfaction
- Backjumping
- conflict learning
- learned clause
- domain wipeout
- propagation
- unsatisfiable core
- backtracking
Learn next
derive a no-good from a small domain-wipeout example, then translate it into a disjunction of negated assignments. Compare keeping the whole search prefix with keeping only the assignments needed for the conflict.
More in Graphs and symbolic AI
- Negation - Negation is the logical operation that states that a proposition is not true.
- Network Simplex - Network simplex is an optimization algorithm for finding a minimum-cost flow through a network while satisfying supply, demand, and capacity constraints.
- Newton-Raphson - Newton-Raphson is an iterative numerical method for finding a root of a function: an input x for which f(x)=0.
- No-regret learning - No-regret learning is a way of making repeated decisions so that the learner's average performance approaches that of a specified hindsight benchmark.
- Node - A node is an individual element of a graph or tree, often representing an entity, state, variable, or operation. Connections between nodes are called edges.
- Noise-based logic - Noise-based logic is a research approach in which distinguishable noise signals represent logical values and specially designed operations manipulate those...
Sources
Katsirelos and Bacchus, “Generalized NoGoods in CSPs,” defines standard and generalized nogoods and explains their use in learning and propagation: https://cdn.aaai.org/AAAI/2005/AAAI05-062.pdf
The three-variable calculation and fictional configurator are original teaching examples. Claims about learned information assume sound derivation under the stated constraint model.
Previous: Nguyen-Wainwright-Jordan lower bound Next: No-information