N-Queens
WHAT IT SAYS
Place n queens on an n x n board so that no two attack each other along a row, a column, or a diagonal, and return every distinct arrangement.
WHAT IT'S REALLY ASKING
"A safe board is not something you inspect at the end — each queen forbids squares the moment it lands. And notice what you never have to ask: if you place exactly one queen per row by construction, the row rule cannot be broken. It stops being a check and starts being a fact about the shape of your search."
Choose n squares out of n-squared, then verify
O(C(n*n, n) * n^2) — about 4.4 billion arrangements for an 8x8 boardEnumerate every way to pick n squares from the n*n available, and for each arrangement check all pairs of queens for a shared row, column or diagonal.
WHERE THE WORK IS WASTED — Almost everything you generate is illegal for a reason you could have made impossible. There are n queens and n rows, so by pigeonhole any arrangement that puts two queens in one row is dead on arrival — and the overwhelming majority of your C(n*n, n) arrangements do exactly that. You spend billions of constructions producing configurations that violate a constraint, and then you pay an O(n^2) pairwise scan to inform yourself of what the pigeonhole principle knew for free.
Fold the constraint into the shape; checking disappears.
Two moves, both of which convert a runtime check into a structural fact. First: n queens, n rows, and no two queens may share a row. By pigeonhole that forces exactly one queen per row — not 'at most', exactly. So represent a candidate not as a set of squares but as an array col[row]: a function from each row to the column its queen occupies. In that representation, two queens in one row is not merely forbidden, it is UNREPRESENTABLE. The row constraint has vanished from the code entirely, and with it the vast majority of the search space. That is the strongest form of pruning there is: not cutting the dead branch, but building a tree that never grew it. Second: what is left is columns and diagonals, and both have closed forms. Two squares lie on the same descending diagonal exactly when row minus column is equal, and on the same ascending diagonal exactly when row plus column is equal. Those are invariants, so 'is this square attacked?' becomes three O(1) lookups — one set of used columns, one of used values of (row - col), one of used values of (row + col) — instead of a scan across the board. And the pruning is sound for the usual reason: adding queens never removes an attack. A conflict on a partial board is permanent, so the moment one appears, every completion beneath it is dead and the subtree can be cut with nothing lost.
One queen per row, three sets for the rest
O(n!) upper bound on the tree, savagely pruned in practice; O(n) extra spaceRecurse on the row index. For each column in that row, skip it if the column, the (row - col) diagonal, or the (row + col) diagonal is already occupied. Otherwise mark all three, place the queen, recurse into the next row, then unmark all three. When the row index passes the last row, every row holds a queen and no constraint was ever violated — record the board.
Make Illegal States Unrepresentable
YOU'LL SEE IT AGAIN WHEN
- A constraint says 'at most one per row / group', and the number of items equals the number of groups — so it is exactly one per group, and the group index can become your recursion depth.
- Conflict relations have closed-form invariants (row minus column, row plus column, a box index) that turn a board scan into a constant-time set lookup.
- Violations are permanent — adding more items can never repair a conflict — which is what makes cutting the subtree sound rather than merely hopeful.