Constraint Satisfaction Problem (CSP)

Assign each variable a value from its domain so that all constraints are satisfied.

What's a CSP?

A CSP is defined by three things:

• Variables X = {x₁, x₂, …, xₙ}
• Domains D_i = set of allowed values for x_i (often integers, but not necessarily)
• Constraints — relations restricting which value combinations are allowed

Example: 5 variables, each with a different domain, 8 binary constraints:

D[1] = {2, 4, 6, 0}
D[2] = {19, 5, 9, 20}
D[3] = {3, 7, 8, 0}
D[4] = {1, 7}
D[5] = {-3, -6, -1}

C(1,2): x1 + x2 < 3
C(1,3): x1 + x3 = 5
C(1,4): x1 + x4 ≥ 7
…

Classic CSPs

Graph coloring

Variables = vertices. Domain = colors. Constraint per edge: endpoints must have different colors.

N-Queens

Variables = N queens. Domain = positions on board. Constraints: no two queens in same row, column, or diagonal.

Timetabling

Variables = lectures. Domain = time slots. Constraints: same lecturer can't teach two slots at once, same room can't host two lectures at once, etc.

Min-Conflicts heuristic

Start with any complete assignment (random or otherwise). Then repeatedly: pick a violating variable, change its value to whichever reduces violations the most.

MIN_CONFLICTS(initial_assignment):
    tries ← 0
    while (violated_constraints > 0 AND tries < MAX_TRIES):
        X ← random variable that participates in a violated constraint
        for each value v in D[X]:
            compute total violations if X = v
        pick the v that minimizes violations (ties broken randomly)
        update X ← v
        tries++
    return current assignment

Worked example

Random initial: x1=6, x2=19, x3=8, x4=7, x5=−1 → 7 of 8 constraints violated.

Pick X5 (involved in violations). Try each value:

x5 = -3:  3 constraints involving X5 still violated → gain 0
x5 = -6:  ALL 3 constraints involving X5 become satisfied → gain 3
x5 = -1:  already current

Pick x5 = −6 → total violated drops from 7 to 4. Continue with another violating variable.

GSAT (Greedy Satisfiability)

Slightly different from Min-Conflicts: instead of picking a random violating variable, it scans every variable to find the single flip with the highest gain.

GSAT(initial_assignment):
    tries ← 0
    while (violations > 0 AND tries < MAX_TRIES):
        best_var, best_gain ← null, -∞
        for each variable X:
            for each value v in D[X]:
                if changing X to v gives a better gain than best_gain:
                    update best_var, best_value, best_gain
        change best_var to best_value
        tries++

Trade-off: GSAT considers more options per step (slower per step), but typically converges in fewer steps than Min-Conflicts.

Multilevel CSP

Like multilevel local search but at each level of recursion you flip several connected variables at once.

For level = num_levels downto 0:
    tries ← 0
    while (violations > 0 AND tries < MAX_TRIES):
        pick "level" random (and connected, in v2) variables
        try a random combined assignment for them
        compute gain
        keep if better
        tries++

Larger levels = coarser, more coordinated moves. Same multilevel idea as for graph partitioning.

Interactive demo — graph coloring CSP

Color the graph so no edge has the same color on both ends.

Exam tips