Overview
The N-Queens problem asks you to place N chess queens on an N×N board so that no two queens attack each other — meaning no two share a row, a column, or a diagonal. It is the textbook example used to teach backtracking, because a queen's wide reach forces the search to prune bad placements aggressively.
Backtracking solves it by placing one queen per row and trying each column in turn. Whenever a placement conflicts with a queen already on the board, the branch is abandoned and the search 'backtracks' to try the next column — exploring the solution space like a depth-first walk of a decision tree.
How N-Queens works
- Work row by row: start at row 0 and try to place a queen in some column of the current row.
- Before placing, check that the chosen column has no conflict with earlier queens on the same column or either diagonal.
- If the placement is safe, recurse into the next row; the search descends one level deeper for each queen fixed.
- If no column in the current row is safe, backtrack: remove the previous queen and try its next available column.
- When a queen is safely placed on the final row, a complete solution has been found; continue backtracking to enumerate all solutions.
When to use it
- Teaching backtracking, pruning, and depth-first search on a decision tree.
- A benchmark for constraint-satisfaction solvers and heuristic search techniques.
- A model for real placement problems where items must not share rows, columns, or diagonals — such as conflict-free resource layout.
- Demonstrating how good pruning shrinks an otherwise explosive search space.
Complexity analysis
A naive placement of one queen per row over N columns gives a search tree bounded by O(N!), since each row has fewer safe columns than the last. Pruning on column and diagonal conflicts removes huge subtrees, so the practical cost is far below the worst case, but the asymptotic bound remains roughly O(N!). Space is O(N) for the recursion stack and the per-column/diagonal bookkeeping.
Frequently asked questions
Why is placing one queen per row enough?
Two queens on the same row would always attack each other, so any valid solution has exactly one queen per row. Fixing one queen per row removes the row constraint entirely and shrinks the search to choosing a column for each row.
How does the diagonal check work efficiently?
Two queens share a diagonal when the difference or the sum of their row and column indices is equal. Tracking used values of (row − col) and (row + col) in sets lets each safety check run in O(1) instead of scanning the board.
Does N-Queens always have a solution?
Solutions exist for every N except N = 2 and N = 3, where the board is too small to separate the queens. From N = 4 upward the number of distinct solutions grows quickly with N.