AI Hints
Home›DSA in Python Tutorial›Puzzles, Bits and Strategy
DSA in Python · Lesson 100 of 132

Practice: N Queens

No two queens attack.

⏱ 2 min read▶ Video at 1:59:48🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Practice: N Queens
From the video: Practice: N Queens
  • 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.

queens.pypython
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)))
Output
. 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.

keyvalue
One per rowrows never clash
Setstaken columns and diagonals
r - c, r + cdiagonal ids
8 queens92 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
Next up: Bit Manipulation — tricks with ones and zeros