N-Queens Constraint Backtracking DSA Solution

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.

Input	Output	Why
`n = 4`	`two valid boards`	For n = 4 there are exactly two valid queen placements.

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

Step	State	Result
Row 0	Try a column and mark diagonals	Move to row 1
Row 1	Blocked columns and diagonals are skipped	Only safe cells are tried
Dead end	No safe column exists	Backtrack and remove marks
row == n	All rows placed	Copy one board

Complexity

Measure	Value	Reason
Time	O(n!)	Backtracking prunes many placements, but the search is still factorial scale.
Space	O(n^2)	The board uses n^2 space and the sets use O(n).

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

Why one queen per row?

Every valid board needs exactly one queen in each row, so row-by-row search reduces choices.

Why row - col and row + col?

Cells on the same diagonals share these values.

What is the core pattern?

Constraint backtracking.

N-Queens: Constraint Backtracking Pattern