Backtracking: Constraint Satisfaction Problems
Constraint Satisfaction Problems represent a class of computational challenges where you need to assign values to variables while respecting a set of rules. Every CSP consists of three components:
Key Insights
- Constraint Satisfaction Problems (CSPs) provide a structured framework for modeling problems with variables, domains, and constraints—backtracking systematically explores this space while pruning invalid branches early.
- Heuristics like Minimum Remaining Values (MRV) and forward checking can reduce backtracking search time by orders of magnitude on real-world problems.
- While backtracking works well for moderately-sized CSPs, knowing when to reach for specialized solvers (SAT, CP libraries) separates pragmatic engineers from those stuck debugging slow code.
Introduction to Constraint Satisfaction Problems
Constraint Satisfaction Problems represent a class of computational challenges where you need to assign values to variables while respecting a set of rules. Every CSP consists of three components:
- Variables: The unknowns you need to solve for
- Domains: The possible values each variable can take
- Constraints: Rules that restrict which combinations of values are valid
You encounter CSPs constantly in software engineering. Scheduling systems assign time slots to meetings while avoiding conflicts. Configuration tools select compatible software versions. Resource allocators distribute workloads across servers. Even your IDE’s code formatter solves a CSP when deciding where to break lines.
The elegance of CSPs lies in their declarative nature. You describe what constitutes a valid solution rather than how to find it. This separation makes problems easier to model and reason about.
Why Backtracking for CSPs?
Brute force would enumerate every possible combination of variable assignments and check each against all constraints. For a problem with 10 variables, each with 10 possible values, that’s 10 billion combinations. Backtracking does better by detecting invalid partial assignments early and abandoning entire branches of the search tree.
The core insight: if assigning value v to variable x violates a constraint, there’s no point exploring any assignment that includes x = v. We backtrack immediately and try another value.
Here’s the generic template:
def backtrack(assignment: dict, variables: list, domains: dict, constraints) -> dict | None:
"""
Generic backtracking solver for CSPs.
Args:
assignment: Current partial assignment {variable: value}
variables: List of all variables to assign
domains: {variable: [possible_values]}
constraints: Function(assignment) -> bool, checks if assignment is valid
Returns:
Complete valid assignment or None if no solution exists
"""
# Base case: all variables assigned
if len(assignment) == len(variables):
return assignment
# Select next unassigned variable
unassigned = [v for v in variables if v not in assignment]
var = unassigned[0]
# Try each value in the domain
for value in domains[var]:
assignment[var] = value
# Check constraints on current partial assignment
if constraints(assignment):
result = backtrack(assignment, variables, domains, constraints)
if result is not None:
return result
# Backtrack: remove the assignment
del assignment[var]
return None
This template captures the essence: assign, check, recurse, and undo if necessary. The power comes from the constraint check happening on partial assignments, not just complete ones.
Classic Example: N-Queens Problem
The N-Queens puzzle asks you to place N chess queens on an N×N board such that no two queens threaten each other. No shared rows, columns, or diagonals.
Modeling as a CSP:
- Variables: One per row (queen’s column position in that row)
- Domains: Columns 0 through N-1
- Constraints: No two queens share a column or diagonal
def solve_n_queens(n: int) -> list[int] | None:
"""
Solve N-Queens problem using backtracking.
Returns list where index is row and value is column, or None.
"""
def is_safe(queens: list[int], row: int, col: int) -> bool:
"""Check if placing queen at (row, col) is valid."""
for prev_row, prev_col in enumerate(queens):
# Same column check
if prev_col == col:
return False
# Diagonal check: |row_diff| == |col_diff|
if abs(prev_row - row) == abs(prev_col - col):
return False
return True
def backtrack(queens: list[int]) -> list[int] | None:
row = len(queens)
if row == n:
return queens
for col in range(n):
if is_safe(queens, row, col):
result = backtrack(queens + [col])
if result is not None:
return result
return None
return backtrack([])
# Example usage
solution = solve_n_queens(8)
print(solution) # [0, 4, 7, 5, 2, 6, 1, 3] - one valid arrangement
The constraint check in is_safe runs in O(n) time, but we only call it when extending a valid partial solution. This pruning is what makes backtracking tractable for reasonable board sizes.
Sudoku Solver Implementation
Sudoku is a perfect CSP example with clear, intersecting constraints. Each cell is a variable with domain 1-9. Constraints enforce uniqueness within rows, columns, and 3×3 boxes.
def solve_sudoku(board: list[list[int]]) -> bool:
"""
Solve Sudoku in-place using backtracking.
Empty cells are represented as 0.
Returns True if solution found, False otherwise.
"""
def find_empty() -> tuple[int, int] | None:
"""Find next empty cell (row, col) or None if complete."""
for r in range(9):
for c in range(9):
if board[r][c] == 0:
return (r, c)
return None
def is_valid(row: int, col: int, num: int) -> bool:
"""Check if placing num at (row, col) violates constraints."""
# Row constraint
if num in board[row]:
return False
# Column constraint
if num in [board[r][col] for r in range(9)]:
return False
# 3x3 box constraint
box_row, box_col = 3 * (row // 3), 3 * (col // 3)
for r in range(box_row, box_row + 3):
for c in range(box_col, box_col + 3):
if board[r][c] == num:
return False
return True
def backtrack() -> bool:
cell = find_empty()
if cell is None:
return True # Solved
row, col = cell
for num in range(1, 10):
if is_valid(row, col, num):
board[row][col] = num
if backtrack():
return True
board[row][col] = 0 # Backtrack
return False
return backtrack()
# Example usage
puzzle = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9],
]
solve_sudoku(puzzle)
Optimization Techniques
The basic backtracking algorithm leaves significant performance on the table. Three heuristics dramatically improve real-world performance:
Minimum Remaining Values (MRV): Choose the variable with the fewest legal values remaining. This “fail-first” strategy detects dead ends earlier.
Degree Heuristic: Among variables with equal MRV, choose the one involved in the most constraints with unassigned variables. This maximizes constraint propagation.
Least Constraining Value: When selecting a value, choose the one that rules out the fewest choices for neighboring variables.
Here’s an enhanced Sudoku solver with MRV:
def solve_sudoku_mrv(board: list[list[int]]) -> bool:
"""Sudoku solver with MRV heuristic for variable selection."""
def get_candidates(row: int, col: int) -> set[int]:
"""Return valid candidates for a cell."""
if board[row][col] != 0:
return set()
candidates = set(range(1, 10))
candidates -= set(board[row]) # Row
candidates -= {board[r][col] for r in range(9)} # Column
# Box
box_row, box_col = 3 * (row // 3), 3 * (col // 3)
for r in range(box_row, box_row + 3):
for c in range(box_col, box_col + 3):
candidates.discard(board[r][c])
return candidates
def find_mrv_cell() -> tuple[int, int, set[int]] | None:
"""Find empty cell with minimum remaining values."""
best = None
best_count = 10
for r in range(9):
for c in range(9):
if board[r][c] == 0:
candidates = get_candidates(r, c)
if len(candidates) < best_count:
best = (r, c, candidates)
best_count = len(candidates)
if best_count == 0:
return best # Early termination: no valid values
return best
def backtrack() -> bool:
result = find_mrv_cell()
if result is None:
return True
row, col, candidates = result
if not candidates:
return False # Dead end
for num in candidates:
board[row][col] = num
if backtrack():
return True
board[row][col] = 0
return False
return backtrack()
On hard Sudoku puzzles, MRV can reduce the number of recursive calls by 90% or more.
Graph Coloring: Another CSP Application
Graph coloring assigns colors to vertices such that no adjacent vertices share a color. This models problems like register allocation, scheduling exams to avoid conflicts, and frequency assignment in wireless networks.
def color_graph(
vertices: list[str],
edges: list[tuple[str, str]],
num_colors: int
) -> dict[str, int] | None:
"""
Color a graph using backtracking.
Args:
vertices: List of vertex names
edges: List of (vertex1, vertex2) adjacency pairs
num_colors: Number of available colors (0 to num_colors-1)
Returns:
{vertex: color} mapping or None if impossible
"""
# Build adjacency list
neighbors = {v: set() for v in vertices}
for v1, v2 in edges:
neighbors[v1].add(v2)
neighbors[v2].add(v1)
def is_valid(assignment: dict, vertex: str, color: int) -> bool:
"""Check if assigning color to vertex is valid."""
for neighbor in neighbors[vertex]:
if assignment.get(neighbor) == color:
return False
return True
def backtrack(assignment: dict, remaining: list) -> dict | None:
if not remaining:
return assignment
# MRV: pick vertex with most colored neighbors
vertex = max(remaining, key=lambda v: len(neighbors[v] & set(assignment)))
remaining = [v for v in remaining if v != vertex]
for color in range(num_colors):
if is_valid(assignment, vertex, color):
assignment[vertex] = color
result = backtrack(assignment, remaining)
if result is not None:
return result
del assignment[vertex]
return None
return backtrack({}, vertices.copy())
# Example: Map of Australian states
vertices = ['WA', 'NT', 'SA', 'Q', 'NSW', 'V', 'T']
edges = [
('WA', 'NT'), ('WA', 'SA'), ('NT', 'SA'), ('NT', 'Q'),
('SA', 'Q'), ('SA', 'NSW'), ('SA', 'V'), ('Q', 'NSW'), ('NSW', 'V')
]
coloring = color_graph(vertices, edges, 3)
print(coloring) # {'T': 0, 'V': 0, 'NSW': 1, 'Q': 0, 'SA': 2, 'NT': 0, 'WA': 1}
Performance Considerations and When to Use Alternatives
Backtracking’s worst-case complexity is exponential—O(d^n) where d is domain size and n is variable count. Heuristics improve average case but can’t change the worst case.
Consider alternatives when:
- Problem size exceeds hundreds of variables: Look at constraint programming libraries like Google OR-Tools or Python-constraint
- Problem has special structure: SAT solvers handle Boolean satisfiability with sophisticated techniques
- You need all solutions or optimization: Dedicated solvers often provide these features built-in
- Real-time requirements exist: Precomputed lookup tables or approximation algorithms may be necessary
For most practical problems under a few hundred variables with reasonable domain sizes, well-optimized backtracking with MRV and forward checking performs adequately. The code is understandable, debuggable, and doesn’t require external dependencies.
The key engineering decision: start with simple backtracking, profile it, add heuristics if needed, and only then consider specialized solvers. Premature optimization toward complex constraint solvers often wastes more time than it saves.