Constrained backtracking

Problem

You must find one, all, or the number of arrangements that satisfy rules: numbers that add to a target, queens that do not attack each other, a path of letters through a grid, a string cut into palindromes. Checking a finished answer is easy; the trouble is the astronomical number of candidates. The rules, however, usually become violated early, long before the answer is complete, and that is the opening.

Intuition

Walking a maze, you do not walk to the end of every corridor to learn it is a dead end. You turn around the moment you see the wall. Backtracking with constraints is the same: you test each next step against the rules, and a step that breaks a rule is never taken, which removes the entire subtree behind it with one comparison.

The power of that cut depends on how early it happens. Rejecting a bad queen on the second row saves every placement of rows three to eight; rejecting a bad grid letter on the first mismatch saves every longer path. So the craft is in ordering the choices and choosing the constraint test so that failures show up as high in the tree as they can.

Only safe placements become nodes. Of the 4⁴ = 256 ways to put one queen in each row, the search ever builds 17 partial boards. Green leaves are solutions; the grey leaves higher up are dead ends, found one row early. The diagram scrolls sideways on a narrow screen.

Mechanics

The invariant

At every call, the path so far satisfies all the rules that can be checked on a partial answer. Each recursive step adds one choice that is validated before it is made, so the invariant holds on entry to the child. When the path is complete, it is therefore a valid answer; when no legal choice remains, the call returns and the loop in the parent tries its next option. Nothing valid is lost, because a rejected choice would have broken a rule that no extension could repair.

That last clause is the correctness condition for any pruning rule: it must only reject a branch when no completion of it is valid. A rule that rejects too much loses answers; a rule that rejects too little is merely slow.

Keeping the check cheap

The test runs at every node, so it must not scan the board. Keep the facts in sets that you update on choose and restore on unchoose:

• For N-Queens, three sets: used columns, used row - col diagonals and used row + col anti-diagonals. A square is safe if all three miss. One queen per row is guaranteed by recursing one row at a time.
• For combination sum, the remaining target. Sorting the candidates once means the first candidate that exceeds the remainder ends the loop with a break, not a continue.
• For word search, the current index into the word, and a visited mark written into the grid itself and restored on the way out.

Where the cuts come from

Three kinds of pruning cover almost every problem. Feasibility: reject a choice that already violates a rule (a queen under attack, a letter that does not match). Bounds: reject when even the best case cannot succeed (the remaining sum is negative, too few items are left). Symmetry and duplicates: do not explore two branches that lead to the same state (a start index so combinations are not reordered, a sort and skip for equal values).

The path may bend but never reuses a cell, so each cell is marked while it is on the path and restored when the search backs out.

Worked example

Combination sum

Candidates 2, 3, 6, 7 (each usable any number of times), target 7. Sorted candidates plus the early break find 2 answers (2+2+3, 7) in 10 calls. The loop examines 16 candidates; without the break, which would skip each overshoot one by one, it would examine 27.

The no-reuse variant on 10, 1, 2, 7, 6, 1, 5 with target 8 sorts to 1, 1, 2, 5, 6, 7, 10 and uses the duplicate-skip rule from the previous page. It finds 4 distinct answers: 1+1+6, 1+2+5, 1+7, 2+6.

N-Queens

For 4 queens the search tries 60 squares in total, builds 17 safe partial boards and finds 2 solutions. Written as the column of the queen in each row from the top, they are:

Scaling up: 6 queens has 4 solutions and 8 queens has 92 solutions, yet the search needs only 2057 nodes for 8 queens, instead of the 8⁸ = 16,777,216 boards of one queen per row.

Word search and palindrome cuts

Searching the grid for ABCCED succeeds after 9 calls along a 6-cell path. Searching for ABCB fails after 20 calls: it walks as far as ABC, then the third letter's neighbors cannot supply another B without reusing a cell.

Cutting "aab" into palindromes gives 2 ways (a|a|b, aa|b) in 6 calls. The piece "ab" is never extended, because it is not a palindrome.

Implementation

def combination_sum(candidates, target):
    nums = sorted(candidates)
    results, path = [], []

    def explore(start, remaining):
        if remaining == 0:
            results.append(path[:])
            return
        for i in range(start, len(nums)):
            if nums[i] > remaining:
                break                          # sorted: every later candidate overshoots too
            path.append(nums[i])
            explore(i, remaining - nums[i])    # i, not i + 1: the same item may repeat
            path.pop()

    explore(0, target)
    return results


def solve_n_queens(n):
    cols, diag, anti = set(), set(), set()
    placed, boards = [], []

    def explore(row):
        if row == n:
            boards.append(["." * c + "Q" + "." * (n - c - 1) for c in placed])
            return
        for col in range(n):
            if col in cols or row - col in diag or row + col in anti:
                continue
            cols.add(col); diag.add(row - col); anti.add(row + col)
            placed.append(col)
            explore(row + 1)
            placed.pop()
            cols.remove(col); diag.remove(row - col); anti.remove(row + col)

    explore(0)
    return boards


def exist(board, word):
    rows, cols = len(board), len(board[0])

    def explore(r, c, i):
        if board[r][c] != word[i]:
            return False
        if i == len(word) - 1:
            return True
        saved, board[r][c] = board[r][c], "#"
        found = any(
            0 <= nr < rows and 0 <= nc < cols and explore(nr, nc, i + 1)
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1))
        )
        board[r][c] = saved
        return found

    return any(explore(r, c, 0) for r in range(rows) for c in range(cols))

Variations and edge cases

def partition_palindromes(s):
    results, path = [], []

    def explore(start):
        if start == len(s):
            results.append(path[:])
            return
        for end in range(start + 1, len(s) + 1):
            piece = s[start:end]
            if piece == piece[::-1]:
                path.append(piece)
                explore(end)
                path.pop()

    explore(0)
    return results

• Sudoku. The same template with one set per row, column and box. Always fill the empty cell with the fewest legal digits first; that ordering often turns a hard puzzle into a quick one.
• Equal-sum partitions (Matchsticks, k equal subsets). Sort descending so big items fail fast, reject early if the total is not divisible by k, and skip trying an empty bucket twice, because two empty buckets are interchangeable.
• Word Break II. The prefix-extension shape of the palindrome code, with the dictionary lookup as the test. Memoize the answers for each suffix when words overlap heavily, or the search repeats itself.
• Marks that leak. Restoring the grid cell must happen on every exit path, including the early success return, or later searches see a damaged grid. Using any(...) with a restore after it keeps the exits to one.
• Break versus continue. break is only right when the candidates are sorted and the failing test is monotonic. Otherwise use continue.
• Edge cases: a target of zero (the empty combination), no candidate small enough, a 1-cell grid, a word longer than the grid, an N that has no solution (2 and 3 queens) and a string that is already a palindrome.

Complexity and tradeoffs

• Time: still exponential in the worst case: up to n! for queens and 4^L for a word of length L on a grid. Pruning does not change the bound; it shrinks the constant enormously, and the real cost is the number of nodes that survive the checks.
• Space: O(depth) for the call stack and the path, plus the constraint sets.
• Baseline. Generate every candidate and filter at the end. For 8 queens that is millions of boards against 2057 nodes.
• When it fails. If the same subproblem recurs (the same remaining sum with the same suffix of candidates, the same string suffix), memoizing it, or turning the search into a table, beats backtracking. If the question asks for a count or an optimum rather than the arrangements, dynamic programming is usually the intended tool. If a bad ordering makes the first branches hopeless, reorder so the most constrained choice comes first.

Problems

Every home problem has a rule that fails early. Combination Sum and Combination Sum II are the cleanest first exercises; N-Queens and Sudoku train the constant-time constraint state; Word Search trains reversible marking. Word Search II (listed below) pairs this with a trie so that many words share one search.

Medium

• 39. Combination Sum Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Let each branch reuse the current candidate or move past it, and prune once the running sum passes the target.
• 40. Combination Sum II NeetCode 150 NeetCode 250
  Sort first, use each number at most once, and skip equal values at the same depth so identical combinations never repeat.
• 79. Word Search Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Depth-first search from each cell, marking cells on the current path so the word never reuses one, and unmark on return.
• 131. Palindrome Partitioning NeetCode 150 NeetCode 250
  Cut off a palindromic prefix and recurse on the rest; precomputing which substrings are palindromes makes each check constant time.
• 473. Matchsticks to Square NeetCode 250
  Sort the sticks longest first and place each into one of four sides, pruning sides that overflow and sides of equal length that were already tried.
• 698. Partition to K Equal Sum Subsets NeetCode 250
  Fill k buckets of the target sum with numbers sorted descending, skipping buckets with the same current load to cut symmetric branches.

Hard

• 37. Sudoku Solver Grind 169
  Fill empty cells one at a time with digits allowed by the row, column and box sets, and undo the moment a cell has no legal digit.
• 51. N-Queens Grind 169 NeetCode 150 NeetCode 250
  Place one queen per row and track occupied columns and both diagonals in sets, so every placement check is constant time.
• 52. N-Queens II NeetCode 250
  Run the row-by-row queen placement but only count complete boards, using column and diagonal sets to prune.
• 140. Word Break II NeetCode 250
  Recurse on every dictionary word that starts the remaining string and memoize the sentence lists for each suffix.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 212. Word Search II Hard

Connections

This page sharpens the template from subsets and permutations with a validity test and a bound, and it is DFS on a grid in the sense of the tree pages. Graph traversal drops the "unchoose" step because a visited set is permanent there, while here the mark is undone so another path may use the cell. When states repeat, dynamic programming is the next move.

Check yourself

References

• Skiena, The Algorithm Design Manual, chapter 9, backtracking with pruning, including the eight-queens and sudoku examples.
• Knuth, The Art of Computer Programming, volume 4B, section 7.2.2 (backtrack programming), and Knuth's "Dancing Links" paper for exact-cover problems such as sudoku.
• Russell and Norvig, Artificial Intelligence: A Modern Approach, chapter 6 on constraint satisfaction, including most-constrained-variable ordering.
• Sedgewick and Wayne, Computer Science: An Interdisciplinary Approach, section 2.3 (recursion), whose exercises build permutations, combinations and the n-queens search.
• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, chapter 34 (NP-completeness): why exact search for problems such as satisfiability has no known polynomial algorithm, so backtracking with pruning stays exponential in the worst case.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.