DSA Roadmap/Backtracking

Constraint Satisfaction Search (N-Queens, Sudoku, Word Search)

Structure decision variables so each solution has one construction order, encode constraints for O(1) checks, and prune before recursing — N-Queens, Sudoku, Word Search, and similar CSPs.

!4/5Theory: 1h 30m4 problems

Where pruning stops being optional

Subsets, combinations, and permutations all have a manageable branching factor and a search space you can often afford to explore close to fully. Constraint satisfaction problems — N-Queens, Sudoku, Word Search — are different: the naive search space is so large that without aggressive pruning, your program does not finish in the age of the universe, let alone within a time limit. This subtopic is still the same choose → explore → un-choose template, but here the is_valid check inside the loop is no longer a minor guard — it is the entire algorithm. Everything you optimize is either "how cheaply can I check validity" or "how early can I detect a dead end."

def backtrack(state): if is_complete(state): record_solution(state) return for choice in next_choices(state): if not can_place(state, choice): # the expensive, load-bearing check continue make_choice(state, choice) backtrack(state) undo_choice(state, choice) # mutation + undo, not just list append/pop

The key mental shift from the previous two subtopics: state is no longer just a growing list you append to and pop from. It's a mutable shared structure — a chessboard, a Sudoku grid, a 2-D character grid — and "choose" and "un-choose" mean mutating and then precisely restoring specific cells of that structure.

Structure the search before you prune

Before optimizing is_valid, ask: what is one decision per recursion level?

Constraint problems are often secretly "assign a value to the next variable," not "pick any free cell / any free slot on the board." If the search is allowed to place pieces in any order among unordered positions, the same complete configuration is rediscovered through many construction paths — and the usual bandage is a seen set of finished boards or strings. That set is a smell: fix the branching so each solution has one canonical construction order, then you won't need to dedupe at the leaves.

The general move:

  1. Find an invariant that partitions the problem into an ordered sequence of variables (one queen per row; one digit per empty cell in a fixed scan order; the next IP octet among exactly four; the next character index in a target word).
  2. Make recursion depth = the next variable to assign.
  3. At that level, only try the domain of that variable (columns for this row; digits 1–9 for this cell; slice lengths 1–3 for this octet; the four neighbors for this letter).
  4. Encode constraints incrementally (sets, bitmasks, in-place markers) so can_place is O(1) — don't rescan the whole board on every try.
Problem shapeVariable at depth dDomain to tryWhat you stop doing
N-Queensrow dcolumns 0..n-1picking any free cell in any order
Sudokunext empty cell (fixed order)digits 1..9trying every cell as "where to write next"
Restore IP Addressesnext octet among 4lengths 1..3placing dots in arbitrary index sets
Permutationsnext position in the resultunused elementsgenerating the same ordering via different index sequences (→ duplicate-skip / used[])
Word Searchnext index in wordup to 4 neighborstreating the board as an unordered bag of free cells

This is the same instinct as the duplicate-handling rule in Permutations: force a canonical order among symmetric choices so the tree doesn't re-derive the same answer. Here the symmetry is spatial or positional ("which queen did I place first?") rather than equal values.

Rule of thumb: if your solution needs a hash set of completed configurations to uniquify the output, the decision variables are almost certainly wrong. Pruning inside can_place is still essential — but structuring the variables is the pruning that happens before the first recursive call.

N-Queens: state tracking without O(n) re-scans

The N-Queens problem places n queens on an n × n board so no two attack each other (same row, column, or diagonal). Apply the section above: two queens can never share a row, so the variable at depth r is "column for row r" — place exactly one queen per row and recurse row by row. That alone collapses the search from "choose among n² cells, then dedupe boards" down to "choose one column per row," which is already the first and most important pruning decision in the problem.

The naive is_valid check re-scans the whole board for conflicts on every placement — O(n) work per check, O(n) checks per row, O(n) rows, so O(n²) work just for validation on top of the O(n!)-shaped search tree. The standard optimization tracks three sets of "attacked" lines and updates them incrementally as you place/remove a queen, turning each validity check into O(1):

def solve_n_queens(n): col = set() pos_diag = set() # identified by (row + col) — constant along "/" diagonals neg_diag = set() # identified by (row - col) — constant along "\" diagonals res = [] board = [["."] * n for _ in range(n)] def backtrack(row): if row == n: res.append(["".join(r) for r in board]) return for c in range(n): if c in col or (row + c) in pos_diag or (row - c) in neg_diag: continue # O(1) pruning check col.add(c); pos_diag.add(row + c); neg_diag.add(row - c) board[row][c] = "Q" backtrack(row + 1) col.remove(c); pos_diag.remove(row + c); neg_diag.remove(row - c) board[row][c] = "." backtrack(0) return res

The insight that every cell on the same "/" diagonal shares the same row + col value (and every cell on the same "" diagonal shares the same row - col value) is what makes O(1) diagonal-conflict checking possible — it's a small piece of coordinate geometry that turns into a huge constant-factor win. Every choice here touches five pieces of state (board, col, pos_diag, neg_diag, implicitly row), and every one of them must be undone on the way back up. Miss undoing one set and every subsequent branch inherits a phantom conflict — the search silently returns fewer solutions than exist, without crashing or throwing any error, which makes it a nasty bug to catch.

Sudoku and Word Search: board mutation + undo

Sudoku Solver and Word Search share a pattern: the "board" itself doubles as the visited/state tracker, so you mutate a cell directly, recurse, and then restore the cell's original value:

# Word Search: is `word` reachable starting from (r, c)? def exist(board, word): rows, cols = len(board), len(board[0]) def dfs(r, c, i): if i == len(word): return True if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[i]: return False original = board[r][c] board[r][c] = "#" # mutate: mark visited in place found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1) or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1)) board[r][c] = original # undo: restore before returning return found return any( dfs(r, c, 0) for r in range(rows) for c in range(cols) if board[r][c] == word[0] )

Using a sentinel character ("#") as the "visited" marker avoids allocating a separate visited set — O(1) extra space instead of O(word length) — but it only works because you reliably restore the original character on every exit path, including early return False paths that happen before your undo line if you're not careful with the control flow (the and/or short-circuit chain above deliberately runs the undo after all four recursive attempts, not interleaved with them).

Sudoku Solver follows the identical shape: find an empty cell, try digits 1–9, mutate the cell, recurse, and reset the cell to empty (.) if the recursive call fails. The pruning lever here is the is_valid(board, row, col, digit) check — the naive version rescans the row, column, and 3×3 box (27 cells) on every attempted digit; the optimized version maintains bitmasks or boolean arrays per row/column/box (the same "avoid O(n) re-scans" idea as N-Queens's diagonal sets) so each check becomes O(1) instead of O(1) work amortized over a fixed 27-cell scan.

Why pruning is the difference between milliseconds and a timeout

All three problems have a nominally exponential-or-worse search space:

  • N-Queens: naively placing queens anywhere is n² choose n; restricting to one per row drops it to nⁿ; adding column/diagonal pruning drops the actually visited tree to a small fraction of n!.
  • Sudoku: naively, 81 cells × 9 digits is 9^81 — astronomically impossible. Restricting to only empty cells and only valid digits per the row/column/box constraints is what makes the problem tractable at all.
  • Word Search: naively exploring all 4 directions from all m × n starting cells for a word of length L is O(m · n · 4^L) — pruning via the sentinel visited-marker (never revisit a cell in the same path) and the immediate character-mismatch check keeps real-world grids fast.

The recurring theme: the worst-case asymptotic complexity does not change — it's still exponential/factorial in the input size — but a cheap, correct is_valid/can_place check applied as early as possible (before recursing, not after) prunes entire subtrees in O(1), and in practice this is the difference between a solution that returns in milliseconds and one that times out. This is the same worst-case-vs-practical distinction from Subsets & Combinations and Permutations, just with the stakes much higher because these search trees are denser and the constraints tighter.

State representation comparison

ProblemWhat "state" is mutatedUndo mechanismValidity check cost (naive → optimized)
N-Queenscol, pos_diag, neg_diag sets + boardRemove from sets, reset board cellO(n) rescan → O(1) set lookup
Sudoku SolverBoard cell + row/col/box trackersReset cell to ., clear tracker bitsO(27) rescan → O(1) bitmask check
Word SearchBoard cell (sentinel char) or separate visited gridRestore original character or unmark visitedO(1) inherently — cost is in branching (4 directions), not validity

Complexity analysis

State the exponential/factorial classes precisely, the same way you would for Subsets & Combinations (O(2ⁿ)) and Permutations (O(n!)):

  • N-Queens: worst-case O(n!) — one queen per row, decreasing valid columns per row due to pruning, structurally similar to a permutation search over columns.
  • Sudoku Solver: worst-case O(9^m) where m is the number of empty cells — bounded by trying up to 9 digits per empty cell.
  • Word Search: O(m · n · 4^L) where L is the word length — 4 directions per character, attempted from every starting cell.

As in the earlier subtopics, quote both the theoretical worst case and the practical effect of pruning when discussing these in an interview: "Worst case is O(n!), but column/diagonal pruning means we discard the vast majority of the tree before ever reaching depth n — in practice N-Queens for n=8 explores a few thousand nodes, not 8! ≈ 40,000, and far less than 8⁸ ≈ 16 million." Precision about which number you're citing (raw branching factor to the power of depth, vs. the tighter factorial bound after the "one per row" restriction, vs. actual pruned node count) is exactly the kind of rigor a Senior-level interviewer is listening for — the same instinct covered generally in the Problem-Solving Framework & Interview Communication topic.

Common pitfalls

  • Searching an unordered placement space, then deduping finished solutions. Trying "any free cell" (or any free slot) at every step and stuffing complete boards/strings into a seen set "fixes" uniqueness by brute force. Prefer an ordered variable sequence (one assignment per row / empty cell / octet / character index) so each solution is constructed once.
  • Checking validity after recursing instead of before. The entire point of pruning is to avoid descending into a doomed subtree. If you recurse first and check validity inside the base case, you've paid the full cost of the search anyway — the check must gate the recursive call, not follow it.
  • Forgetting to undo a mutation before backtracking — the #1 backtracking bug, again, at higher stakes. In subsets/permutations, forgetting to undo corrupts some future output. Here, forgetting to remove a queen's column/diagonal markers, or forgetting to reset a Sudoku cell to ., or forgetting to restore a Word Search sentinel character, corrupts the shared board/state for every subsequent sibling branch in the entire remaining search — a much larger blast radius because the state is global and heavily reused, not a simple list. Early return True paths are a common place this slips — every exit must restore state (or you must structure control flow so undo always runs).
  • O(n) validity re-scans that silently dominate runtime. A correct-but-naive isSafe/isValid function that rescans the row, column, diagonals, or 3×3 box from scratch on every call is a common reason an otherwise-correct backtracking solution times out. Encode constraints in incremental trackers (sets, bitmasks, boolean arrays) instead of rescanning.
  • Off-by-one errors in diagonal identification. row + col and row - col are the standard diagonal identifiers, but row - col can be negative — if you're using an array instead of a set/hash map for neg_diag, you need an offset (row - col + n) to keep the index non-negative.
  • Mutable shared board passed without cloning at the point of recording a solution. When you find a valid complete configuration (e.g., a Sudoku solution or an N-Queens board), you must copy/serialize it into the results at that moment — the same "copy, not reference" bug from Subsets & Combinations and Permutations applies here too, just applied to a 2-D board instead of a 1-D list.

Further Resources (Optional)

Practice Problems

Interview relevancy:!!!Critical — must-have!!Important — highly recommended!Good to have~Niche — rarely asked

Optional Practice (Extra Reps)

For once you've cleared the main set above and want more reps on this pattern. These don't count toward the roadmap's progress stats — solve them purely for your own benefit.