Practice: N Queens
No two queens attack.
Place eight queens on a chessboard, so that no two queens can attack each other. No two in the same row, the same column, or the same diagonal. It's the classic backtracking puzzle. Let's solve a smaller board first, six by six, and draw the answer.

- Eight queens, no attacks
- Rows, columns, diagonals
- Start with six by six
One row at a time
We place one queen per row, so rows can never clash. Three sets remember which columns and diagonals are already taken. On a diagonal, row minus column stays the same, and on the other diagonal, row plus column stays the same. If a square is safe, we place the queen, recurse to the next row, and then remove it. Run it. Here's a solution, and the count for eight queens. Ninety two.
def queens(n):
cols, d1, d2, place, sols = set(), set(), set(), [], []
def row(r):
if r == n:
sols.append(list(place)); return
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); place.append(c)
row(r + 1)
cols.remove(c); d1.remove(r - c); d2.remove(r + c); place.pop()
row(0)
return sols
first = queens(6)[0]
for c in first:
print(". " * c + "Q " + ". " * (6 - c - 1))
print("solutions for 8 queens:", len(queens(8))). Q . . . . . . . Q . . . . . . . Q Q . . . . . . . Q . . . . . . . Q . solutions for 8 queens: 92
Why backtracking works here
There are over four billion ways to put eight queens on a board. But by checking safety as we go, we abandon a placement the moment it fails, and never explore the millions of boards that would follow from it. That's pruning at work again.
| key | value |
|---|---|
| One per row | rows never clash |
| Sets | taken columns and diagonals |
| r - c, r + c | diagonal ids |
| 8 queens | 92 solutions |
Summary
Place queens row by row, check columns and diagonals with sets, and backtrack on conflicts. Next, a few tricks with the bits inside numbers.
Key takeaways- Row by row
- Sets for safety
- Backtrack on conflict