dfs(partial_assignment): emit when complete; choose unassigned variable x, try each v in domain(x) consistent with current constraints, apply x=v, propagate/recurse, and undo.
Recognition signals
A board, labeling, partition, or path must satisfy several local constraints.
Variables have finite domains and search-sized scale.
A partial assignment can already expose conflicts.
A concrete witness or all witnesses are required.
MRV, most-constrained-variable, or value ordering can prune heavily.
False friends
Signal
Why it is different
Connectivity or shortest paths
When states can be reused by node, BFS or Dijkstra avoids enumerating complete histories.
A constraint graph with DP structure
Chains, trees, or low treewidth may admit DP that reuses equivalent partial assignments.
A matching or 2-SAT special case
A dedicated polynomial algorithm is stronger than generic exponential search.
Core invariant
At recursion entry, the partial assignment satisfies every activated constraint and every auxiliary set/count exactly matches it; a pruned branch has no legal completion.
State, transition, and processing order
Item
Definition
State
Partial assignment, unassigned variables, incremental summaries for each constraint class, and optional reduced domains.
Transition
Choose a variable, try a compatible value, atomically update assignment and constraint state, recurse, then restore every change.
Frontier / order
One consistent partial assignment in the search tree; selecting the variable with fewest candidates tends to fail earlier.
Python skeleton
def color_graph(graph, color_count):
n = len(graph)
color = [-1] * n
def dfs(done):
if done == n: return True
candidates = [u for u in range(n) if color[u] < 0]
u = max(candidates, key=lambda x: sum(color[v] >= 0 for v in graph[x]))
forbidden = {color[v] for v in graph[u] if color[v] >= 0}
for c in range(color_count):
if c in forbidden: continue
color[u] = c
if dfs(done + 1): return True
color[u] = -1
return False
return color if dfs(0) else None
Correctness sketch
The invariant makes every attempted partial assignment legal.
All currently legal values of the chosen variable are tried; any complete solution assigns one of them, so none is missed.
Failure is returned only for an immediate contradiction or failed exhaustive children; undo restores the parent, making witnesses valid and failure conclusions sound.
Complexity
Time
Space
Parameters
Worst case O(d^n·check); pruning changes practice, not the exponential bound
O(n+constraint_state)
n is variable count and d the largest domain.
Edge cases
no variables
preassigned variables
an empty domain
self-loop or contradictory constraints
one versus all solutions
exceptions during state rollback
Error patterns
Pattern
Why it fails / fix
Checking constraints only at leaves
This preserves doomed prefixes; validate or propagate immediately after apply.
Incomplete rollback
Undoing the assignment but not sets or counts contaminates sibling branches; pair all mutations.
Heuristic pruning without proof
Every prune must establish that no completion exists or it can remove valid answers.
Always choosing input order
Correct but often slow; MRV or most-constrained-first exposes contradictions earlier.
Selection and exclusion rules
Identify constraints testable on a partial assignment.
Encapsulate apply/undo so state changes stay atomic.
Choose the most constrained variable and order promising values.
Exclude matching, SAT special cases, or structured DP before generic search.