Backtracking

Constraint Search

Search with pruning: N-Queens, Sudoku, word search.

Hard, about 120 minutes to practise.

1Understand

The idea

Search the choices one at a time and prune as soon as a partial solution breaks a rule, instead of building complete candidates and checking them at the end. Keeping fast lookups of what is already used (columns, diagonals, box digits) makes each check O(1), which is what makes the search finish.

Intuition

Search choices one at a time and prune as soon as a partial assignment breaks a rule, instead of building complete candidates and checking at the end. Early failure is what makes N-Queens and Sudoku finish.

Keep fast structure for constraints already used, columns, diagonals, box digits, so each check is O(1). Place, recurse, unplace (restore the structures).

Order matters: trying more constrained positions first (MRV) often prunes harder, but the clear place/remove skeleton is the priority in interviews.

What you will be able to do

  • Prune early with O(1) validity checks
  • Restore state on backtrack

When to use it

  • Place items so no two conflict
  • Fill a board satisfying rules
  • Find a word in a grid

2See it

Walkthrough

N-Queens prune

n=4, place a queen only if col/diag free.

1 / 6

i
.
.
.
.
0123
i → index 0

Row 0 empty. cols/diags empty sets. Try column 0.

if c in cols or diag busy: continue

Live template

Line 1 active

1def solve(state):
2 if complete(state): return True
3 for choice in candidates(state):
4 if valid(state, choice):
5 apply(choice)
6 if solve(state): return True
7 undo(choice)
8 return False

Complexity: time exponential with pruning, space O(depth)

Worst case still exponential, but pruning makes realistic n feasible. Checking only at full boards explores far more dead ends. O(1) constraint lookups are worth the small extra space.

Read the walkthrough as text

N-Queens idea for n = 4.

  1. Place a queen row by row. In row 0, try columns; record col, diag r-c, anti r+c.
  2. A placement that shares any of those with a prior queen is illegal, skip.
  3. Reach row 4 → record a solution; backtrack and try the next column.
  4. Two distinct solutions exist for n = 4.

Sudoku is the same: try digits 1-9 in the next empty cell, prune with row/col/box sets.

3Recognise it

Kinds of problems (7)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • N-Queens

    Example. Place n queens with no attacks.

    How. Row-by-row; track cols and diagonals with sets; prune before recurse.

  • Sudoku solver

    Example. Fill empty cells so rows, columns, boxes are 1-9.

    How. Find next empty; try digits with O(1) row/col/box validity via sets.

  • Word search in a grid

    Example. Find a word by adjacent letters.

    How. DFS from each cell matching first letter; mark visited, undo on backtrack.

  • Palindrome partitioning

    Example. Split string into all palindrome part lists.

    How. Try each cut; recurse on suffix when prefix is palindrome.

  • Partition into k equal subsets

    Example. Split array into k subsets with equal sum.

    How. Target sum = total/k; backtrack assign each number to a bin under capacity.

  • Split a string into valid parts (IP addresses)

    Example. Restore all valid IPv4 strings from digits.

    How. Place dots at valid segment lengths 1-3; prune invalid numbers early.

  • Insert operators between digits (expression target)

    Example. Combine digits with +−× to hit target.

    How. Track running total and last term for ×; branch operators at each gap.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Late pruning

    Why it happens. Checking board only when all queens placed still eventually finds solutions.

    How it fails. N-Queens places conflicting queen in column 3 at row 1 then explores millions of dead rows.

    Fix. Reject candidate before recurse with O(1) col/diag sets.

  • State not restored

    Why it happens. Undoing the last choice feels enough when cells were “empty”.

    How it fails. Sudoku marks 9 in cell, backtracks without clearing, grid stuck wrong for siblings.

    Fix. undo(choice) must revert every mutation (board char, counts, visited flags).

  • Slow validity check

    Why it happens. Rescanning the full board is obviously correct.

    How it fails. Sudoku tries digit, scans all 81 cells every time, search tree explodes.

    Fix. Maintain row/col/box sets updated on place/remove.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons