Does a CSP always have one solution?

No. It can have no solutions, one solution, or many solutions.

Must every domain contain numbers?

No. A domain may contain names, categories, components, or other suitable values.

Can a CSP choose the cheapest solution?

An optimization extension can minimize cost over feasible assignments. The basic satisfaction question alone does not define cheapest.

AI Glossary / Graphs and symbolic AI / Beginner

Constraint satisfaction problem

Definition

A constraint satisfaction problem, or CSP, describes a task using variables, the possible values of those variables, and rules that acceptable combinations must obey. Solving the problem means assigning a value to every variable so that all the constraints hold. It is a general framework for finding feasible arrangements.

What it means

The variables represent decisions, such as which room hosts each meeting. Their domains contain permitted choices, such as available rooms. Constraints express relationships: two simultaneous meetings cannot occupy the same room, and a particular meeting needs a room with sufficient capacity.

A solution is complete and consistent. Complete means every required variable has a value. Consistent means the assignments violate none of the constraints. A partial arrangement may be consistent so far without being extendable to a full solution.

The basic CSP asks whether an acceptable arrangement exists and, usually, requests one. Selecting the cheapest or most convenient acceptable arrangement adds an objective and turns the task into a constraint optimization problem. Feasibility and preference are different questions, even when a software package supports both.

How it works

Start by translating the operational task into a model. Identify decisions, define their domains, and state constraints precisely. A constraint can involve one variable, a pair, or several variables together.

A solver can reduce domains by propagating constraints, then select a variable and try a value. If that choice creates a contradiction, the solver backtracks and tries another branch. Variable ordering, specialized constraints, and the structure of the model can greatly affect the amount of search.

Another approach starts with a complete but possibly invalid assignment and repairs violations. Such local search can find useful solutions, but failure to find one within a time limit does not establish that none exists.

Whatever the method, check the returned arrangement against the original constraints. A mathematical solution can still be unusable if the model omitted a real requirement or used outdated availability information.

Three practical examples

1. A training coordinator assigns workshops to time slots while preventing an instructor from teaching two workshops simultaneously.

2. A product configuration service chooses compatible components, respecting connector types, capacity limits, and required accessories.

3. A puzzle application assigns digits to cells subject to row, column, and region restrictions. The same modeling ideas can support less playful allocation tasks.

Think of it this way

Think of seating guests using named cards, available chairs, and seating rules. The cards are variables, the possible chairs are domains, and the rules determine acceptable combinations. An arrangement is finished only when every card has a suitable chair.

The analogy has limits. CSP variables need not represent physical objects, and their domains need not be small finite lists. Also, the solver knows only the rules that the model explicitly represents; it cannot infer every unspoken social preference.

Worked example

Suppose three tasks A, B, and C must occupy three distinct slots numbered 1, 2, and 3. Task A must occur before task B. Each variable initially has domain {1, 2, 3}.

Without constraints, there are 3 × 3 × 3 = 27 complete assignments. Requiring distinct slots leaves six permutations. Adding A < B leaves exactly three solutions, written as (A, B, C):

(1, 2, 3), (1, 3, 2), and (2, 3, 1).

The assignment (2, 1, 3) uses distinct slots but violates the ordering constraint. The partial assignment A = 3 looks permissible when considering its domain alone, yet cannot be completed because B would need a later slot.

Any of the three solutions satisfies the stated problem. Calling one best would require an additional criterion, such as preferring an earlier slot for C. These counts are a teaching calculation, not a solver benchmark.

Illustrative case study

Fictional case: North Pier Learning needs a workshop timetable. Its first model assigns rooms and times and prevents instructor clashes. A feasible timetable is returned, but a coordinator notices that equipment must move between buildings between two sessions.

The team adds a travel-time restriction and reruns the model. It also introduces a separate preference for avoiding late sessions. The case illustrates two responsibilities: representing all mandatory requirements and distinguishing those requirements from desirable outcomes. It does not claim that formal modeling automatically discovers missing rules.

Common misconceptions and mistakes

Do not equate a low number of violations with a solution when every constraint is mandatory. One remaining violation is still a failure of feasibility.

Do not interpret a search timeout as proof of impossibility. A complete method must finish the relevant reasoning to justify that conclusion.

Avoid assuming all constraints can be replaced by pairwise restrictions without a careful transformation. Some relationships naturally involve several variables.

Finally, do not assume a CSP assignment is automatically an executable action plan. If sequence, duration, resources, or changing state matter, those features must be represented appropriately.

Business use

Businesses can use CSPs to express scheduling, allocation, and compatibility decisions in a form that supports automated checking. Their value depends on clear requirements as much as on algorithm choice.

Maintain ownership for each constraint, test sample acceptable and unacceptable cases, and distinguish infeasible models from incomplete searches. When users challenge a result, an explanation of the binding restrictions is often more useful than simply presenting a different arrangement.

Check your understanding

A timetable assigns every workshop, but two workshops require the same instructor at the same time. Is it a solution?

Answer: No, assuming instructor availability is a constraint. The assignment is complete but inconsistent. Both completeness and satisfaction of all constraints are required.

Related terms

Domain
Constraint propagation
Constraint graph
Global constraint
Local search
constraint
backtracking
constraint optimization

Learn next

Study domain filtering and backtracking next. Build a three-variable example, enumerate its assignments, and mark which constraints reject each invalid assignment. Then add one preference and observe how the question changes from finding any feasible solution to comparing feasible solutions.

Domain

Sources

Primary source: Russell and Norvig, Artificial Intelligence: A Modern Approach, chapter on constraint satisfaction: https://aima.cs.berkeley.edu/2nd-ed/newchap05.pdf

The source establishes the variables, domains, constraints, and solution framework. The scheduling counts, fictional case, and explanatory examples are original teaching material.

Previous: Constraint satisfaction Next: Constraint weighting