For constraint satisfaction: Sudoku, scheduling, N-queens, logic puzzles, SAT-like problems, assignment problems. Uses propagate-then-search pattern.
Constraint Propagation + Search: Eliminate impossibilities first, then guess only when necessary.
def solve(puzzle):
"""Solve by propagation, then search if needed."""
state = propagate(puzzle)
if state is None:
return None # Contradiction found
if is_solved(state):
return state
return search(state)
def search(state):
"""DFS with constraint propagation at each step."""
# Choose variable with Minimum Remaining Values (MRV)
var = min(unassigned(state), key=lambda v: len(state[v]))
for value in state[var]:
new_state = assign(copy(state), var, value)
new_state = propagate(new_state)
if new_state is not None:
result = search(new_state)
if result is not None:
return result
return None
def eliminate(values, s, d):
"""Eliminate digit d from values[s]; propagate constraints."""
if d not in values[s]:
return values # Already eliminated
values[s] = values[s].replace(d, '')
# Constraint 1: If only one value left, eliminate from peers
if len(values[s]) == 0:
return None # Contradiction
elif len(values[s]) == 1:
d2 = values[s]
if not all(eliminate(values, peer, d2) for peer in peers[s]):
return None
# Constraint 2: If only one place for d in a unit, assign it
for unit in units[s]:
places = [sq for sq in unit if d in values[sq]]
if len(places) == 0:
return None # Contradiction
elif len(places) == 1:
if not assign(values, places[0], d):
return None
return values
def search(values):
"""DFS with MRV heuristic."""
if values is None:
return None
if all(len(values[s]) == 1 for s in squares):
return values # Solved!
# MRV: choose square with fewest possibilities
n, s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
for d in values[s]:
result = search(assign(values.copy(), s, d))
if result:
return result
return None
units and peers once, use everywhere