N-Queens and Constraint Propagation
Place N queens on an N×N board using column and diagonal sets for O(1) constraint checking, and discuss how to count vs enumerate solutions.
The N-Queens Problem
The N-Queens problem (LeetCode 51/52) asks you to place N queens on an N×N chessboard such that no two queens attack each other. Queens attack along rows, columns, and both diagonals. For N=4, there are exactly 2 solutions. For N=8 (the classic version), there are 92 solutions. This is the canonical backtracking problem with constraint checking that prunes the search space dramatically.
# N-Queens constraints:
# 1. Exactly one queen per row
# 2. No two queens in the same column
# 3. No two queens on the same diagonal (top-left to bottom-right)
# 4. No two queens on the same anti-diagonal (top-right to bottom-left)
# For N=4, the 2 solutions:
sol1 = ['.Q..', '...Q', 'Q...', '..Q.']
sol2 = ['..Q.', 'Q...', '...Q', '.Q..']
print('N=4 solutions:')
for row in sol1: print(row)
print()
for row in sol2: print(row)Placing One Queen Per Row
Since no two queens can share a row, we place exactly one queen per row. The backtracking recurses row by row, choosing a column for each row. This reduces the search space from N² choices per queen to only N columns per row, giving N^N starting branches — but constraints reduce this dramatically. The recursion depth is N (one level per row), and the branching factor is at most N.
def solve_n_queens(n):
results = []
queens = [] # queens[row] = column of queen in that row
def backtrack(row):
if row == n:
# Build the board representation
board = []
for r in range(n):
board.append('.' * queens[r] + 'Q' + '.' * (n - queens[r] - 1))
results.append(board)
return
for col in range(n):
if is_valid(row, col):
queens.append(col) # CHOOSE
backtrack(row + 1) # EXPLORE
queens.pop() # UNCHOOSE
def is_valid(row, col):
for r, c in enumerate(queens):
if c == col: return False # same column
if abs(row - r) == abs(col - c): return False # diagonal
return True
backtrack(0)
return results
print(len(solve_n_queens(4)), 'solutions for N=4') # 2
print(len(solve_n_queens(8)), 'solutions for N=8') # 92All lessons in this course
- Backtracking Template: Choose, Explore, Unchoose
- Subsets and Power Set
- Permutations and Combinations
- N-Queens and Constraint Propagation