N Queens Problem
The N-queens problem asks: place N queens on an N-by-N chessboard such that no two queens attack each other. Two queens attack each other if they share the...
Problem Definition and Constraint Model
The N-queens problem asks: place N queens on an N-by-N chessboard such that no two queens attack each other. Two queens attack each other if they share the same row, the same column, or the same diagonal. Find all valid arrangements (or determine if any exist, or count them).
The key insight for efficient constraint representation: since no two queens can share a row, place exactly one queen per row. This reduces the problem to finding a column assignment c[i] for each row i such that no two queens conflict. With this structure, the search space is N^N naive (N choices per row), but constraint pruning reduces it dramatically.
Three constraint checks are needed: column uniqueness (no two queens in the same column), left-diagonal uniqueness (for queens at (r1, c1) and (r2, c2), conflict if r1 - c1 == r2 - c2), and right-diagonal uniqueness (conflict if r1 + c1 == r2 + c2). Use three boolean arrays (or sets) — cols[], left_diag[], right_diag[] — to track which columns and diagonals are occupied. Checking a placement is O(1) with these arrays.
Algorithm: place queens row by row. For each row, try each column; if the column and both diagonals are free, place the queen (mark col, left diagonal, right diagonal as occupied), recurse to the next row, then unplace (unmark).
Time complexity: O(N!) in the worst case (N choices for row 1, at most N-2 for row 2 due to column and diagonal constraints, etc.), but far fewer branches survive pruning in practice. Space: O(N) for the recursion stack and O(N) for the tracking arrays.
Interview tip: Immediately represent the constraint using the three arrays. Saying "I will track occupied columns, and diagonals using row-minus-col and row-plus-col values" shows you know the mathematical structure of the constraint, not just that the problem exists.
Implementation and Board Reconstruction
A clean N-queens implementation uses recursion with explicit state passed by reference. The three boolean arrays cols[N], left_diag[2N-1], and right_diag[2N-1] track which columns and diagonals are taken. The current placement is stored in an integer array queen_col[N] where queen_col[i] = j means the queen in row i is placed at column j.
Pseudocode: solve(row): if row == N, record current placement (a valid solution). For each col from 0 to N-1: if not cols[col] and not left_diag[row - col + N - 1] and not right_diag[row + col]: mark col, left_diag[row-col+N-1], right_diag[row+col] as true. queen_col[row] = col. solve(row + 1). Unmark col, left_diag, right_diag. (The offset N-1 in left_diag ensures non-negative indices.)
To reconstruct and print the board from a solution, iterate rows 0 to N-1; in row i, print '.' for all columns except queen_col[i], where you print 'Q'. This gives the standard chessboard visualization.
Counting all solutions for small N: N=1: 1, N=4: 2, N=5: 10, N=6: 4, N=7: 40, N=8: 92. These are well-known values — if your implementation produces different counts, there is a bug.
For large N (N > 20), an iterative approach with an explicit stack or heuristic methods (like simulated annealing or constraint propagation with backtracking) perform better because the recursive call stack depth is N and the recursion overhead is more significant.
Interview tip: Test your implementation on N=4 (the smallest N with multiple solutions) and verify you get exactly 2 solutions. Then test N=8 and verify 92 solutions. These small tests confirm both correctness and completeness without requiring large inputs.
Optimizations and Bit Manipulation Tricks
For competitive programming, a highly optimized N-queens solution uses bit manipulation to represent the constraint state. Instead of boolean arrays, represent the occupied columns and diagonals as integer bitmasks. The key operations are: check if a column is free (AND with column bitmask equals zero), place a queen (OR the bitmask in), shift diagonals by one position each row.
Bit manipulation solution for N-queens counting: represent the state as three integers — cols (occupied columns), left_diag (occupied left diagonals, shifted left each row), right_diag (occupied right diagonals, shifted right each row). Free positions for the current row are given by available = full_mask AND NOT (cols OR left_diag OR right_diag), where full_mask = (1 << N) - 1. Extract the rightmost set bit: bit = available AND (-available). Place queen: recurse with (cols OR bit, (left_diag OR bit) << 1, (right_diag OR bit) >> 1). Clear bit: available = available XOR bit. This isolates each available position as a single bit and explores each one.
This bitmask approach reduces constant factors significantly because bitwise operations are extremely fast and the state is packed into three integers. For N=17 (the largest N where all solutions are typically counted in benchmarks), this approach runs in seconds while the naive approach takes much longer.
Symmetry pruning is another optimization: the board has 8-fold symmetry (rotations and reflections). By constraining the first row's queen to the left half only, you find half the solutions and double the count (plus special handling for the center column when N is odd). This halves the search time.
Interview tip: The bitmask trick for N-queens is a memorable showpiece of bit manipulation. If you implement and explain it correctly in an interview, it stands out. However, start with the clear boolean array version first to show you understand the algorithm, then offer the bitmask optimization as an improvement.