N-Queens: Constraint Backtracking Pattern

Learning Outcome

After this lesson, you should be able to encode board constraints with column and diagonal sets.

Problem Statement

Given n, return all distinct ways to place n queens on an n x n board so no two queens attack each other.

Brute Force Approach

Try placements and scan the whole board each time to check safety. This repeats expensive checks.

Optimized Approach

Place one queen per row and track used columns, row-col diagonals, and row+col diagonals in sets.

Exact Pseudocode

dfs(row):
  if row == n:
    answer.add(copy(board))
    return
  for col from 0 to n - 1:
    if col or diagonals are blocked:
      continue
    place queen
    mark col and diagonals
    dfs(row + 1)
    remove queen and marks
dfs(0)
  

Reference Code

class Solution:
    def solveNQueens(self, n):
        answer = []
        board = [["."] * n for _ in range(n)]
        cols, diag1, diag2 = set(), set(), set()

        def dfs(row):
            if row == n:
                answer.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

                cols.add(col)
                diag1.add(row - col)
                diag2.add(row + col)
                board[row][col] = "Q"
                dfs(row + 1)
                board[row][col] = "."
                cols.remove(col)
                diag1.remove(row - col)
                diag2.remove(row + col)

        dfs(0)
        return answer
  

Sample Dry Run

Complexity

Edge Cases

• n = 1 has one solution.
• n = 2 and n = 3 have no solutions.
• Diagonal keys are row - col and row + col.

Interview Checklist

• Place exactly one queen per row.
• Use sets for O(1) conflict checks.
• Remove all marks during backtracking.

FAQs