Can a complete assignment be wrong?

Yes. It can assign every variable while violating constraints or using inappropriate values if domain validation was omitted.

Is a partial assignment always useless?

No. Partial assignments are central to many search methods and can expose conflicts before every variable is assigned.

Does a solution have to be complete?

Under the standard constraint-satisfaction definition, a solution is a complete assignment satisfying all constraints.

AI Glossary / Graphs and symbolic AI / Beginner

Complete assignment

Definition

A complete assignment gives a value to every variable in a specified problem. In a constraint-satisfaction problem, completeness means that no problem variable remains unassigned. A complete assignment is a solution only if its values also satisfy all the constraints; filling every variable does not by itself establish correctness or feasibility.

What it means

A constraint-satisfaction problem defines variables, a domain of possible values for each variable, and constraints on permitted combinations. An assignment records selected values for some or all of those variables.

A partial assignment leaves at least one variable without a value. A complete assignment covers the entire defined variable set. These terms describe coverage, while consistency describes whether the assigned values violate the relevant constraints.

This distinction is useful because a candidate can be complete but inconsistent, or partial and consistent so far. Even a partial assignment that has not yet violated a checked constraint may fail to extend to any complete solution. Coverage, local acceptability, and eventual solvability are separate properties.

How it works

To check completeness, compare the assignment's variable keys with the problem's variable set. Every required variable must have one selected value from its domain. A list of remaining possibilities for a variable is not the same as selecting its value.

Then evaluate the constraints. A complete domain-respecting assignment that satisfies all of them is a solution to the satisfaction problem. If the task also contains an objective, such as minimizing cost, a feasible complete assignment may still be inferior to another solution.

Different search methods use complete assignments differently. Backtracking commonly builds a partial assignment one variable at a time while rejecting conflicts. Local search can start with a complete assignment that violates constraints and repeatedly change values to reduce those violations.

Completeness is relative to the model. Assigning every variable in an incomplete business model does not establish that every real-world requirement has been represented.

Three practical examples

1. A scheduler checks that every defined session has a room and time assignment before separately checking capacity and overlap constraints.

2. A product configurator distinguishes an unfinished configuration from a fully specified configuration whose feature combination is incompatible.

3. A Boolean satisfiability tool evaluates a truth assignment covering all its variables and checks whether every clause is satisfied.

Think of it this way

Think of a form whose required boxes are all filled in. That makes the form complete in a coverage sense, but the entries can still conflict with one another or violate the form's rules.

The analogy does not mean that arbitrary text counts as a value. A formal assignment must respect the variable's permitted domain, and the model must define which fields are actually required.

Worked example

Suppose three adjacent display panels form a line: A-B-C. Each panel can be colored Red or Blue. The constraints require A to differ from B and B to differ from C; A and C do not touch. There are 2 cubed, or 8, complete color assignments before constraints are checked.

{A=Red, B=Blue} is partial because C has no assigned color. It violates neither constraint involving only assigned variables. Choosing C=Blue makes the assignment complete but creates a conflict between B and C.

Choosing C=Red instead gives {A=Red, B=Blue, C=Red}, a complete assignment satisfying both constraints. Reversing every color produces the other solution, {A=Blue, B=Red, C=Blue}. The remaining six complete assignments violate at least one adjacency constraint.

By contrast, {A=Red, B=Red} is already inconsistent before C is assigned. No choice for C can repair that particular conflict without changing an earlier value. The example separates coverage from consistency and shows why checking partial assignments can avoid unnecessary work.

Illustrative case study

Fictional case: Maple Events builds a scheduling dashboard that marks a plan ready when every session has a slot. During review, the team discovers that two sessions requiring the same exclusive room overlap.

The developers separate coverage from constraint validation. The dashboard first confirms that the required variables are assigned, then checks room use and other modeled restrictions. A fully filled but conflicting plan receives a different status from an unfinished plan.

The team also reviews whether its variable set captures all required decisions. This fictional case illustrates that formal completeness is helpful only when the model and the user-facing interpretation are aligned.

Common misconceptions and mistakes

Complete does not mean consistent. A full assignment can violate one or many constraints.

Consistent so far does not always mean extendable. An apparently acceptable partial choice can leave no compatible values for the remaining variables.

A domain reduced to one possible value may imply a choice, but an implementation must define when that value becomes part of the explicit assignment. Avoid mixing solver-internal conventions with an unexplained user-facing status.

Finally, complete does not mean optimal. In an optimization problem, several feasible complete assignments can have different objective values. Establishing optimality requires more than finding the first fully specified candidate.

Business use

For business systems, keep completion, feasibility, and optimization status distinct. Users need to know whether information is missing, constraints conflict, or a feasible plan is still being improved.

Document the variable set and the meaning of any optional or not-applicable values. If a variable can legitimately be not applicable, represent that explicitly in the model rather than silently treating an omitted value as assigned. Validate the final candidate against the current constraints, particularly when requirements can change while a solver is running.

Check your understanding

A model has four variables, and three are assigned consistently. Is the assignment complete?

Answer: No. One variable remains unassigned. The current choices may be consistent so far, but completeness requires a value for every defined variable.

Related terms

Learn next

Create a small problem with three variables and list its complete assignments. Mark which satisfy the constraints. Then inspect partial assignments and identify one that has no valid completion, explaining why local progress does not always guarantee a solution.

Sources

Primary source consulted: Russell and Norvig, Constraint Satisfaction Problems, definitions and search formulations, https://aima.eecs.berkeley.edu/2nd-ed/newchap05.pdf . The panel-coloring example and fictional scheduling case are original teaching illustrations; completeness is explicitly distinguished from consistency and optimality.

Previous: Complementizers Next: Complete data