In N-Queens, how do column and diagonal sets make each attack check O(1) instead of a scan?
answer
- what do mutually attacking cells share
- one arithmetic relation per diagonal direction
- sum of coordinates, difference of coordinates
- differences go negative, so shift them
- three constant-time lookups, no scan
basics
~20 sThree occupancy structures replace the scan: one keyed by column, one by row plus column, one by row minus column. Cells sharing a diagonal share one of those derived keys, so a candidate square is cleared with three constant-time lookups.
solid answer
~50 sTwo cells lie on the same "/" diagonal exactly when `row + col` is equal, and on the same "\\" diagonal exactly when `row - col` is equal. Those derived values are the keys: keep one occupancy structure per constraint family — columns, `row + col`, `row - col` — mark all three when a queen is placed and clear all three when the branch is abandoned. Testing a candidate is then three lookups, not a walk over every queen placed so far, which removes an `O(n)` factor from the work at every node. The trap is the third family: `row - col` ranges from `-(n-1)` to `n-1`, so with plain arrays you must add an offset of `n-1` and size the array `2n-1`. Offsetting by less, or sizing at `n` or `2n-2`, is the classic out-of-bounds or wrong-collision bug.
code
pseudocode · 13 linesPLACE-QUEENS(row):
if row == n:
report(placement)
return
for col in 0..n-1:
d1 = row + col // range 0 .. 2n-2
d2 = row - col + (n - 1) // range 0 .. 2n-2
if cols[col] or diagA[d1] or diagB[d2]:
continue
placement[row] = col
cols[col] = true; diagA[d1] = true; diagB[d2] = true
PLACE-QUEENS(row + 1)
cols[col] = false; diagA[d1] = false; diagB[d2] = falsego deeper
Recall that cells on one diagonal share a fixed sum or a fixed difference of their coordinates, and that this lets you test a square by lookup instead of comparing it against every queen already on the board.
Derive both keys out loud, state the ranges, and size the difference array 2n - 1 with an offset of n - 1. Show the mark and the matching unmark, and say why exactly three keys change on each placement.
Separate per-node cost from tree size: the trick removes a factor of n per node and leaves the explored tree untouched. Be able to spot a state-key bug from a symptom such as a solution count that is too low.
Own the readability-versus-speed call. Argue when the derived-key encoding is worth the extra invariants a future maintainer must preserve, and how you would guard it — for example by cross-checking counts against a slow reference for small board sizes in tests.
## Why a scan is the natural first answer, and what it costs The obvious validity test is: for each queen already placed, check whether the candidate square shares its column or lies on one of its diagonals. Placing into row `r` means `r` queens are on the board, so the test is `O(r)`, i.e. `O(n)` in the worst case. Multiply that by the number of nodes the search visits and you have paid an extra factor of `n` for information that never needed to be recomputed. ## Turning a relation into a key The fix is to notice that "attacks" is an equivalence-style relation with a cheap invariant per family. Index the board with `row` increasing downward and `col` increasing to the right: | Constraint family | Invariant shared by all cells in it | Key range | |---|---|---| | Column | `col` | `0 .. n-1` | | Anti-diagonal ("/") | `row + col` | `0 .. 2n-2` | | Main diagonal ("\\") | `row - col` | `-(n-1) .. n-1` | Check the anti-diagonal claim on a 4-wide board: `(0,3)`, `(1,2)`, `(2,1)`, `(3,0)` all have `row + col == 3`, and they do form a "/" line. For the main diagonal, `(0,0)`, `(1,1)`, `(2,2)` all have `row - col == 0`. Moving one step down-right adds one to both `row` and `col`, leaving the difference fixed and increasing the sum by two — which is exactly why one family is keyed by the sum and the other by the difference. Since each family partitions the board into disjoint lines, "is any queen on my line?" becomes "is this line's key marked?". Keep one boolean occupancy structure per family. Placing sets three keys; undoing clears the same three. The row family needs nothing, because the search already assigns one queen per row. ## The negative-index trap and the off-by-one `row - col` is negative whenever the queen sits right of the main diagonal, so it cannot index a plain array directly. Add `n - 1`: - minimum: `0 - (n-1) + (n-1) = 0` - maximum: `(n-1) - 0 + (n-1) = 2n - 2` So the array length must be `2n - 1`, not `2n - 2` (the maximum index is `2n-2`, and an array of that length tops out at `2n-3`) and not `n` (which cannot hold `2n-1` distinct lines and would silently fuse two different diagonals into one key — a wrong answer, not a crash). The `row + col` family needs no offset but the same `2n - 1` length. If instead of arrays you use a keyed set, the offset is unnecessary — negative keys are fine — which is precisely why the bug appears when someone switches from a set to an array for speed. ## What it changes and what it does not The derived-key trick removes an `O(n)` factor from the per-node work: each candidate square is now three lookups and, on acceptance, three writes plus three writes to undo. It does **not** change the number of nodes explored — the shape of the search tree is identical to the scanning version, and the algorithm remains exponential. Anyone who says "constant-time checks make it polynomial" has confused per-node cost with tree size. The honest statement is: same tree, `n` times cheaper per node. The undo is not optional bookkeeping. The three structures describe the *current* partial placement; leaving a key set after abandoning a branch marks a queen that is no longer there, and the search will then reject legal squares and under-report solutions. Symmetrically, clearing a key you did not set corrupts a sibling branch's state. ## Where the idea generalizes Any constraint of the form "no two chosen items may agree on some function of their position" collapses to a set keyed by that function. Placement puzzles on grids reuse the sum and difference keys constantly. Constraints that are *not* line-shaped do not collapse this way: forbidding two queens a knight's move apart is a relation on a small fixed neighbourhood, not a partition of the board, so it stays an explicit check of a handful of nearby cells — still constant time, but for a different reason. ## Interview register "Cells on a shared diagonal have equal `row + col` or equal `row - col`, so I keep three occupancy structures — column, sum, difference — and a candidate is three lookups. If those are arrays I offset the difference by `n - 1` and size both diagonal arrays `2n - 1`. Placing marks the three keys, backtracking clears exactly those three. It removes a factor of `n` per node; the tree is unchanged."
- What exactly does the undo step reset, and what breaks if a branch skips it?It clears the same three keys the placement set: the column, `row + col`, and `row - col`. Skipping it leaves a phantom queen recorded on lines that are actually empty, so later sibling branches reject legal squares and the search under-reports or misses solutions entirely. Clearing keys you did not set is the mirror bug, wrongly freeing lines another queen still occupies.
- Does the constant-time check change the algorithm's asymptotic complexity?It changes the per-node cost from `O(n)` to `O(1)`, so total work drops by a factor of `n`. The number of nodes explored is identical — the same partial placements are visited in the same order — so the search remains exponential in `n`. It is a large constant-and-linear-factor win, not a complexity-class change.
- If the rules also forbade two queens a knight's move apart, would the same key trick extend?Not directly. Knight-move conflicts do not partition the board into lines, so there is no single derived value that all conflicting cells share. Since rows are filled top to bottom, you instead check the four specific cells two rows up and one column aside, or one row up and two columns aside, against a per-cell occupancy record. Still constant time, but as a fixed-size neighbourhood check rather than a line key.
Each diagonal is a numbered lane on the board; instead of asking every queen whether it shares your lane, you just check whether your lane number is already taken.
saying these in an interview costs you the question
- Says the diagonal check must scan every queen placed so far
- Uses row+col for both diagonal directions
- Indexes an array with row-col without adding an offset
- Sizes the diagonal arrays at n or 2n-2 instead of 2n-1
- Forgets to clear all three keys when abandoning a branch
- Claims constant-time checks make the search polynomial