Skip to content

Volume ITechnology

4.18.9 — N-Queens ​

LeetCode 51 · Hard

The problem ​

Place n queens on an n × n board so that no two attack each other. A queen attacks along its row, its column, and both diagonals. Return every distinct arrangement.

n = 4  →  2 solutions

. Q . .        . . Q .
. . . Q        Q . . .
Q . . .        . . . Q
. . Q .        . Q . .

n is at most 9.

The pattern ​

Two reductions make this tractable, and the first one is free.

One queen per row. No two queens can share a row, and there are n queens and n rows, so every row holds exactly one. That means you never search over rows — you place row 0, then row 1, and so on, and the only decision is which column.

The search space drops from "choose 8 squares out of 64" (4 \times 10^9) to "choose a column for each row" (8^8 = 16.7 million). Before any pruning.

Then: prune at the moment of placing. Check the conflict as you choose a column, not after building a whole board. That takes 16.7 million down to about 2,000 positions actually explored.

This is the difference the constraint step makes, and it is why N-Queens is the reference problem for backtracking.

Naming the conflict groups ​

A candidate square (r, c) conflicts if another queen shares its column or either diagonal. Checking that by scanning the board is O(n) per candidate. You can make it O(1) by giving each group a name and keeping a set of the occupied ones.

Column: the name is c. Obvious.

The ↘ diagonal (top-left to bottom-right): moving down-right adds 1 to both r and c, so r − c stays constant along it.

The ↗ diagonal (top-right to bottom-left): moving down-left adds 1 to r and subtracts 1 from c, so r + c stays constant.

r − c on a 4×4 board          r + c on a 4×4 board

  0  -1  -2  -3                 0   1   2   3
  1   0  -1  -2                 1   2   3   4
  2   1   0  -1                 2   3   4   5
  3   2   1   0                 3   4   5   6

Every ↘ diagonal is one value of r − c; every ↗ diagonal is one value of r + c.

This is exactly the box-index idea from 4.4.8 Valid Sudoku — give each group a computable name, keep one set per group, and membership becomes O(1). Same technique, different geometry.

Think of this like assigning zip codes to every diagonal line crossing a city grid. If you place a queen on a corner, you instantly look up the two "zip codes" for the two diagonal streets she controls. When placing the next queen, you just check if her street zip code is already in your "occupied" list. You don't need to manually walk down the street to see if someone is there.

The solution ​

python
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        result = []  # (1)
        cols = set()  # (2)
        diag = set()        # (3) r − c   (the ↘ diagonals)
        anti = set()        # (4) r + c   (the ↗ diagonals)
        placement = []      # (5) placement[r] = the column used in row r

        def backtrack(r: int):  # (6)
            if r == n:                                  # (7) all rows filled
                result.append(['.' * c + 'Q' + '.' * (n - c - 1)
                               for c in placement])
                return

            for c in range(n):  # (8)
                if c in cols or (r - c) in diag or (r + c) in anti:  # (9)
                    continue                            # attacked — prune

                cols.add(c)  # (10)
                diag.add(r - c)
                anti.add(r + c)
                placement.append(c)  # (11)

                backtrack(r + 1)  # (12)

                placement.pop()                         # (13) undo all four
                anti.discard(r + c)
                diag.discard(r - c)
                cols.discard(c)

        backtrack(0)
        return result
ts
function solveNQueens(n: number): string[][] {
  const result: string[][] = [];  // (1)
  const cols = new Set<number>();  // (2)
  const diag = new Set<number>();  // (3)
  const anti = new Set<number>();  // (4)
  const placement: number[] = [];  // (5)

  function backtrack(r: number): void {  // (6)
    if (r === n) {  // (7)
      result.push(placement.map(c => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1)));
      return;
    }
    for (let c = 0; c < n; c++) {  // (8)
      if (cols.has(c) || diag.has(r - c) || anti.has(r + c)) continue;  // (9)

      cols.add(c); diag.add(r - c); anti.add(r + c);  // (10)
      placement.push(c);  // (11)

      backtrack(r + 1);  // (12)

      placement.pop();  // (13)
      anti.delete(r + c); diag.delete(r - c); cols.delete(c);
    }
  }

  backtrack(0);
  return result;
}

Line by line ​

(1) result collects every complete board.

(2) The columns that already hold a queen.

(3) The downward diagonals (↘) that already hold a queen. Every cell on one of these diagonals has the same value of r - c, row minus column. So that number names the diagonal.

(4) The upward diagonals (↗) that already hold a queen. Every cell on one of these has the same r + c.

(5) placement[r] is the column of the queen in row r. We place exactly one queen per row, so this is enough to describe the whole board.

(6) backtrack(r) places a queen in row r. Rows above it already have their queens.

(7) All n rows have a queen, so this is a solution. Only now do we build the board as strings: row r is c dots, a Q, and the rest dots.

(8) Try each column in this row.

(9) Skip a square that is attacked by an earlier queen: same column, same ↘ diagonal, or same ↗ diagonal. Each check is a set lookup, so it is constant time.

(10) Place the queen: record its column and its two diagonals as taken,

(11) and note its column for this row.

(12) Place queens in the remaining rows.

(13) Undo all four records, in reverse order, so the next column in this row starts from a clean state.

Four pieces of state, four undos. Miss one and later branches see phantom queens. Writing the undos in reverse order of the additions is a habit that makes them easy to check by eye.

No board is stored during the search. placement[r] = c is all the information there is, and the board strings are built only when a solution is complete. That keeps the recursion light and the state trivial to undo.

The check is one line and O(1), which is the entire performance story.

Why r − c can be negative ​

r − c ranges from −(n−1) to n−1. A set handles negative keys with no trouble.

If you wanted arrays instead of sets — which is faster — offset the index by n − 1 so it lands in 0 … 2n−2:

python
diag = [False] * (2 * n - 1)     # index with (r - c + n - 1)
anti = [False] * (2 * n - 1)     # index with (r + c)

That offset is the only fiddly part. Mention it as the improvement you would make if the size mattered.

Edge cases ​

  • n = 1. One board: ["Q"].
  • n = 2 and n = 3. No solution exists, and the answer is []. Every placement ends with some row where all squares are attacked.
  • n = 4. Two solutions, mirror images of each other.

Complexity ​

O(n!) in the worst case: n choices in the first row, at most n−1 compatible in the second, and so on. In practice the diagonal constraints cut it far below n!.

O(n) space for the sets and the placement, plus the output.

There is no known polynomial algorithm for counting N-Queens solutions, and the counts are only known up to about n = 27, each one having taken serious computing effort. Saying that is a good way to answer "can you do better".

Let's break this down further:

  • Time Complexity: The first row has n choices. The second row has at most n-1 valid choices (since the column used above is blocked, and diagonals block others). The third row has at most n-2 choices, and so on. This bounds the total number of operations strictly by O(n!). Our constant-time O(1) set lookups mean checking legality adds no extra overhead.
  • Space Complexity: The recursion goes n levels deep. The three sets (cols, diag, anti) and the placement array each store at most n items. Therefore, auxiliary space is strictly O(n), excluding the final output arrays.

The bitmask version ​

For the fastest known implementation, replace the three sets with three integers, one bit per group.

python
def solveNQueens(self, n):
    result = []
    def backtrack(r, cols, diag, anti, placement):
        if r == n:
            result.append(...)
            return
        available = ~(cols | diag | anti) & ((1 << n) - 1)   # free columns
        while available:
            bit = available & -available                     # lowest set bit
            available -= bit
            c = bit.bit_length() - 1
            backtrack(r + 1, cols | bit, (diag | bit) << 1,
                      (anti | bit) >> 1, placement + [c])
    backtrack(0, 0, 0, 0, [])
    return result

The elegant part: shifting the diagonal masks by one as you move to the next row is exactly what a diagonal does geometrically. A ↘ diagonal moves one column right per row, hence << 1; a ↗ diagonal moves one left, hence >> 1. No arithmetic on indices at all.

available & -available isolates the lowest set bit, an idiom from 4.29.

Know it exists. Write the set version in an interview — it is readable and you can explain every line — and mention this if asked about speed.

Where this goes next ​

  • N-Queens II — count the solutions instead of listing them. Same search, no board building.
  • Sudoku Solver — this template with three group families (row, column, box) instead of three (column, two diagonals). The validity check from 4.4.8 becomes the pruning step, which is why the bitmask version of that check earns its keep.
  • Constraint satisfaction generally — graph colouring, scheduling, timetabling. All of them are "assign values to variables subject to constraints", and all of them are this template with better heuristics on top (choose the most constrained variable first, and the least constraining value).

What the interviewer will push on ​

"How do you name the diagonals?" r − c and r + c. Derive it by saying what happens to each coordinate as you step along the diagonal.

"Why one queen per row?" They cannot share a row, and there are n of each, so it is forced. That reduction is the first thing to say.

"Where does the pruning happen and how much does it buy?" At the moment of placing, and it takes 8^8 = 16.7 million down to about 2,000.

"Can you make the check O(1)?" Sets or arrays keyed by the three group names — which it already is.

"How would you speed it up further?" Bitmasks, with the diagonal masks shifted per row.

One thing to volunteer: connect it to Valid Sudoku. "Both problems are 'this cell belongs to several overlapping groups' — I name each group with a formula and keep one set per group." That is the transferable idea, and it is why these two problems belong in the same head.

Next: 4.19 moves from trees to graphs, where a node can have many parents and cycles are allowed — and where the heap you built in 4.16 becomes the engine of shortest-path search.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet