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
Row 0 empty. cols/diags empty sets. Try column 0.
Live template
Line 1 active
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.
- Place a queen row by row. In row 0, try columns; record col, diag
r-c, antir+c. - A placement that shares any of those with a prior queen is illegal, skip.
- Reach row 4 → record a solution; backtrack and try the next column.
- 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.