AI Glossary / Computer vision and multimodal AI / Intermediate

Constraint satisfaction

Definition

Constraint satisfaction is the task of assigning values to variables so that all specified restrictions are met. A constraint satisfaction problem defines the variables, their allowed values and the relationships that a valid assignment must satisfy, without necessarily requiring the best assignment according to an objective.

What it means

A timetable might assign rooms and times to classes while preventing room conflicts and respecting availability. Many assignments are possible, but only some obey every rule. Constraint satisfaction provides a structured way to describe and search for those valid combinations. It appears in scheduling, puzzles, configuration, planning and parts of computer vision. The distinction between finding a valid solution and optimizing a preference is important. If the task also asks for the cheapest or fastest valid solution, it becomes a constrained optimization problem or an extended formulation with an objective.

How it works

Each variable has a domain of possible values. Constraints can involve one variable, pairs or larger groups. A solver may choose a variable, try a value and propagate the consequences by removing incompatible options from other domains. If an assignment leads to contradiction, it backtracks and tries an alternative.
Heuristics influence which variables and values are tried first. Consistency techniques can detect some contradictions before a complete assignment is built, reducing unnecessary search. They do not necessarily solve every problem without branching. If every possibility is ruled out, the system is unsatisfiable under the stated domains and constraints. The model must accurately represent the real requirements for a mathematically valid solution to be practically useful.

Three practical examples

• A training center assigns instructors to sessions while avoiding overlapping commitments and respecting required qualifications.
• A product configurator checks whether selected components can work together before accepting a proposed configuration.
• A visual interpretation system uses geometric compatibility constraints to eliminate impossible combinations of candidate feature matches across images.

Think of it this way

Think of seating guests at a dinner while obeying a list of conditions about who can share a table and how many seats are available. Every seating decision narrows the remaining choices. The analogy is limited because formal problems require precise domains and rules; vague preferences must be clarified or represented as objectives rather than silently treated as absolute constraints.

Worked example

Let three variables A, B and C each have domain {red, green, blue}. Require all three values to differ, fix A=red and prohibit B=blue. Since B cannot be red because of A and cannot be blue by its own restriction, B must be green. C must then be blue. The valid assignment is (red,green,blue).
If a new requirement also prohibits C=blue, no assignment can satisfy this exact set of constraints. A solver should report that conflict rather than quietly ignoring a rule. This small example shows propagation from local restrictions to a complete conclusion; larger problems may still require substantial search.

Illustrative case study

Fictional example: Juniper Training builds a weekly workshop timetable. The first model finds no solution because one instructor is required for two sessions that are both fixed to the same time. The team checks the source requirements and learns that one time was only a preference. It moves that preference into an optimization criterion while keeping genuine availability limits hard. The resulting process distinguishes a modeling conflict from a solver failure and preserves a record of which requirements may be relaxed.

Common misconceptions and mistakes

A constraint is not automatically a preference: hard constraints define validity, while soft constraints or objectives express trade-offs. Finding one solution does not prove it is best. Failure to find a solution before a timeout is not the same as proving unsatisfiability. Constraint propagation can reduce domains without resolving the whole problem. Adding more rules can either help prune search or make the model infeasible. Finally, a mathematically consistent assignment can still be operationally wrong if an important real-world requirement was omitted.

Business use

Businesses should classify requirements carefully and involve the people who own them. Record domains, hard restrictions and preferences separately. Test the model on known feasible and infeasible examples, and explain how conflicts are reported. A production system should distinguish a valid solution, a proven impossibility and an unfinished search. Keep an auditable record of any approved relaxation. This makes automated planning more useful because users can understand whether a problem lies in available resources, contradictory requirements or the search method's current limits.

People also ask

Is constraint satisfaction always an optimization task?

No. Basic constraint satisfaction asks for any assignment meeting all restrictions. Optimization adds a criterion for comparing valid assignments.

What does unsatisfiable mean?

No assignment within the declared domains meets every constraint. It refers to the model as stated, not necessarily every possible redesign of the real situation.

Can a solver explain conflicting rules?

Some systems support conflict explanations, but the detail and guarantees depend on the formulation and solver.

Check your understanding

A solver stops after a time limit without a valid schedule. Has it necessarily proved that no schedule exists?

Answer: No. The search may simply be incomplete. Proven infeasibility and failure to find a solution within available resources are different outcomes.

Related terms

• Constraint satisfaction problem
• Domain
• Constraint propagation
• Satisfiability
• Scheduling
• Constrained optimization
• backtracking

Learn next

Model a small puzzle using variables, domains and constraints, then trace how one assignment removes other options. Learn backtracking and consistency checks before adding preferences or interpreting solver status in a real planning workflow.

More in Computer vision and multimodal AI

• Connected-component labeling - Connected-component labeling assigns a distinct label to each connected group of foreground pixels in an image.
• Conservative vector field - A conservative vector field is a vector field that can be expressed as the gradient of a scalar potential on its domain.
• Constrained least squares - Constrained least squares finds model parameters that minimize a sum of squared residuals while obeying specified restrictions.
• Content-aware fill - Content-aware fill is an image-editing technique that replaces a selected region with content chosen or synthesized to fit the surrounding image.
• Content-based image retrieval - Content-based image retrieval, or CBIR, finds images using information extracted from their visual content.
• Content-preserving warp - A content-preserving warp is a spatially varying image transformation that balances desired movement against distortion of visible structures.

Sources

Carnegie Mellon University, Constraint Satisfaction Problems course notes: https://www.cs.cmu.edu/~15281/coursenotes/constraints/ Primary university teaching excerpts consulted; full solver-specific and editorial review remain pending. The three-variable example and fictional timetable are original.

Previous: Constraint propagation Next: Constraint satisfaction problem