The problem
Place n chess queens on an n × n board so that no two attack each other (no shared row, column or diagonal). Return all solutions.
Input: n = 4 Output: 2 solutions (queens in columns [1,3,0,2] and [2,0,3,1], one per row)
Picture it
Picture a chessboard. We place one queen per row, from top to bottom. In each row we try every column that is not attacked by queens already placed (same column, or either diagonal). If a row has no safe column, we go back up and move the previous queen.
How to recognise it
- You must place items on a board so that no two conflict, and return all valid placements.
- The rules are of the form "nothing shares a row, column or diagonal", so placing one item rules out many squares for later ones.
- The board is small (n up to 9), which allows an exponential search, but 9^9 ≈ 387 million arrangements is already too many to test one by one.
- Because each queen needs its own row, the natural decision tree has one level per row and up to n branches (the columns).
- Place, recurse, remove: this is the textbook form of backtracking, where conflicts let you abandon a branch long before the board is full.
Start with brute force
Put one queen in every row (there must be exactly one per row), try every combination of columns, and test the finished board for conflicts.
from itertools import product
def solve_n_queens_brute(n):
res = []
for cols in product(range(n), repeat=n): # cols[r] = column in row r
if (len(set(cols)) == n
and len({r - c for r, c in enumerate(cols)}) == n
and len({r + c for r, c in enumerate(cols)}) == n):
res.append(list(cols))
return res
There are n^n candidate boards: 4^4 = 256, 8^8 = 16,777,216, 9^9 = 387,420,489. Each is checked only after it is complete, so a board with two queens in the same column is built in full before being rejected. Time is O(n · n^n) and space is O(n) beyond the output.
From brute force to the idea
- Place row by row.
place(r)puts a queen in rowr, trying each columnc. A queen in each row guarantees no two share a row. - Know what is attacked in O(1). Keep three sets:
cols(columns taken),d1(the valuesr - c, which are equal along a diagonal running down and to the right) andd2(the valuesr + c, equal along a diagonal running down and to the left). - Skip attacked squares. If
c in cols or r - c in d1 or r + c in d2, the square is attacked, socontinue. - Choose, recurse, un-choose. Add
cto all three sets and append it toboard, callplace(r + 1), then removecfrom all three and pop it. - Save at the bottom. When
r == nevery row has a queen, soboard(the column of each row) is a solution. The code turns it into LeetCode's strings, one per row:"Q"in the queen's column and"."everywhere else.
This is the key idea: the three sets reject an attacked square in O(1), so bad branches die early. For n = 8 the shown code makes about 2,000 calls, against 16.8 million boards for the brute force.
The key idea
Backtrack row by row; three sets (columns, r−c diagonals, r+c diagonals) make each safety check O(1).
Python solution
def solve_n_queens(n):
cols, d1, d2, res, board = set(), set(), set(), [], []
def place(r):
if r == n:
res.append(["." * c + "Q" + "." * (n - c - 1) for c in board]); return
for c in range(n):
if c in cols or r - c in d1 or r + c in d2:
continue # attacked: skip this square
cols.add(c); d1.add(r - c); d2.add(r + c); board.append(c)
place(r + 1)
cols.remove(c); d1.remove(r - c); d2.remove(r + c); board.pop()
place(0)
return resIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (all n^n boards) | O(n · n^n) | O(n) beyond the output |
| Row by row with three sets (shown code) | Bounded by O(n!) because each row uses a column no earlier row used; in practice far less because diagonals prune too | O(n): the three sets, board and the recursion are each at most n deep |
Edge cases
- n = 1: returns
[[0]], a single queen at column 0. - n = 2 and n = 3: return
[]; no placement works. - n = 4: returns
[[1, 3, 0, 2], [2, 0, 3, 1]], the two solutions in the example, each listed as the column of the queen in rows 0 to 3. - n = 8: 92 solutions. n = 9: 352 solutions.
- Output format: each solution is a list of strings such as
".Q..", as LeetCode expects. The comprehension builds new strings, so later changes toboardcannot affect saved answers. - Sets are shared: the three sets and
boardare updated in place and restored after every call, so they are empty again whensolve_n_queensreturns.
Common mistakes
- Checking only the columns. That accepts every arrangement with one queen per row and column, which for n = 4 is all 24 permutations.
- Using one diagonal set for both directions, so
r - candr + cvalues collide. - Forgetting to remove an entry from one of the three sets after the recursive call. The set then keeps "attacked" marks from dead branches. Forgetting only the
r + cset returns 0 solutions for n = 4. - Saving
boarditself (for exampleres.append(board)) instead of a converted copy, which makes every answer the same list that is emptied by the time the search ends.
Return how many solutions exist for n (for example 92 for n = 8), without keeping the boards. Describe your approach, then write it if you like.
Compare with our answer
Use the same row by row search with the same three sets, but return numbers instead of collecting boards: a full board counts 1, and each call returns the sum of what its children return. There is no need to keep board or a result list.
def count_queens(n):
cols, d1, d2 = set(), set(), set()
def place(r):
if r == n:
return 1
total = 0
for c in range(n):
if c in cols or r - c in d1 or r + c in d2:
continue
cols.add(c); d1.add(r - c); d2.add(r + c)
total += place(r + 1)
cols.remove(c); d1.remove(r - c); d2.remove(r + c)
return total
return place(0)
The counts for n = 1 to 10 are 1, 0, 0, 2, 10, 4, 40, 92, 352, 724. The time is the same as for the full version, but space is O(n) with no output at all.
A strong answer mentions: returning a count from each call, adding a full board as 1, and keeping the same three sets and the same undo steps.
1. A seating planner must list every way to place 6 guests in 6 rows so that no two guests share a column or a diagonal. Which approach fits best?
Placing guest by guest and rejecting attacked squares cuts dead branches early; 6^6 = 46,656 complete plans are much more than the search visits. Greedy can get stuck and returns only one plan, and the other option scores plans instead of listing them.
2. Why do the sets use r - c for one diagonal and r + c for the other?
Moving one step down and one step right keeps r - c the same; moving down and left keeps r + c the same. So each value identifies one whole diagonal in O(1). The other statements are not what makes the trick work.
3. A learner deletes d2.remove(r + c) but keeps the other removals. Which input exposes the bug?
The stale r + c values from abandoned branches make safe squares look attacked. For n = 4 the code returns no solutions instead of two. For n = 1, 2 and 3 the answers (1, 0 and 0) are unchanged.
Score 60% or more and the lesson is marked complete.