How do you solve N-Queens?

Use backtracking to place queens row by row. Maintain sets to track occupied columns and diagonals. For each row, iterate over columns and skip those that conflict with existing queens. Place a queen, update tracking sets, recurse to the next row, and backtrack by removing the queen and updating sets. When all rows are processed, record the valid board configuration. This approach guarantees all solutions are found efficiently.

What pattern does N-Queens use?

The Pattern: Backtracking (State Restoration) The Heuristic: For constraint satisfaction problems like N-Queens, incrementally build partial solutions while pruning invalid states early, and always restore state after exploring each branch to enable exhaustive and correct search.

N-Queens — Backtracking

Q: What is the time complexity of N-Queens?

O(n!). Each queen must be placed in a different row and column, so the number of permutations is n!. The pruning of invalid diagonals reduces the search space but the worst-case complexity remains factorial.

Problem

Given an integer n, return all distinct solutions to the n-queens puzzle such that no two queens threaten each other on an n x n chessboard.

1 ≤ n ≤ 9

Example

Input: n = 4

Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

The algorithm explores placing queens row by row. For n=4, it tries placing a queen in the first row at each column, checking if the position is safe by verifying columns and diagonals. When it reaches the last row and successfully places a queen without conflicts, it records the board configuration. The critical moment is when the algorithm backtracks after exploring all columns in a row, removing the queen and trying alternative placements, ensuring all valid solutions are found.

Approach

Straightforward Solution

A brute-force approach would try all possible placements of n queens on an n x n board, which is O(n^n) and infeasible for larger n due to the combinatorial explosion.

Core Observation

The fundamental truth is that no two queens can share the same column, positive diagonal, or negative diagonal. This reduces the problem to a constraint satisfaction problem where each row must have exactly one queen placed in a safe column.

Path to Optimal

Preview

The key insight is to build the solution incrementally, placing one queen per row and pruning invalid placements early by tracking columns and diagonals already occupied…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use backtracking to place queens row by row. Maintain sets to track occupied columns and diagonals…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n!)

Each queen must be placed in a different row and column, so the number of permutations is n!. The pruning of invalid diagonals reduces the search space but the worst-case complexity remains factorial.

Space

O(n^2)

The board requires O(n^2) space to store the current state. The recursion stack and sets for columns and diagonals use O(n) space each, which is dominated by the board storage.

Solution

Python

1class Solution:
  def solveNQueens(self, n: int) -> list[list[str]]:
      col = set()
      pos_diag = set() 
      neg_diag = set() 
6
      res = []
      board = [["."] * n for i in range(n)]
9
      def backtrack(r):
          if r == n:
              copy = ["".join(row) for row in board]
              res.append(copy)
              return
          
          for c in range(n):
              if c in col or (r + c) in pos_diag or (r - c) in neg_diag:
                  continue
              
              col.add(c)
              pos_diag.add(r + c)
              neg_diag.add(r - c)
              board[r][c] = "Q"
24
              backtrack(r + 1)
26
              col.remove(c)
              pos_diag.remove(r + c)
              neg_diag.remove(r - c)
              board[r][c] = "."
      
      backtrack(0)
      return res

Step-by-Step Solution

1

Initialize Board and Tracking Sets for Backtracking

3col = set()
4pos_diag = set() 
5neg_diag = set() 
7res = []
8board = [["."] * n for i in range(n)]

Objective

To prepare the data structures that track queen placements and constraints before starting the recursive search.

Key Insight

Using sets for columns and diagonals allows O(1) checks for conflicts, which is critical for pruning invalid placements early. Representing the board as a 2D list of characters enables easy updates and final solution formatting. This setup lays the foundation for efficient backtracking.

Interview Quick-Check

Core Logic

Sets for columns and diagonals enable constant-time conflict detection, which is essential for pruning the search space.

Common Pitfalls & Bugs

Forgetting to initialize the board or tracking sets correctly leads to incorrect conflict checks and invalid solutions.

2

Place Queens Row-by-Row Using Backtracking with Conflict Checks

To recursively place queens on the board, ensuring no conflicts in columns or diagonals, and backtrack when necessary.

3

Start Backtracking from the First Row and Return All Solutions

To initiate the recursive search from the first row and return the collected valid board configurations.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 6 Critical lines interviewers watch for.

Line 27 Critical

col.remove(c)

Remove the current column from the occupied set during backtracking.

This state restoration is critical; it ensures that after exploring one branch, the algorithm correctly resets the column occupancy to allow other branches to be explored without false conflicts.

Line 11 Critical

if r == n:

Check if all rows have been processed (base case).

When r equals n, a valid configuration has been found, signaling the recursion to record the solution and backtrack.

Line 17 Critical

if c in col or (r + c) in pos_diag or (r - c) in neg_diag:

Skip columns that are already occupied or conflict on diagonals.

This pruning step prevents invalid queen placements early, drastically reducing the search space and improving efficiency.

Full line-by-line criticality + rationale for all 23 lines available on Pro.

Test Your Understanding

Why is it necessary to track columns and both diagonals when placing queens?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct N-Queens from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the N-Queens drill

or drill a free problem

1	`class Solution:`
2	`def solveNQueens(self, n: int) -> list[list[str]]:`
3	`col = set()`
4	`pos_diag = set()`
5	`neg_diag = set()`
6
7	`res = []`
8	`board = [["."] * n for i in range(n)]`
9
10	`def backtrack(r):`
11	`if r == n:`
12	`copy = ["".join(row) for row in board]`
13	`res.append(copy)`
14	`return`
15
16	`for c in range(n):`
17	`if c in col or (r + c) in pos_diag or (r - c) in neg_diag:`
18	`continue`
19
20	`col.add(c)`
21	`pos_diag.add(r + c)`
22	`neg_diag.add(r - c)`
23	`board[r][c] = "Q"`
24
25	`backtrack(r + 1)`
26
27	`col.remove(c)`
28	`pos_diag.remove(r + c)`
29	`neg_diag.remove(r - c)`
30	`board[r][c] = "."`
31
32	`backtrack(0)`
33	`return res`

3	`col = set()`
4	`pos_diag = set()`
5	`neg_diag = set()`
7	`res = []`
8	`board = [["."] * n for i in range(n)]`