Solve Constraint Puzzle

solve-constraint-puzzle

When to Use

• Sudoku and Sudoku-like puzzles
• Scheduling problems (classes, shifts, tournaments)
• N-queens and placement puzzles
• Logic puzzles (Einstein's riddle)
• Resource assignment problems
• Any problem with variables, domains, and constraints

When NOT to Use

• Optimization problems (use local search instead)
• Problems without clear constraints
• When brute force is fast enough

The 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

Example (from pytudes Sudoku.ipynb)

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

Key Principles

1. Propagate before search: Eliminate impossibilities to reduce search space
2. MRV heuristic: Try most constrained variable first (fail fast)
3. Copy on branch: Don't mutate state during search; copy before guessing
4. Return None for failure: Distinguishes "no solution" from "not yet solved"
5. Precompute constraints: Build units and peers once, use everywhere