Backtracking

Backtracking is the go-to for constraint satisfaction problems: configuration generators, puzzle solvers, and scheduling with complex rules. You try options, check constraints, and undo when you hit a dead end.

What it solves

Any problem that asks for configurations — assignments of choices that satisfy constraints. Fill this board, arrange these pieces, schedule these jobs under rules, place these queens, solve this nonogram. The signature is that a partial choice can be extended or abandoned.

Recognition signals

• "All possible ways / all valid configurations / every arrangement"
• "Find a valid assignment such that…" with several interlocking rules
• "Puzzle", "board", "fill", "place", "arrange"
• "Try different options", "backtrack when it doesn't work"
• Constraints that make a partial solution provably dead (pruning opportunities)

The approach

The skeleton is tiny and stable:

def solve(partial):
    if complete(partial):       # solution found
        return partial
    for option in options(partial):
        if valid(partial, option):      # constraint check
            apply(partial, option)
            result = solve(partial)
            if result: return result
            undo(partial, option)       # the backtrack
    return None

The hard parts are: the state representation (what is partial?), the constraint check (how do you prune cheaply and early?), and the undo strategy (mutate-and-undo vs. copy state). Ordering options well also matters — trying promising branches first finds solutions faster, and good pruning is the difference between seconds and hours.

What to tell the AI

Decide the state and the pruning yourself; have the AI implement the recursion:

Implement backtracking for the nonogram: represent the board as a mutable 2D array of booleans. For each row, enumerate placements that match the row clues, pruning when a placement conflicts with already-known cells. Mutate the board in place, recurse, and undo on failure. Stop at the first full solution.

What to verify

• The undo step — the AI's #1 bug here: forgetting to undo on the failure path, or undoing the wrong mutation.
• Pruning actually prunes — if the AI "backtracks" by enumerating everything and filtering at the end, it's brute force with extra steps. Check the constraint check runs before recursion.
• State aliasing — shared mutable arrays copied by reference; sibling branches corrupting each other.
• Termination — base case correct? Solutions returned at the wrong depth?
• First-vs-all — does it stop at the first solution when asked, or keep searching?
• Search-space blowup — without early pruning, large inputs time out. Ask for the complexity of the branch factor.

Worked micro-example

Place N queens on an N×N board. options = columns of the current row; valid = no attack with already-placed queens (checked incrementally in O(1) with row/col/diagonal sets). Choose column → recurse next row → undo. For N=8, good pruning makes this instant; without the diagonal check it explodes.

Practice problems

Try these: Nonogram Solver (row-by-row constraint satisfaction), Connect Four (game-tree search with depth limit), Maximize Unique Characters (greedy + backtracking over swaps), and Spell Checker (trie-guided candidate enumeration).