Must every complete state satisfy the constraints?

No. Allowing complete but conflicting candidates is central to many local-search formulations.

Is this limited to local search?

No. It is a representation choice, although local search is a common way to explore such states.

Does complete-state mean the system knows everything about the world?

No. It means the candidate's modeled components are specified, not that the environment is fully known.

AI Glossary / Graphs and symbolic AI / Intermediate

Complete-state formulation

Definition

A complete-state formulation represents every search state as a fully specified candidate, rather than a partially constructed candidate. In constraint satisfaction, each state assigns every variable a value, even when some constraints are violated. Search then changes parts of the candidate to find a state that satisfies the goal conditions.

What it means

A problem can often be represented in more than one way. An incremental formulation begins with an incomplete candidate and adds choices. A complete-state formulation starts with all choices present and revises them.

For example, a scheduling state might assign a time to every session, even if two sessions clash. A neighboring state could change one session's time while leaving the others unchanged. The search is trying to repair the candidate, not fill an empty slot in the representation.

Complete describes the state representation, not whether the candidate is correct or the search algorithm is complete. A fully specified state can be invalid, and an algorithm operating on complete states can still fail to find an existing solution.

How it works

Define the variables or components of a candidate and how a full state records their values. Next define the neighborhood: which changes can transform one full candidate into another. A move might reassign one variable, swap two values, or use another problem-specific transformation.

The goal test identifies acceptable states. For a constraint-satisfaction problem, that normally means no violated constraints. An evaluation function may count conflicts or estimate another objective to guide search among states that are not yet solutions.

Local-search methods can then explore the neighborhood. A min-conflicts strategy, for example, selects a conflicted variable and considers a value that minimizes conflicts with the remaining assignment. Other methods use different movement rules.

The formulation does not guarantee that greedy improvement will succeed. Plateaus, local optima, and neighborhood restrictions can prevent progress. The choice of search method, restarts, and stopping conditions must be evaluated separately from the representation.

Three practical examples

1. A timetable repair system begins with a fully assigned but conflicting schedule and changes selected sessions to restore feasibility.

2. A queens-puzzle solver keeps one queen in every column and changes row positions, measuring how many pairs attack one another.

3. A configuration optimizer stores a value for every feature and explores nearby configurations while separately tracking constraint violations and objective quality.

Think of it this way

Think of editing a complete seating chart. Every guest already has a seat, but some placements may violate the organizer's requirements. Improvement comes from changing assignments rather than adding missing names.

The analogy assumes that the final arrangement matters more than the sequence of edits. If intermediate placements have real consequences, those consequences need a richer model.

Worked example

Suppose four training sessions A, B, C, and D each receive slot 1 or slot 2. The constraints are A differs from B, B differs from C, and C differs from D. A state records all four slot choices.

Start with (A=1, B=1, C=1, D=1). This is a complete state with three violated constraints. Change B to 2, producing (1,2,1,1). The first two constraints are now satisfied, while C and D still clash, leaving one violation.

Change D to 2, producing (1,2,1,2). All three constraints are satisfied, so the state is a solution. Every intermediate state remained complete; only its quality changed.

There are 2 to the fourth, or 16, complete states in this small model. The successful two-move repair illustrates one search trajectory. It does not prove that an arbitrary greedy procedure will solve every complete-state problem or that every neighborhood provides access to all solutions.

Illustrative case study

Fictional case: Pinehall Training has a timetable whose every session already has a room and slot. A room closure introduces conflicts. The team uses the existing timetable as the initial complete state and searches for a revised assignment.

Reviewers track both feasibility and the number of changes from the published plan. They discover that minimizing conflicts alone can produce a valid schedule with unnecessary disruption, so they make the secondary objective explicit.

The fictional lesson is that complete-state search can support repair, but the evaluation criteria must reflect the actual task. A candidate with every field filled is neither automatically feasible nor automatically the best revision.

Common misconceptions and mistakes

A complete-state formulation is not the same as complete search. The first describes states; the second concerns whether an algorithm is guaranteed to find a solution when one exists under stated assumptions.

It is also different from full observability. A search representation can specify every modeled variable while the real environment still contains uncertainty or omitted information.

Do not assume that fewer conflicts always means fewer edits, lower cost, or better business outcomes. Those objectives need their own definitions.

Finally, a local move must preserve the intended representation. If each state must assign every variable, a move that simply deletes a value produces a different kind of state unless replacement is part of the same operation.

Business use

Businesses may use complete-state formulations when revising an existing plan or optimizing a fully specified candidate is natural. They are especially helpful when the path of internal edits is not itself the product being delivered.

Document the state, neighborhood, goal test, and evaluation criteria. Keep a clear distinction between a returned candidate and a verified solution. If a search reaches its time limit with conflicts remaining, report that status accurately rather than interpreting a fully populated output as a completed task.

Check your understanding

In the four-session example, is (1,2,1,1) incomplete because it still has a conflict?

Answer: No. All four variables have values, so it is complete. It is not yet a solution because C and D share a slot despite their constraint.

Related terms

Learn next

Represent the same small scheduling task both incrementally and with complete states. Compare what a search move means in each formulation. Then define a repair objective that distinguishes satisfying constraints from minimizing changes to the original plan.

Sources

Primary source consulted: Russell and Norvig, Constraint Satisfaction Problems, complete-state formulation and min-conflicts discussion, https://aima.eecs.berkeley.edu/2nd-ed/newchap05.pdf . The four-session trajectory and fictional timetable case are original teaching examples. Representation completeness is explicitly separated from algorithmic completeness.

Previous: Complete Join Next: Completely randomized design