Constraint Satisfaction Problems

Jr Codex AI Notes

Level: Intermediate–Advanced Prerequisites: Chapter 5 Time to complete: ~30 minutes

Table of Contents

1. What is a CSP?
2. Formal Definition
3. Backtracking Search
4. Constraint Propagation
5. Variable & Value Ordering Heuristics
6. A Complete Worked Example: Map Coloring
7. CSPs vs General Search — When to Use Which
8. Summary & Next Steps

1. What is a CSP?

A Constraint Satisfaction Problem (CSP) is a special kind of search problem (Chapter 1) where a state is defined by an assignment of values to a fixed set of variables, and the goal is any assignment satisfying a given set of constraints — there's no notion of path cost at all, only "valid" or "invalid."

General Search Problem (Ch.1)          CSP (this chapter)
─────────────────────────────         ─────────────────────────────
  States are ARBITRARY                   States are STRUCTURED:
  (a city, a board position)               specific VARIABLES, each
                                            with a value from its DOMAIN

  Goal test: some arbitrary                Goal test: EVERY constraint
  condition                                  between variables is satisfied
─────────────────────────────         ─────────────────────────────

This extra structure is what makes CSPs special — because we know exactly what a "state" consists of (variable-value pairs) and what makes it invalid (a violated constraint), CSPs admit much more powerful, specialized techniques than the generic search from Chapters 2-3.

2. Formal Definition

Three Components of a CSP
─────────────────────────────────────────
  Variables (X):     the things needing a value
                       e.g. X = {WA, NT, SA, Q, NSW, V, T}  (Australian regions)

  Domains (D):          the possible values EACH variable can take
                         e.g. D = {red, green, blue} for every region

  Constraints (C):        rules restricting which COMBINATIONS
                            of values are allowed
                            e.g. "adjacent regions must have
                            DIFFERENT colors"
─────────────────────────────────────────

# Formalizing the Australia map-coloring problem (a classic CSP example)
variables = ["WA", "NT", "SA", "Q", "NSW", "V", "T"]
domains = {var: ["red", "green", "blue"] for var in variables}
 
# Constraints: pairs of regions that are ADJACENT (must differ in color)
adjacent_pairs = [
    ("WA", "NT"), ("WA", "SA"), ("NT", "SA"), ("NT", "Q"),
    ("SA", "Q"), ("SA", "NSW"), ("SA", "V"), ("Q", "NSW"),
    ("NSW", "V"),
]      # Tasmania (T) has no land borders — no constraints involving it

3. Backtracking Search

The standard CSP-solving algorithm: assign values to variables one at a time, and backtrack (undo the last assignment and try a different value) the moment a constraint is violated — no point continuing down a path already known to be invalid.

def is_consistent(assignment, var, value, constraints):
    """Check if assigning `value` to `var` violates any constraint with already-assigned variables."""
    for (var1, var2) in constraints:
        if var1 == var and var2 in assignment and assignment[var2] == value:
            return False
        if var2 == var and var1 in assignment and assignment[var1] == value:
            return False
    return True
 
def backtracking_search(variables, domains, constraints, assignment=None):
    if assignment is None:
        assignment = {}
 
    if len(assignment) == len(variables):
        return assignment      # every variable assigned, all constraints satisfied — SOLVED
 
    unassigned = [v for v in variables if v not in assignment]
    var = unassigned[0]      # simplest choice — Section 5 covers smarter ordering
 
    for value in domains[var]:
        if is_consistent(assignment, var, value, constraints):
            assignment[var] = value
            result = backtracking_search(variables, domains, constraints, assignment)
            if result is not None:
                return result
            del assignment[var]      # BACKTRACK — this value didn't lead to a solution
 
    return None      # no value works — backtrack further up the recursion
 
solution = backtracking_search(variables, domains, adjacent_pairs)
print(solution)      # e.g. {'WA': 'red', 'NT': 'green', 'SA': 'blue', 'Q': 'red', ...}

Backtracking as Depth-First Search With Early Pruning
─────────────────────────────────────────
  Backtracking is DFS (Chapter 2) over CSP states, with one
  critical enhancement: it checks constraints IMMEDIATELY after
  each assignment, abandoning a branch the MOMENT it becomes
  invalid — rather than waiting to discover the problem only
  after a full (invalid) assignment is complete.
─────────────────────────────────────────

4. Constraint Propagation

Backtracking can be dramatically sped up by propagating constraints before fully committing to an assignment — eliminating values from other variables' domains that could never work, given what's already assigned.

def forward_checking(assignment, domains, var, value, constraints):
    """
    After assigning `value` to `var`, remove now-invalid values from
    the domains of variables directly constrained with it.
    Returns an updated domains dict, or None if any domain becomes empty (dead end).
    """
    new_domains = {v: list(d) for v, d in domains.items()}
 
    for (var1, var2) in constraints:
        other = var2 if var1 == var else (var1 if var2 == var else None)
        if other and other not in assignment:
            if value in new_domains[other]:
                new_domains[other].remove(value)
            if not new_domains[other]:
                return None      # DEAD END — this variable has no valid values left at all
    return new_domains

Forward Checking, Visualized
─────────────────────────────────────────
  Assign WA = red
       │
       ▼
  NT's domain: {red, green, blue} → {green, blue}   (red removed — WA-NT are adjacent)
  SA's domain: {red, green, blue} → {green, blue}   (red removed — WA-SA are adjacent)

  If assigning a LATER variable ever empties another variable's
  domain entirely, we know IMMEDIATELY (without trying every
  value) that this branch cannot lead to a solution — backtrack
  right away.
─────────────────────────────────────────

Levels of Constraint Propagation (Increasing Power & Cost)
─────────────────────────────────────────
  No propagation:     plain backtracking (Section 3) — checks
                        constraints only against ALREADY assigned variables

  Forward checking:      after each assignment, prunes newly-invalid
                            values from DIRECTLY connected UNASSIGNED
                            variables (shown above)

  Arc consistency (AC-3):   propagates further — for every pair of
                              connected variables, ensures every value
                              in one's domain has SOME compatible value
                              in the other's, repeatedly, until stable
─────────────────────────────────────────

The trade-off: stronger propagation catches dead ends earlier (saving wasted search) but costs more to compute per step — forward checking is the standard practical default, striking a good balance for most problems.

5. Variable & Value Ordering Heuristics

Backtracking's unassigned[0] in Section 3 picked the first unassigned variable arbitrarily — smarter ordering can dramatically reduce the search needed, directly echoing Chapter 3's heuristic-design lessons.

def most_constrained_variable(assignment, variables, domains):
    """
    Minimum Remaining Values (MRV) heuristic: choose the unassigned
    variable with the FEWEST legal values left — it's most likely to
    fail soon, so resolving it EARLY prunes the search tree faster.
    """
    unassigned = [v for v in variables if v not in assignment]
    return min(unassigned, key=lambda v: len(domains[v]))
 
def least_constraining_value(var, domains, constraints, assignment):
    """
    Order VALUES to try the one that rules out the FEWEST options
    for other variables first — keeps the most flexibility available
    for as long as possible.
    """
    def count_conflicts(value):
        count = 0
        for (var1, var2) in constraints:
            other = var2 if var1 == var else (var1 if var2 == var else None)
            if other and other not in assignment and value in domains[other]:
                count += 1
        return count
 
    return sorted(domains[var], key=count_conflicts)

Two Complementary Heuristics
─────────────────────────────────────────
  Minimum Remaining Values (MRV):   pick the variable LIKELIEST
                                       to fail soonest — "fail fast"
                                       so wasted search is discovered
                                       early, not deep into a doomed branch

  Least Constraining Value (LCV):     for the chosen variable, try
                                         the value that keeps the MOST
                                         options open for everyone
                                         else — maximizes the chance
                                         the rest of the problem stays
                                         solvable
─────────────────────────────────────────

These two heuristics are often used together: MRV picks which variable to assign next; LCV picks which value to try first for it — a combination that dramatically outperforms the naive ordering from Section 3 on most real CSPs.

6. A Complete Worked Example: Map Coloring

Bringing every technique in this chapter together, solving Chapter 6's Australia map-coloring problem with the full toolkit:

def backtracking_with_heuristics(variables, domains, constraints, assignment=None):
    if assignment is None:
        assignment = {}
 
    if len(assignment) == len(variables):
        return assignment
 
    var = most_constrained_variable(assignment, variables, domains)      # Section 5: MRV
    ordered_values = least_constraining_value(var, domains, constraints, assignment)  # Section 5: LCV
 
    for value in ordered_values:
        if is_consistent(assignment, var, value, constraints):
            assignment[var] = value
            new_domains = forward_checking(assignment, domains, var, value, constraints)  # Section 4
 
            if new_domains is not None:      # no domain wiped out — keep going
                result = backtracking_with_heuristics(variables, new_domains, constraints, assignment)
                if result is not None:
                    return result
 
            del assignment[var]      # backtrack
 
    return None
 
solution = backtracking_with_heuristics(variables, domains, adjacent_pairs)
print(solution)

This combines Section 3's backtracking skeleton, Section 4's forward checking (pruning dead-end domains early), and Section 5's MRV/LCV ordering — the standard, practical recipe for solving real CSPs efficiently.

7. CSPs vs General Search — When to Use Which

Decision Guide
─────────────────────────────────────────
  Problem has CLEAR variables, each with a well-defined DOMAIN
  of possible values, and success means satisfying CONSTRAINTS
  (not minimizing a path cost)
      → Model it as a CSP (this chapter) — Sudoku, scheduling,
        map coloring, resource allocation

  Problem is about finding the BEST PATH/SEQUENCE of actions
  to reach a goal, often with associated COSTS
      → General search instead (Ch.1-3) — route-finding, puzzle-solving
        where the sequence of moves itself matters
─────────────────────────────────────────

8. Summary & Next Steps

Key Takeaways

• A CSP is defined by variables, their domains, and constraints between them — success means any assignment satisfying every constraint, with no notion of path cost.
• Backtracking search is DFS with early pruning: it abandons an assignment the moment a constraint is violated, rather than discovering the problem only later.
• Constraint propagation (forward checking, arc consistency) proactively removes now-invalid values from unassigned variables' domains, catching dead ends earlier.
• MRV (choose the most-constrained variable next) and LCV (choose the least-constraining value first) are complementary ordering heuristics that dramatically speed up practical CSP solving.

Module 2 Complete — Next Module

You now have the full classical search toolkit: state-space framing, uninformed and informed search, local search, adversarial search for games, and constraint satisfaction. Module 3 builds on this foundation with knowledge representation, logic, and automated planning — techniques for reasoning about facts and sequencing actions in more structured, expressive ways than plain search states allow.

Concept Check

1. What's the key structural difference between a CSP and a general search problem from Chapters 1-3?
2. Why does forward checking help backtracking search find dead ends earlier?
3. What do MRV and LCV each optimize for, and why are they often used together?

Next Chapter

→ Module 3: Knowledge, Reasoning & Planning

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index