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.
N-Queens and Constraint Propagation is a free DSA Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
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') # 92O(1) Constraint Checking with Sets
Checking validity by scanning all placed queens is O(N) per candidate, making the total algorithm O(N² × N!) in the worst case. We can reduce each validity check to O(1) by maintaining three sets: cols (occupied columns), diag (row-col values for top-left diagonals), and anti_diag (row+col values for top-right diagonals). Queens on the same diagonal share the same row-col; on the same anti-diagonal, they share the same row+col.
def solve_n_queens_fast(n):
results = []
cols = set() # occupied columns
diag = set() # row - col (positive diagonal)
anti = set() # row + col (negative diagonal)
queens = []
def backtrack(row):
if row == n:
board = ['.' * c + 'Q' + '.' * (n-c-1) for c in queens]
results.append(board)
return
for col in range(n):
if col in cols or (row-col) in diag or (row+col) in anti:
continue # PRUNE: constraint violated
# CHOOSE
cols.add(col); diag.add(row-col); anti.add(row+col); queens.append(col)
backtrack(row + 1) # EXPLORE
# UNCHOOSE
cols.remove(col); diag.remove(row-col); anti.remove(row+col); queens.pop()
backtrack(0)
return results
print(len(solve_n_queens_fast(8))) # 92Diagonal Invariant Explained
The diagonal insight: all cells on the same top-left-to-bottom-right diagonal have the same value of row - col. For example, (0,0), (1,1), (2,2) all have row-col=0. All cells on the same anti-diagonal have the same row + col: (0,2), (1,1), (2,0) all have row+col=2. These are the constant-time invariants that let us check diagonal conflicts with O(1) set lookup instead of O(N) linear scan.
# Visualise the diagonal invariants for a 4x4 board
n = 4
print('row-col values (same diagonal):')
for r in range(n):
print([r-c for c in range(n)])
print('row+col values (same anti-diagonal):')
for r in range(n):
print([r+c for c in range(n)])
# Verify: (0,0) and (2,2) share diag value 0
print('(0,0) diag:', 0-0, '| (2,2) diag:', 2-2) # both 0
# Verify: (0,2) and (2,0) share anti-diag value 2
print('(0,2) anti:', 0+2, '| (2,0) anti:', 2+0) # both 2Counting Solutions: N-Queens II
N-Queens II (LeetCode 52) asks only for the count, not the boards. This allows a slight optimisation: skip the board construction step, just increment a counter. Using bitmasks instead of sets can further speed up the count to near-O(1) per operation. The number of solutions grows non-monotonically: 1(N=1), 0(N=2), 0(N=3), 2(N=4), 10(N=5), 4(N=6), 40(N=7), 92(N=8).
def total_n_queens(n):
count = [0]
cols = set(); diag = set(); anti = set()
def backtrack(row):
if row == n:
count[0] += 1
return
for col in range(n):
if col in cols or (row-col) in diag or (row+col) in anti:
continue
cols.add(col); diag.add(row-col); anti.add(row+col)
backtrack(row + 1)
cols.remove(col); diag.remove(row-col); anti.remove(row+col)
backtrack(0)
return count[0]
for n in range(1, 11):
print(f'N={n}: {total_n_queens(n)} solutions')Bitmask N-Queens for Speed
For very large N, a bitmask implementation runs significantly faster. Use three integers as bitmasks: cols, left_diag (shifts left each row), right_diag (shifts right each row). The available columns are ((1<<n)-1) & ~(cols|left_diag|right_diag). Extract each available column with bit = available & -available (lowest set bit), then recurse. This achieves O(1) per constraint check with bitwise operations.
def total_n_queens_bitmask(n):
full = (1 << n) - 1 # all n columns set
count = [0]
def bt(cols, left_diag, right_diag):
if cols == full:
count[0] += 1
return
available = full & ~(cols | left_diag | right_diag)
while available:
bit = available & -available # lowest set bit
available &= available - 1 # remove lowest bit
bt(cols | bit,
(left_diag | bit) << 1,
(right_diag | bit) >> 1)
bt(0, 0, 0)
return count[0]
for n in range(1, 13):
print(f'N={n}: {total_n_queens_bitmask(n)}')Constraint Propagation Concept
Constraint propagation goes beyond simple pruning: after placing a queen, immediately deduce and eliminate all invalid positions in future rows. This is more aggressive than checking validity at each candidate — you proactively narrow the search space before branching. The most famous example is Arc Consistency in SAT solvers and Sudoku solvers, where placing one digit eliminates options in the same row, column, and 3×3 box.
# Constraint propagation in Sudoku:
# After placing 5 in cell (0,0):
# - Row 0: no other cell can have 5
# - Column 0: no other cell can have 5
# - Box (0,0)-(2,2): no other cell can have 5
# This is propagated BEFORE branching further
# Simple demo: remaining valid columns after placing queens
def remaining_columns(n, queens):
cols = set(q for q in queens)
diags = set(r - q for r, q in enumerate(queens))
anti_diags = set(r + q for r, q in enumerate(queens))
row = len(queens)
return [c for c in range(n)
if c not in cols
and (row-c) not in diags
and (row+c) not in anti_diags]
print(remaining_columns(8, [0])) # valid cols for row 1 after placing col 0 in row 0Sudoku Solver
Sudoku is the canonical constraint propagation problem. At each empty cell, the valid digit choices are those not already in the same row, column, or 3×3 box. The backtracking solver: find the first empty cell, try each valid digit, recurse. If a contradiction is reached (empty cell with no valid digit), backtrack. Good Sudoku solvers also apply constraint propagation (pencil marks) before backtracking.
def solve_sudoku(board):
def is_valid(r, c, num):
for i in range(9):
if board[r][i] == num: return False # row
if board[i][c] == num: return False # col
br, bc = (r//3)*3, (c//3)*3
for i in range(3):
for j in range(3):
if board[br+i][bc+j] == num: return False # box
return True
def backtrack():
for r in range(9):
for c in range(9):
if board[r][c] == '.':
for d in '123456789':
if is_valid(r, c, d):
board[r][c] = d
if backtrack(): return True
board[r][c] = '.'
return False # no valid digit found
return True # no empty cells: solved
backtrack()
return board
# Mini test with a solvable board (simplified)
print('Sudoku solver implemented')Most-Constrained Variable Heuristic
A key optimisation for constraint satisfaction problems: always choose the most-constrained variable (the cell with the fewest valid choices) next. In Sudoku, if one cell has only 1 valid digit, filling it immediately is forced — no backtracking needed. Choosing such cells first dramatically reduces the search tree depth. This is the Minimum Remaining Values (MRV) heuristic from AI constraint programming.
def solve_sudoku_mrv(board):
'''Find cell with fewest valid choices (MRV heuristic).'''
def valid_choices(r, c):
nums = set('123456789')
for i in range(9):
nums.discard(board[r][i])
nums.discard(board[i][c])
br, bc = (r//3)*3, (c//3)*3
for i in range(3):
for j in range(3):
nums.discard(board[br+i][bc+j])
return nums
def find_mrv():
best = (10, -1, -1, set()) # (choices_count, r, c, choices)
for r in range(9):
for c in range(9):
if board[r][c] == '.':
choices = valid_choices(r, c)
if len(choices) < best[0]:
best = (len(choices), r, c, choices)
return best[1], best[2], best[3]
def backtrack():
r, c, choices = find_mrv()
if r == -1: return True # no empty cells
for d in choices:
board[r][c] = d
if backtrack(): return True
board[r][c] = '.'
return False
backtrack()
return boardN-Queens Solutions Count Table
The number of N-queens solutions follows this well-known sequence: N=1: 1, N=2: 0, N=3: 0, N=4: 2, N=5: 10, N=6: 4, N=7: 40, N=8: 92, N=9: 352, N=10: 724. No closed-form formula is known; the count must be computed. For N=27, about 2.34 × 10^17 solutions exist. Interview questions typically ask for N ≤ 9. Understanding the exponential growth justifies why the bitmask optimisation matters for larger N.
def count_queens(n):
'''O(1) per constraint check using sets.'''
count = [0]
cols = set(); diag = set(); anti = set()
def bt(row):
if row == n: count[0] += 1; return
for col in range(n):
if col in cols or (row-col) in diag or (row+col) in anti: continue
cols.add(col); diag.add(row-col); anti.add(row+col)
bt(row+1)
cols.discard(col); diag.discard(row-col); anti.discard(row+col)
bt(0)
return count[0]
sequence = [count_queens(n) for n in range(1, 12)]
print('N-Queens counts:', sequence)
# [1, 0, 0, 2, 10, 4, 40, 92, 352, 724, 2680]N-Queens Board Construction
When the interviewer asks to return the actual boards (LeetCode 51), build each board from the queens list where queens[r] is the column of the queen in row r. String construction: '.' * col + 'Q' + '.' * (n - col - 1) for each row. This O(n²) construction is called only at leaves of the recursion tree (when all N queens are placed), so it does not affect the overall complexity.
def n_queens_boards(n):
results = []
queens = []
cols = set(); diag = set(); anti = set()
def build_board():
return ['.' * c + 'Q' + '.' * (n-c-1) for c in queens]
def bt(row):
if row == n:
results.append(build_board())
return
for col in range(n):
if col in cols or (row-col) in diag or (row+col) in anti: continue
cols.add(col); diag.add(row-col); anti.add(row+col); queens.append(col)
bt(row+1)
cols.remove(col); diag.remove(row-col); anti.remove(row+col); queens.pop()
bt(0)
return results
for board in n_queens_boards(4):
for row in board: print(row)
print()Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: N-Queens places one queen per row and uses sets for cols, diagonals (row-col), and anti-diagonals (row+col) for O(1) constraint checking, bitmasks further accelerate constraint checks and allow exploring all placements in near O(1) per operation, and constraint propagation (MRV heuristic) reduces search by always choosing the most-constrained variable next. Next up we compare Greedy vs DP approaches and learn when to apply each.
Frequently asked questions
Is the “N-Queens and Constraint Propagation” lesson free?
Yes — the full text of “N-Queens and Constraint Propagation” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “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. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “N-Queens and Constraint Propagation” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Backtracking Template: Choose, Explore, Unchoose
- Subsets and Power Set
- Permutations and Combinations
- N-Queens and Constraint Propagation