Pattern 19 of 27

Backtracking with Constraints

Backtracking where most branches are invalid, so the speed comes from rejecting a choice as early as possible.

Cost: Exponential in the worst case; pruning decides the real cost
Problems: 6

When to reach for it

A board, grid or string has to satisfy rules while you fill it in.
Only valid arrangements count, and most partial ones fail quickly.
Trying every arrangement is far too large.

How it works

The skeleton is the same choose, explore, undo loop, but pruning does the heavy lifting. Keep enough state to test a choice in constant time: sets of used columns and diagonals for N-Queens, a visited mark on the grid for Word Search, a precomputed palindrome table for partitioning. Reject a choice before recursing rather than discovering the problem at the bottom of the tree. Every level you prune earlier removes an exponential number of calls.

The template

Written for N-Queens II

def total_n_queens(n):
    cols, diag, anti = set(), set(), set()

    def place(row):
        if row == n:
            return 1
        count = 0
        for c in range(n):
            if c in cols or row - c in diag or row + c in anti:
                continue              # prune before recursing
            cols.add(c); diag.add(row - c); anti.add(row + c)
            count += place(row + 1)
            cols.remove(c); diag.remove(row - c); anti.remove(row + c)
        return count

    return place(0)

Open in the editor Trace it line by line

Six problems, in learning order

1.Combination Sum IILeetCode 40Each number used at most once, with duplicates skipped at the same depth.Medium
2.Letter Combinations of a Phone NumberLeetCode 17Each digit is a level of the tree and its letters are the choices.Medium
3.Word SearchLeetCode 79Mark the cell visited, recurse into four neighbours, then unmark it.Medium
4.Palindrome PartitioningLeetCode 131Only cut where the prefix is a palindrome; a precomputed table speeds this up.Medium
5.N-QueensLeetCode 51Track columns and both diagonals, then build the board strings.Hard
6.N-Queens IILeetCode 52Count the placements instead of building the boards.Not in the curated 370 yet.Hard

What usually goes wrong

Validating only at the end instead of before each recursive call.
Not restoring grid cells or sets after returning, which corrupts sibling branches.
Recomputing an expensive check, like a palindrome test, in every call instead of precomputing it.