Where it runs
1. The problem
Put 4 chess queens on a 4×4 board so that no two of them attack each other. A queen attacks along its row, its column and both diagonals. So no two queens may stand on the same such line. The same kind of problem comes up in exam timetables: two exams that share students can't go in the same time slot. Or with meetings: two meetings with a shared participant must not overlap.
You could list every way to place the pieces and then throw out the invalid ones. On a normal 8×8 board there are 4,426,165,368 ways to place 8 queens, and only 92 of them are valid. If you check the rule only at the end, when all the pieces are down, almost all the work goes into layouts that went wrong at the second piece.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- generate all subsets/permutations/combinations
- n is small (roughly n <= 12-20), exponential search is acceptable
- make a choice, recurse, then undo it before trying the next choice
- place items under constraints and back off on conflict (N-Queens, Sudoku)
- return every valid arrangement, not just one
Looks similar, isn't
- Recursion
Recursion goes down and comes back. Backtracking also puts the state back as it returns.
- Recursion with memoization
A cache pays off when arguments repeat. Down a path of distinct choices they rarely do.
- Dynamic programming (1-D)
DP counts or optimises without listing anything. Backtracking is for when you need the arrangements.
- Matrix word search (grid DFS/backtracking)
That is this pattern on a grid. The choice there is which neighbour to step into.
The output is exponential, so n stays small. Subsets of 20 items are 1e6, permutations of 10 are 3.6e6.
On LeetCode
Placement puzzles where pieces must not clash, such as queens on a board or digits in a sudoku. Keep sets of used rows, columns and diagonals, check them in O(1) before each placement, and undo on the way back.
Only the bookkeeping half of the lesson, one set per row, column and 3 by 3 box, with no search.
Fill positions one by one with unused numbers and cut a branch as soon as the divisibility rule fails.
The lesson task exactly, with the row minus col and row plus col diagonal sets.
Try 1 to 9 in each empty cell, check the row, column and box sets, and undo when a later cell gets stuck.