Constraint placement with pruning

45 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Place 4 queens on a 4×4 chessboard so that no two share a row, a column or a diagonal. By hand you put a queen in row 0, then try to place one in row 1 that is not attacked, then row 2, and when row 2 has no safe square you go back and move the row 1 queen. That back-and-forth is the whole method; the only question is how to do it without losing track.

Why not try every arrangement? Choosing one square per row gives 4⁴ = 256 boards for n = 4, but 8⁸ ≈ 16.8 million for n = 8 and 10¹⁰ for n = 10. Most of those boards are wrong in their first two rows, and a method that checks the whole board at the end wastes everything it did after the first mistake.

Build the structure, one piece at a time

Piece one: place queens one row at a time, so the row rule is automatic and the search is a sequence of decisions, one per row.

Piece two: a fast way to answer "is this square attacked?". Keep three sets: columns in use, and the two diagonal families. A square (r, c) lies on the diagonal numbered r − c and the anti-diagonal numbered r + c, so three set lookups replace scanning the board.

Piece three, the rule: place(row): if row = n, a full solution exists. Otherwise for each column c: if c, r − c and r + c are all free, add them to the sets, recurse on row + 1, then remove them and try the next column. Removing is the undo that lets the search move the earlier queen.

Why it is correct

The invariant: at every moment the queens on the board attack none of each other, and the three sets describe exactly those queens. A queen is only placed on a square whose column and both diagonals are free, so adding it keeps the board legal; removing it on the way back restores the sets. The loop over columns, with backtracking, visits every legal partial board, so if a full solution exists it is reached, and a board accepted at row n is legal by the invariant.

Why it is fast

Pruning means a branch dies at the first illegal row rather than at the end. For n = 8, brute force examines about 16.8 million boards; the pruned search visits roughly 2,000 partial boards. There is no neat closed form, which is why the complexity is quoted as "exponential with pruning", but the gap in practice is thousands to one. Each legality check is three constant-time set lookups rather than a scan of up to n queens.

How to recognise it in an interview

Cues: "place items so that no two conflict", "fill the grid so every row, column and box is valid", "find an arrangement satisfying constraints", with a small board. The first thing to say: "I will fill one position at a time, check the constraints before recursing, and undo on return." N-Queens is the example above. Sudoku Solver is the same with nine candidates per empty cell and three sets per row, column and 3×3 box. 24 Game and Expression Add Operators use the same skeleton with operators as the choices.

02The idea in one line

Place one item per row/cell; check constraints before recursing; prune early.

Reach for it when: N-queens, sudoku solver, valid arrangement, 24 game.

Cost: exponential with pruning.

03The walk-through, step by step

The video works one example: 4-Queens. These are its captions in order, so you can follow without the video or check a step you missed.

1. Place one queen per row; a cell is legal only if no column or diagonal is taken
2. Row 0: column 0 is free, place a queen
3. Row 1: column 2 is free, place a queen
4. Row 2: every column attacked, backtrack to row 1
5. Row 1, column 2 leads nowhere: remove it, try the next column
6. Row 1: column 3 is free, place a queen
7. Row 2: column 1 is free, place a queen
8. Row 3: every column attacked, backtrack to row 2
9. Row 2, column 1 leads nowhere: remove it, try the next column
10. Row 2: every column attacked, backtrack to row 1
11. Row 1, column 3 leads nowhere: remove it, try the next column
12. Row 1: every column attacked, backtrack to row 0
13. Row 0, column 0 leads nowhere: remove it, try the next column
14. Row 0: column 1 is free, place a queen
15. Row 1: column 3 is free, place a queen
16. Row 2: column 0 is free, place a queen
17. Row 3: column 2 is free, place a queen
18. All 4 rows filled: solution found
19. Sets for columns and diagonals make each check O(1); pruning kills most branches

04Asked at Google

8 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Backtracking: Subsets (include / exclude), Permutations with a used set, Combination sum with a start index, Grid DFS with undo, Generate valid sequences.