Pattern1 Practice11 Interview

Constraint Satisfaction

GuideCode Labs

Search assignments incrementally while pruning partial states that violate constraints. Learn its decision rule, maintained state, Python cost model, and transfer from a focused drill to a full Interview Problem.

Recognize it when

Consider Constraint Satisfaction when the prompt's constraints and required operations match this shape: Search assignments incrementally while pruning partial states that violate constraints.

On this page · Model Variables Domains and Constraints

Checking your account…

Model Variables Domains and Constraints

A constraint-satisfaction problem has variables, allowed domains, and relations that rule out joint assignments. A partial assignment is valid only if every currently testable constraint holds.

Choose the Most Constrained Variable

Selecting the unassigned variable with the fewest legal values exposes failure early. Tie-break deterministically so traces and tests remain explainable.

Trace Most-Constrained Choices

Reference

def choose_variable(domains,assigned):
    candidates=[name for name in domains if name not in assigned]
    return min(candidates,key=lambda name:(len(domains[name]),name)) if candidates else None

Practice

Implement choose_variable(domains,assigned). Return the unassigned variable with the smallest domain, breaking ties by variable name, or None.

def choose_variable(domains,assigned):
    pass

Public tests

Choose minimum remaining values

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Propagate Before Recursing

After assigning a value, remove inconsistent values from neighboring domains or at least reject conflicts immediately. If any unassigned domain becomes empty, prune because no completion exists.

Solve a Small Graph Coloring

Reference

def color_graph(adjacency,colors):
    assigned=[None]*len(adjacency)
    def search(node):
        if node==len(adjacency): return True
        for color in colors:
            if all(assigned[n]!=color for n in adjacency[node]):
                assigned[node]=color
                if search(node+1): return True
                assigned[node]=None
        return False
    return assigned if search(0) else []

Practice

Implement color_graph(adjacency,colors). Return the first valid color list in node order using colors order, or [].

def color_graph(adjacency,colors):
    pass

Public tests

Respect constraints and restore failures

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Restore Every Domain Change

Record every assignment and domain removal made by one choice, then restore them on failure. Copying all domains is simpler but expensive; an undo log is efficient only if restoration is exact.

Explain It in an Interview

Say: “This variable has the smallest remaining domain. I try one value, propagate its constraints, recurse only if every domain remains viable, then restore every change.” Describe worst-case exponential search and why the heuristic changes practical work, not correctness.

Python Version Note

Python 3.11+

The examples use the standard Python syntax and containers supported by the browser Judge; the Constraint Satisfaction invariant is independent of a minor Python release.

Verify in Python docs

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

Operation	Average	Worst	Interview note
Constraint Satisfaction decision loop	`O(b^n)`	`O(b^n)`	Depth-first assign sorted candidate values, pruning used values and undoing both assignment and constraint state after failure.

Space

O(n) for the focused Build a Unique Assignment implementation.

Assumptions

Each branch contains only unique partial assignments. Backtracking enumerates every legal candidate sequence, and sorted traversal makes the first complete sequence lexicographically smallest; if none completes, no valid assignment exists.
The bound includes real Python operations; no repeated slicing, linear list membership, or hidden sorting is treated as free.

Invariants Worth Saying Aloud

State the precise Constraint Satisfaction invariant before coding and preserve it after every update, traversal step, or recursive return.
Every partial assignment satisfies all constraints checked so far.
Undo restores both the assignment and every auxiliary constraint structure.
Maintain a used-value constraint incrementally. Preserve this property after every transition.
Explore sorted candidates to make the first complete assignment lexicographically smallest. Preserve this property after every transition.

When To Use Or Avoid Constraint Satisfaction

Use It When

Use Constraint Satisfaction when the prompt exposes the ordering, monotonicity, recurrence, or constraint that makes this decision safe.
Use it when every partial assignment satisfies all constraints checked so far.

Choose Another Tool When

Avoid Constraint Satisfaction when its decision rule cannot eliminate work or preserve the required state.
Avoid forcing the label onto a prompt whose simpler direct scan already meets the constraints.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Moving state without a proof

Applying the pattern without proving its ordering, monotonicity, or window invariant can silently miss valid candidates.

Prevent it: Write the decision rule beside the loop and verify it against Build a Unique Assignment before optimizing.

Avoid

def smallest_unique_assignment(options):
    pass

Use instead

def smallest_unique_assignment(options):
    assignment = []
    used = set()
    def search(position):
        if position == len(options):
            return True
        for value in sorted(options[position]):
            if value in used:
                continue
            used.add(value)
            assignment.append(value)
            if search(position + 1):
                return True
            assignment.pop()
            used.remove(value)
        return False
    return assignment if search(0) else []

Where you will hit this: Build a Unique Assignment(opens in a new tab)

Breaking the maintained state

Uses a greedy first-unused choice and cannot recover when that choice blocks a later position.

Prevent it: Use the public tests and preserve this state: Every partial assignment satisfies all constraints checked so far.

Avoid

def smallest_unique_assignment(options):
    out=[]; used=set()
    for choices in options:
        available=[x for x in sorted(choices) if x not in used]
        if not available:return []
        out.append(available[0]); used.add(available[0])
    return out

Use instead

def smallest_unique_assignment(options):
    assignment = []
    used = set()
    def search(position):
        if position == len(options):
            return True
        for value in sorted(options[position]):
            if value in used:
                continue
            used.add(value)
            assignment.append(value)
            if search(position + 1):
                return True
            assignment.pop()
            used.remove(value)
        return False
    return assignment if search(0) else []

Where you will hit this: Build a Unique Assignment(opens in a new tab)

Hiding Python work in the hot path

Python slicing, copying, membership in lists, or repeated sorting inside the loop can invalidate the intended complexity.

Prevent it: Count every slice, copy, sort, membership check, and container update before claiming O(b^n).

Avoid

def smallest_unique_assignment(options):
    out=[]; used=set()
    for choices in options:
        available=[x for x in sorted(choices) if x not in used]
        if not available:return []
        out.append(available[0]); used.add(available[0])
    return out

Use instead

def smallest_unique_assignment(options):
    assignment = []
    used = set()
    def search(position):
        if position == len(options):
            return True
        for value in sorted(options[position]):
            if value in used:
                continue
            used.add(value)
            assignment.append(value)
            if search(position + 1):
                return True
            assignment.pop()
            used.remove(value)
        return False
    return assignment if search(0) else []

Where you will hit this: Reusable-Candidate Combination Sum(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.

Python Compound Statements — Function Definitions(opens in a new tab)
python-docs · checked 2026-07-27
Hello Interview — Backtracking Overview(opens in a new tab)
hello-interview · checked 2026-07-12

Checking your account…