The N-Queens problem is the classic backtracking problem. It places N chess queens on an N×N board so no two queens attack each other. Mastering it teaches you the backtracking template that applies to Sudoku, permutations, combinations, and constraint satisfaction problems.
Problem
Place N queens on an N×N chessboard such that no two queens share the same row, column, or diagonal. Return all valid placements.
Backtracking Solution
def solve_n_queens(n: int) -> list[list[str]]:
"""
Backtracking: place one queen per row, track attacked columns/diagonals.
Time: O(N!), Space: O(N) for the recursion stack
"""
results = []
# Track which columns and diagonals are under attack
cols = set()
diag1 = set() # top-left to bottom-right: (row - col) is constant
diag2 = set() # top-right to bottom-left: (row + col) is constant
board = [['.' for _ in range(n)] for _ in range(n)]
def backtrack(row):
if row == n:
# All queens placed — record this solution
results.append([''.join(r) for r in board])
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue # This cell is under attack
# Place queen
board[row][col] = 'Q'
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
backtrack(row + 1) # Recurse to next row
# Remove queen (backtrack)
board[row][col] = '.'
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
backtrack(0)
return results
solutions = solve_n_queens(4)
for sol in solutions:
for row in sol:
print(row)
print()
# Two solutions for N=4Count-Only Version (LeetCode 52)
def total_n_queens(n: int) -> int:
"""Just count solutions without recording board states."""
count = [0]
cols = set()
diag1 = set()
diag2 = set()
def backtrack(row):
if row == n:
count[0] += 1
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
cols.add(col); diag1.add(row - col); diag2.add(row + col)
backtrack(row + 1)
cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)
backtrack(0)
return count[0]
print(total_n_queens(8)) # 92Bit Manipulation Optimization
For large N, represent attacked columns and diagonals as bitmasks for O(1) set operations:
def solve_n_queens_bits(n: int) -> int:
"""
Bit manipulation: cols, diag1, diag2 as integers.
Attacked positions = set bits.
Time: O(N!), but constant factors are much smaller than set-based approach.
"""
count = [0]
limit = (1 << n) - 1 # All N bits set = all columns occupied
def backtrack(cols, diag1, diag2):
if cols == limit:
count[0] += 1
return
# Available positions: not attacked by cols, diag1, or diag2
available = limit & ~(cols | diag1 | diag2)
while available:
pos = available & (-available) # Isolate rightmost set bit
available &= available - 1 # Remove rightmost set bit
backtrack(
cols | pos,
(diag1 | pos) <> 1
)
backtrack(0, 0, 0)
return count[0]The Backtracking Template
N-Queens demonstrates the universal backtracking pattern:
def backtrack(state):
if is_solution(state):
record(state)
return
for choice in get_choices(state):
if is_valid(state, choice):
apply(state, choice) # Make choice
backtrack(state) # Recurse
undo(state, choice) # Undo choice (backtrack)This same template solves: Sudoku, generate permutations/combinations/subsets, word search on a grid, and all constraint satisfaction problems.
Related Recursion Topics
- Generate All Subsets — both use the same backtracking template; subsets has no constraints, N-Queens has column/diagonal constraints