N Queens
Lesson 6 of 11
6♛ N Queens
Your first real backtracking: how to build a solution step by step and retreat the moment it becomes impossible, instead of trying every arrangement and waiting forever.
What the picture shows: Place one queen per row; when no column is safe, back up a row and try the next column, until [1, 3, 0, 2] comes out.
Map of this part
The concepts in order, click any one to jump to it:
Two ways into the same idea
You want to place several queens on a chessboard so none threatens another. You put one in each row, and whenever the new queen is under attack you lift it and try another square, and if no square works you step back to the previous row. That way you reach a solution without trying every possibility.
backtracking is a depth-first search that builds the solution step by step and prunes a branch once it breaks the constraints. You pick a column per row and check safety with three sets: columns and the two diagonals r - c and r + c. That cuts the search far below n^n.
Required fundamentals
Recursion
A function that calls itself on a smaller problem, with a stopping case. Here the smaller problem is "arrange the remaining rows", and the stopping case is reaching row n.
The set
An in check on a set is instant; on a list it walks the elements. That difference alone is what makes this solution fast.
Copying lists
lst[:] copies the list, while lst points at the same one. Confusing the two here makes every saved solution identical.
sys.argv
The command-line argument list, whose first item is the program name. Validate it precisely, since the error messages are specified character by character.
Core concepts
The task: place N queens on an N×N board so that none attacks another, and print every solution. A chess queen attacks along her row, her column and both diagonals, without limit.
1Why brute force does not work
Trying every arrangement of eight queens on 64 squares means over four billion cases. Even after the obvious improvement of one queen per row, you still face Nᴺ possibilities for N=8, which is 16.7 million. The problem is not the arithmetic; it is that you discover failure at the last step, after building the whole solution.
2The clever representation: one queen per row
The first design decision removes half the problem for free: since two queens in the same row always attack each other, every solution has exactly one queen in each row. So we do not ask "where do the queens go?" but "which column holds each row's queen?". The solution becomes a list of N columns.
[[0, 1], [1, 3], [2, 0], [3, 2]], notice the first numbers run 0, 1, 2, 3 in order. The output format itself tells you the representation is row-then-column and that rows come in order. Many design decisions are written in the example, not in the prose.3When do two queens attack? The arithmetic trick
The row is already handled by the representation, so three checks remain. The column is easy; the diagonals have a lovely trick:
| Direction | Condition | Why |
|---|---|---|
| Same column | c1 == c2 | direct |
| Diagonal ↘ | r1 - c1 == r2 - c2 | each step down moves one column right, so r - c is constant along the whole diagonal |
| Diagonal ↙ | r1 + c1 == r2 + c2 | each step down moves one column left, so r + c is constant |
The check becomes three subtractions and additions instead of walking every placed queen. We keep three sets: the used columns, the used r - c values, and the used r + c values. The whole test is:
if col in cols or (row - col) in diag or (row + col) in anti:
continue4Backtracking: build, and retreat the moment it is impossible
Backtracking in one sentence: build the solution piece by piece, and the moment the current piece becomes impossible, go back and try another. The difference from brute force is that you cut off a whole branch of possibilities at once, not a single possibility.
And every retreat requires cleanup: you lift the queen off the board and erase her entries from the three sets. Forgetting the cleanup is the number one backtracking bug, because the board stays polluted by a failed attempt.
cols.add(col) and forget cols.discard(col) after the recursive call, you will count columns from failed attempts as still occupied, and you will lose valid solutions. The rule: every add before the call has a matching discard after it, in reverse order.5Input validation: read the brief literally
This is where marks are lost for no reason, because the messages are specified exactly:
| Case | Message | Exit |
|---|---|---|
| The argument count is not one | Usage: nqueens N | exit(1) |
| The argument is not a number | N must be a number | exit(1) |
N is smaller than 4 | N must be at least 4 | exit(1) |
The order matters: check the count first, then the type, then the value. And import nothing but sys, the project explicitly forbids every other module.
pycodestyle 2.5 on Python 3.8; this one with PEP 8 (pep8 1.7) on Python 3.4. So: the first line is #!/usr/bin/python3, not #!/usr/bin/env python3, and no f-strings and no modern type annotations, they did not exist in 3.4.N=2 and N=3 have no solution at all: the board is too small for the queens to avoid each other. And N=1 has only the trivial solution of a single queen. The problem really begins at 4.How it works
Three pictures: the backtracking cycle, the real search tree for N=4, and when two queens attack.
Diagram 15, The full backtracking cycle: place, descend, and on failure lift and try the next; when columns run out, back up a row.
Diagram 16, The search tree for N=4 from column 0 and column 1. The entire left branch dies at row 2, and backtracking cuts it in one move instead of trying everything beneath it.
Diagram 17, The attack decision tree: the row is settled by the representation, leaving the column and the two diagonals, each of which collapses into a single number.
Worked example, step by step
We write the solution, run it on the two required examples, check the error messages, then measure the effect of pruning with real numbers. Every output below is real.
Step 1, the solution
#!/usr/bin/python3
"""Solve the N queens puzzle."""
import sys
def solve(n, row, cols, diag, anti, board, out):
"""Place one queen per row, backtracking when a row has no safe column."""
if row == n:
out.append([pair[:] for pair in board])
return
for col in range(n):
if col in cols or (row - col) in diag or (row + col) in anti:
continue
cols.add(col)
diag.add(row - col)
anti.add(row + col)
board.append([row, col])
solve(n, row + 1, cols, diag, anti, board, out)
board.pop()
anti.discard(row + col)
diag.discard(row - col)
cols.discard(col)
def main():
"""Validate the argument, then print every solution."""
if len(sys.argv) != 2:
print("Usage: nqueens N")
sys.exit(1)
try:
n = int(sys.argv[1])
except ValueError:
print("N must be a number")
sys.exit(1)
if n < 4:
print("N must be at least 4")
sys.exit(1)
out = []
solve(n, 0, set(), set(), set(), [], out)
for sol in out:
print(sol)
if __name__ == "__main__":
main()Note the [pair[:] for pair in board] when saving a solution: without it you save a reference to the very board that changes one line later, and you end up with identical or empty solutions.
Step 2, the two required examples
$ ./0-nqueens.py 4 [[0, 1], [1, 3], [2, 0], [3, 2]] [[0, 2], [1, 0], [2, 3], [3, 1]] $ ./0-nqueens.py 6 [[0, 1], [1, 3], [2, 5], [3, 0], [4, 2], [5, 4]] [[0, 2], [1, 5], [2, 1], [3, 4], [4, 0], [5, 3]] [[0, 3], [1, 0], [2, 4], [3, 1], [4, 5], [5, 2]] [[0, 4], [1, 2], [2, 0], [3, 5], [4, 3], [5, 1]]
Step 3, error messages and exit codes
$ ./0-nqueens.py ; echo "exit=$?" Usage: nqueens N exit=1 $ ./0-nqueens.py hello ; echo "exit=$?" N must be a number exit=1 $ ./0-nqueens.py 3 ; echo "exit=$?" N must be at least 4 exit=1
Step 4, what the solution looks like on the board
[[0, 1], [1, 3], [2, 0], [3, 2]] -> . Q . .
. . . Q
Q . . .
. . Q .Read the list like this: row 0's queen is in column 1, row 1's in column 3, and so on. Check with your own eyes that no two share a column or a diagonal.
Step 5, why the diagonal trick works
col0 col1 col2 col3 <- each cell shows (row-col)/(row+col)
row0 +0/0 -1/1 -2/2 -3/3
row1 +1/1 +0/2 -1/3 -2/4
row2 +2/2 +1/3 +0/4 -1/5
row3 +3/3 +2/4 +1/5 +0/6
(0,1) and (1,3): row-col = -1 and -2 -> different
row+col = 1 and 4 -> different -> safe
(0,1) and (1,2): row-col = -1 and -1 -> SAME -> same diagonal, attackingStep 6, walk N=4 step by step
The real search the code performs
Row 0. We try column 0 and place the queen: cols={0}, diag={0} and anti={0}.
Row 1. Column 0 is taken. Column 1: 1-1=0, which is in diag → attacking. Column 2 is safe, so we place it and descend.
Row 2. Column 0 taken, 1 on a diagonal, 2 taken, 3 on a diagonal. No safe column → backtrack.
Cleanup. We lift row 1's queen, erase her entries, and try column 3. Descending to row 2 we find the same situation: no safe column → backtrack again.
Row 1's columns are exhausted, so we back up to row 0 and lift its queen. Note: we cut off the whole branch under column 0 after only two attempts.
Row 0 again, column 1. Descending: row 1 → column 3 is safe. Row 2 → column 0 is safe. Row 3 → column 2 is safe.
We reached row == n, so we save a copy of the board: [[0,1],[1,3],[2,0],[3,2]] ✓
We do not stop. Every solution is wanted, so we keep backtracking from where we were. The search finds a second solution [[0,2],[1,0],[2,3],[3,1]] and then the possibilities run out.
Step 7, how much did pruning actually save?
N solutions placements tried N^N N! 4 2 60 256 24 5 10 220 3,125 120 6 4 894 46,656 720 7 40 3,584 823,543 5,040 8 92 15,720 16,777,216 40,320 9 352 72,378 387,420,489 362,880 10 724 348,150 10,000,000,000 3,628,800
The important comparison is the third column against the fourth: at N=8 the solution tries 15,720 placements instead of 16.7 million arrangements, under one in a thousand. And the gap widens as N grows.
N=8 : 92 solutions, 15,720 placements tried, 0.002s N=10: 724 solutions, 348,150 placements tried, 0.045s N=12: 14,200 solutions, 10,103,868 placements tried, 1.234s
Myth vs. reality
| The myth | The reality |
|---|---|
| “Backtracking is a kind of brute force.” | Both explore possibilities, but backtracking cuts a whole branch the moment it becomes impossible. We measured the difference: 15,720 placements against 16.7 million at N=8. |
| “I must check every placed queen at every step.” | No. Three sets make the check instant: the column, row-col, and row+col. |
“I can just return at the end of the function.” | Every solution is required, so the function continues searching after each one it finds instead of stopping at the first. |
| “The order of the input checks does not matter.” | It does. Checking sys.argv[1] before the argument count crashes with IndexError when the program is called with no arguments, instead of printing the required message. |
| “I add the queen to the sets and move on; cleanup is a detail.” | Cleanup is the backtracking. Without it, failed attempts stay recorded and valid solutions disappear. |
“N=3 has a solution like the rest.” | It has none at all, and neither does N=2. That is why the project starts at 4. |
Where it is used in practice
Sudoku and grid puzzles
Literally the same structure: pick a cell, try a value, check the constraints, descend, and retreat when it is impossible.
Scheduling and resource allocation
Timetables and shift rotas: each item has a limited set of options and constraints that forbid clashes, which is another phrasing of the same problem.
Map and frequency colouring
Colour each region so it shares no colour with a neighbour, or assign frequencies to adjacent towers.
Searching large spaces
Every "find a combination satisfying constraints" problem is solved with this pattern, which is the basis of what is called CSP, constraint satisfaction problems.
Try it yourself
In the backtracking function you forgot the line cols.discard(col) after the recursive call. What happens?
The cols set is a single object shared by every level of the recursion, and nothing cleans it for you. If a column stays recorded after its branch failed, later levels believe it is occupied and skip it, losing valid solutions. Running N=4 with this bug prints one solution or none instead of two. The rule: every add before the call has a matching discard after it.
Quick review flashcards
row - col is constant along the whole diagonal, so we keep the used values in a set.row + col is constant, and that is the third set.[pair[:] for pair in board] when saving?board changes one line later; without the copy you save a reference to it, not a picture of it.N=8?Check your understanding
1. Why check the argument count before converting the argument to a number?
Because sys.argv[1] raises IndexError when the program is called with no arguments, crashing with a traceback instead of printing Usage: nqueens N and exiting with 1. The right order is: count, then type, then value.
2. Explain precisely why row - col identifies the ↘ diagonal.
Moving along that diagonal means increasing the row by one and the column by one together, so their difference never changes. Every ↘ diagonal has its own unique difference, so the check becomes "is this difference used?" instead of walking the queens. The same logic applies to row + col for the other diagonal: a step down is matched by a step back in the column, so the sum stays constant.
3. (Spot the bug) Your solution prints the same solution repeated as many times as there are solutions. Where is the mistake?
You saved board directly instead of a copy of it. That list is one object mutated at every step, so everything you saved is a reference to the same object, and at the end they all print in its final state. The fix is [pair[:] for pair in board], and note that board[:] alone is not enough, being a shallow copy that shares the inner lists.
4. Does the number of solutions change if you iterate columns instead of rows?
No. The board is symmetric in that sense, and the number of solutions is a property of the problem, not of how you search. What changes is the order in which solutions appear, and the brief says explicitly that no particular order is required.
5. (Decision) You want just one solution for N=30 as fast as possible. What do you change?
Stop at the first solution instead of collecting all of them, which alone cuts the time enormously. If you need more speed, order the columns you try so the least constraining come first, or use one of the known direct construction formulas for N queens. "All solutions" and "one solution" are two different problems in cost, so read what is asked before optimising.
Resources for this part
Sorted by kind: start with the official docs when you want the precise reference, or with an article or video when you want the explanation first.
Resources for this lesson
Grouped by type. Start with the official docs for precision, or an article or video for the explanation.
Tools2
Done with this lesson?
Sign in to save your progress.