Constraint Satisfaction Problem: Concepts, a Worked Search Trace and Exam Traps

In a Constraint Satisfaction Problem, domains shrink as constraints propagate, and a locally legal choice can still create a later dead end. A precise model uses variables, domains and constraints; propagation removes unsupported values before backtracking explores what remains. In the four-exam schedule, the first branch fails when D loses every value, while the chain CSP becomes arc consistent at X=1, Y=2 and Z=3.

Constraint Satisfaction Problem: variables, domains and constraints

A CSP is (X, D, C): X = {X1, ..., Xn} is a finite variable set, D(Xi) lists values allowed for Xi, and C specifies permitted combinations.

A partial assignment values some variables; a complete one values all. A consistent assignment violates no constraint. A solution is complete and consistent.

Let X = {A, B}, D(A) = D(B) = {1,2,3}, and A != B. {A=1} is partial and consistent, {A=1,B=1} is complete but inconsistent, and {A=1,B=2} is a solution. A domain value is a choice, not a probability or heuristic score.

Hard constraints hold in every solution. Soft constraints express preferences or penalties in optimisation. A hard-constraint CSP has no objective function unless an optimisation criterion is added.

CSP constraint graphs and constraint types

A unary constraint concerns one variable, such as A != 3; a binary constraint concerns two, such as B < D; a global constraint has a larger scope, such as AllDifferent(A,B,C). Here that global rule becomes A != B, A != C, and B != C.

The constraint graph has vertices A,B,C,D and edges A-B, A-C, B-C, B-D, and C-D, but no A-D edge. In Graph Theory: Euler, Hamiltonian, Coloring for GATE CS, colouring is a CSP where vertices are variables, colours form domains, and adjacent vertices differ. The directed precedence rule B < D makes scheduling more than colouring.

A constraint is a relation over its scope. On {1,2,3}, B < D permits only (1,2), (1,3), and (2,3). Propositional and Predicate Logic: Truth Tables, Quantifiers helps with logical conditions, while a CSP also requires variables, domains, and scopes.

Constraint Satisfaction Problem worked example: schedule four exams

Place exams A, B, C, and D in slots {1,2,3}, with every domain initially {1,2,3}. Constraints are A != B, A != C, B != C, B < D, and C != D: A, B, and C clash pairwise, B precedes D, and C clashes with D. The unpruned space has 3^4 = 81 complete assignments.

Use variable order A,B,C,D and value order 1,2,3. Try A=1. Reject B=1, then take B=2. Reject C=1 because of A and C=2 because of B, so take C=3. Now D=1 and D=2 violate B < D; D=3 violates C != D. Backtrack to B=3; no D value exceeds 3, so A=1 fails.

Next try A=2, then B=1. Reject C=1 because of B and C=2 because of A, so set C=3. Choose D=2: 1 < 2, 3 != 2, and all five constraints hold. The first solution is (A,B,C,D) = (2,1,3,2). A and D can share slot 2 because no constraint joins them.

The solutions are (2,1,3,2), (3,1,2,3), and (3,2,1,3). First-solution search stops there.

Forward checking and arc consistency: prune before search

Forward checking detects failure earlier. After A=1, remove 1 from B and C, giving D(B)=D(C)={2,3}. After B=2, remove 2 from C to get D(C)={3}, and apply B < D to get D(D)={3}. Assigning C=3 removes 3 from D through C != D. The empty domain appears before D is assigned.

For a binary constraint, an arc is consistent when every Xi value has support in the current domain of Xj. Take D(X)=D(Y)=D(Z)={1,2,3}, X < Y, and Y < Z.

An AC-3-style revision proceeds as follows:

1. Remove 3 from X because no Y value is greater.

2. Remove 1 from Y because no X value is smaller.

3. Remove 3 from Y because no Z value is greater, leaving Y={2}.

4. Revisit X. Only X=1 has support in Y={2}, so X={1}.

5. Revisit Z. Only Z=3 has support from Y={2}, so Z={3}.

The fixed point is X=1,Y=2,Z=3. Forward checking follows an assignment's immediate effect; arc consistency repeatedly prunes unsupported values between unassigned variables too. Neither changes the solution set. A non-empty arc-consistent network need not have a solution, although this chain ends in singletons.

CSP heuristics: MRV, degree and least-constraining value

Minimum Remaining Values (MRV) chooses the smallest current domain. Degree breaks a tie by selecting the variable with most unassigned neighbours. Least Constraining Value (LCV) orders values by how few neighbour-domain values they remove. MRV and degree choose variables; LCV orders values.

After A=2, forward checking gives D(B)=D(C)={1,3} and D(D)={1,2,3}. MRV ties B and C, so fixed order selects B. B=3 empties D; B=1 leaves D(C)={3} and D(D)={2,3}, so LCV tries B=1. MRV then selects C, after which D becomes {2}.

Heuristics can expose failure earlier and reduce nodes. They do not change legality, complete an incomplete solver, or remove the exponential worst case.

CSP search, local repair and game-playing boundaries

Backtracking is depth-first search over partial assignments. A successor assigns one variable, checks prune inconsistent nodes, and a complete consistent node passes the goal test. With n variables and maximum domain size d, exhaustive search has up to d^n leaves. Assignment storage is O(n), apart from domains and constraints. Binary-CSP AC-3 commonly takes O(e d^3) for e directed arcs, subject to implementation details.

Min-conflicts starts with a complete, possibly inconsistent assignment, selects a conflicted variable, and moves it to a value minimising conflicts. It can help with large satisfiable CSPs, but failure does not prove unsatisfiability. Exhaustive finite backtracking is complete.

A CSP restricts assignments through relations. Game playing adds alternating agents, adversarial choices, utilities, and a game tree. A game position may contain a CSP, but backtracking is not minimax, and MRV is not an opponent model.

Constraint Satisfaction Problem exam patterns and common traps

Typical tasks ask you to identify (X,D,C), classify an assignment, count the naive space, trace forward checking, perform REVISE, apply MRV or LCV, or distinguish CSP from game-tree search.

Use these four checks:

• Four variables with three values each give 3^4=81 complete assignments before constraints.

• Under B<D, (B,D)=(2,3) is supported, while (3,2) is not.

• After A=2,B=1, propagation gives C={3} and then D={2}.

• For X<Y<Z over {1,2,3}, arc consistency ends at (1,2,3).

Traps include inventing a constraint for a missing edge, calling a complete inconsistent assignment a solution, using MRV to choose a value, equating forward checking with arc consistency, and declaring unsatisfiability after one failed branch. For broader practice, the GATE CS Exam Preparation page groups subject and exam-preparation resources.

Constraint Satisfaction Problem in short and the next step

Recall: write (X,D,C); draw scopes or a constraint graph; propagate restrictions; choose a variable with MRV plus degree; order values with LCV; backtrack on an empty domain; accept only a complete consistent assignment. The first solution remains (2,1,3,2).

Self-test: add A != D. The first solution fails because A=D=2. Solutions (3,1,2,3) and (3,2,1,3) also fail because A=D=3. The strengthened instance is unsatisfiable.

Use AI & ML for Placements for broader AI learning, or GATE Guidance by Sanchit Sir when you want a structured exam-preparation path. A useful final check is to redraw each diagram, then identify the exact assignment that empties D's domain in the failed branch.