Backtracking State Management

State management keeps auxiliary maps (counts, occupied columns) consistent with the mutable board—every push has a matching pop in all return paths.

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)

Use small structs: cols, diag1, diag2 booleans or bitmasks for N-Queens style checks. Update before recurse, revert after.

Try this in Python

def is_valid(s: str) -> bool:
    stack: list[str] = []
    pairs = {')': '(', '}': '{', ']': '['}
    for ch in s:
        if ch in '({[':
            stack.append(ch)
        else:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
    return not stack


print(is_valid('()[]{}'))

Common mistakes

• Asymmetric update/undo (update two structures, undo one).
• Using global without clearing between multiple top-level calls.

Key takeaways

• Mirror add/remove in try/finally rarely needed; instead mirror before/after each dfs() call pair.
• Prefer passing immutable slices when depth is small.