What Is the N-Queens Problem?
N-Queens places N queens on an N×N board so none attack each other (or counts the ways to do so). A queen attacks along its row, column, and both diagonals, so no two queens may share a row, column, or diagonal. It's the textbook example of backtracking.
The one-line idea: "one queen per row; if it doesn't work, back up." Instead of blindly trying every arrangement, abandon a path the moment it's stuck and return to a different choice.
The Core Is Backtracking
By deciding to place one queen per row, row conflicts vanish automatically. Only columns and diagonals remain.
Backtracking works like this: place a queen in a safe column of the current row and recurse into the next row; if there's nowhere to place one (stuck), remove the queen just placed and back up to the previous row to try a different column.
Pruning
Scanning the whole board each time is slow. Recording column usage and both diagonal usages in boolean arrays lets you judge a square's safety in O(1).
- •same column:
col[c] - •↘ diagonal: same
row + col - •↙ diagonal: same
row - col(offset by+N-1to avoid negatives)
Cutting impossible branches immediately shrinks the search a lot.
How It Works
Step 1. Start at row = 0.
Step 2. For each column c in the current row, if the column and both diagonals are free, place a queen, mark them, and recurse to row + 1.
Step 3. When the recursion returns (success or failure), clear the marks and remove the queen (backtrack) — so the next column gets a fair try.
Step 4. Reaching row == N means all N are placed — one solution complete.
The AlgoNote visualization color-codes queens being placed, getting stuck, backing up, and being removed, step by step.
Time and Space Complexity
| Complexity | |
|---|---|
| Time | near O(N!) worst case (much less with pruning) |
| Space | O(N) |
Pruning makes the real search far smaller than N!.
Walking Through an Example
4-Queens:
- •place (row0,col0) → row1 only col2 is safe → row2 has no safe spot → back up
- •place (row0,col1) → row1 col3 → row2 col0 → row3 col2 → solution complete
- •4-Queens has exactly 2 solutions.
Common Mistakes
- •Diagonal indices: mixing up
row+colandrow-col(offset by N-1) misaligns the conflict check. - •Not restoring state: after returning from recursion you must undo the column/diagonal marks and remove the queen (the heart of backtracking).
- •Confusing the goal: "count of ways" vs "one arrangement" changes when you stop.
See It in Action on AlgoNote
Watch queens get placed one row at a time and the search back up to try another column when stuck, step by step on AlgoNote.