Constraint Pruning in Search

Constraint pruning encodes rules like “no two adjacent picks” or “sum divisible by k” into checks before recursing—shrinks branching factor dramatically.

Why this shows up in the real world

Puzzle games, constraint solvers, and interview combinatorial search all share the same skeleton: build state, recurse, undo.

Core idea (explained for students)

Push validation left: validate placement before DFS rather than deep rejection after wasting depth.

Try this in Python

def is_safe(board: list[str], r: int, c: int) -> bool:
    n = len(board)
    for i in range(r):
        j = board[i].find('Q')
        if j == c or abs(j - c) == r - i:
            return False
    return True


print(is_safe(['.Q..', '...Q'], 2, 1))

Common mistakes

• Redundant checks every level—factor into incremental invariants.
• Constraints that need global graph info—backtracking may be wrong tool.

Key takeaways

• Maintain running totals and forbidden sets updated in O(1) per step.
• When stuck, switch viewpoint to CSP with arc consistency (advanced).