51. N-Queens¶

Edited by Charles

Hard · Python · Backtrack

Problem

Read the original problem on LeetCode.

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

See the Python implementation and detailed notes below.

Original study notes follow, including intermediate snippets and earlier attempts.

Approach: Backtracking¶

Core Idea¶

We need to place n queens on an n × n chessboard such that no two queens attack each other.

Two queens attack each other if they are in the same:

row
column
diagonal

The key idea is:

Place exactly one queen in each row.

Therefore, each level of recursion represents one row.

For the current row, we try every column:

for j in range(n):

If placing a queen at:

(row, j)

is valid, we:

place the queen
recursively move to the next row
remove the queen when backtracking

Board Representation¶

We initialize the board as:

[['.'] * n for _ in range(n)]

For example, when n = 4:

. . . .
. . . .
. . . .
. . . .

A queen is represented by:

and an empty position is represented by:

Meaning of `row`¶

The recursion starts with:

self.backtrack(0, n, board)

Here:

row = current row where we want to place a queen

Each recursive call moves to the next row:

self.backtrack(row + 1, n, board)

So the recursion structure is:

row 0
  ↓
row 1
  ↓
row 2
  ↓
...
  ↓
row n

This automatically guarantees that there is at most one queen in each row.

Therefore, we do not need to check whether another queen exists in the same row.

Try Every Column¶

For the current row:

for j in range(n):

we try placing the queen in every possible column:

(row, 0)
(row, 1)
(row, 2)
...
(row, n - 1)

Before placing the queen, we check:

if self.isValid(row, j, board, n):

If the position is valid:

board[row][j] = 'Q'

then recursively process the next row:

self.backtrack(row + 1, n, board)

After returning from recursion, undo the choice:

board[row][j] = '.'

This is the standard backtracking pattern:

make a choice
    ↓
recurse
    ↓
undo the choice

Base Case¶

When:

row == n

it means we have successfully placed one queen in every row.

Therefore, we found one valid solution:

if row == n:
    self.res.append([''.join(r) for r in board])
    return

The board currently looks like:

[
    ['.', 'Q', '.', '.'],
    ['.', '.', '.', 'Q'],
    ['Q', '.', '.', '.'],
    ['.', '.', 'Q', '.']
]

But LeetCode requires:

[
    ".Q..",
    "...Q",
    "Q...",
    "..Q."
]

Therefore, we convert every row into a string:

[''.join(r) for r in board]

Since we place queens row by row from top to bottom, when we are trying to place a queen at:

(row, col)

all existing queens must be above the current row.

Therefore, we only need to check:

1. Same column
2. Upper-left diagonal
3. Upper-right diagonal

We do not need to check:

same row
lower-left diagonal
lower-right diagonal

because:

the current row does not contain another queen
lower rows have not been processed yet

Check the Same Column¶

We check whether there is already a queen in the same column:

for i in range(n):
    if board[i][col] == 'Q':
        return False

For example:

. . Q .
. . . .
. . X .
. . . .

If we want to put a queen at X, there is already a queen above it in the same column.

Therefore, the position is invalid.

Conceptually, because queens are placed from top to bottom, checking only:

for i in range(row):

would also be enough.

But the current code checks the whole column, which is also correct.

Check the Upper-Left Diagonal¶

Starting from:

(row - 1, col - 1)

we continuously move:

↖

by doing:

rowIdx -= 1
colIdx -= 1

Code:

rowIdx, colIdx = row - 1, col - 1

while rowIdx >= 0 and colIdx >= 0:
    if board[rowIdx][colIdx] == 'Q':
        return False

    rowIdx -= 1
    colIdx -= 1

Example:

Q . . .
. X . .
. . . .
. . . .

The queen and X are on the same diagonal, so X is invalid.

Check the Upper-Right Diagonal¶

Starting from:

(row - 1, col + 1)

we continuously move:

↗

by doing:

rowIdx -= 1
colIdx += 1

Code:

rowIdx, colIdx = row - 1, col + 1

while rowIdx >= 0 and colIdx < n:
    if board[rowIdx][colIdx] == 'Q':
        return False

    rowIdx -= 1
    colIdx += 1

Example:

. . . Q
. . X .
. . . .
. . . .

Again, X is attacked diagonally by the queen.

Consider:

n = 4

Initially:

....
....
....
....

Start with:

row = 0

Try column 0:

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

Then recursively process:

row = 1

Column 0 is invalid because of the same column:

Q...
X...
....
....

Column 1 is invalid because of the diagonal:

Q...
.X..
....
....

Column 2 is valid:

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

Then recursively process row 2.

If no valid position can be found later, we backtrack:

board[row][j] = '.'

and try the next column.

Therefore, the search explores possibilities like:

row 0
├── col 0
│   ├── row 1 col 2
│   │   └── ...
│   └── row 1 col 3
│       └── ...
│
├── col 1
│   └── ...
│
├── col 2
│   └── ...
│
└── col 3
    └── ...

Invalid branches are removed immediately by isValid().

This is the pruning step of backtracking.

In combination problems, we often use:

backtrack(startIndex)

because we are choosing elements from a candidate list.

For example:

LeetCode 77 — Combinations

might use:

for i in range(startIndex, n):

But N-Queens is different.

Each recursion level already represents a specific row.

The structure is:

recursion level → row
for loop        → column

Therefore:

def backtrack(row):
    for col in range(n):

is enough.

There is no need for a startIndex.

The structure can be summarized as:

def backtrack(row):
    if all rows are processed:
        save solution
        return

    for col in every column:
        if position is valid:
            place queen

            backtrack(row + 1)

            remove queen

For this problem:

if self.isValid(row, j, board, n):
    board[row][j] = 'Q'

    self.backtrack(row + 1, n, board)

    board[row][j] = '.'

There are at most n choices for the first row, then fewer choices for later rows because many positions become invalid.

A commonly used upper bound for the backtracking search is:

O(n!)

because each row can use a different column.

In this implementation, however, isValid() also scans columns and diagonals, costing up to:

O(n)

per validity check.

So the practical complexity includes this additional checking cost.

The board uses:

O(n²)

space.

The recursion depth is:

O(n)

One recursion level represents one row¶

backtrack(row)

means:

Find a valid column for the queen in the current row.

The `for` loop represents column choices¶

for j in range(n):

means:

Try placing the queen in every column of the current row.

Therefore:

recursion → rows
for loop  → columns

Only check previously placed queens¶

Since queens are placed from top to bottom, we only need to check:

↑   same column
↖   upper-left diagonal
↗   upper-right diagonal

There is no need to check the lower part of the board.

Standard backtracking structure¶

Choose
↓
Explore
↓
Undo

In this problem:

board[row][j] = 'Q'

self.backtrack(row + 1, n, board)

board[row][j] = '.'

`isValid()` is the pruning step¶

Without validity checking, we would explore many impossible boards.

isValid() immediately removes branches where the new queen would be attacked.

Therefore:

Backtracking
=
DFS
+
Pruning
+
Undoing choices

The most important sentence for this problem is:

Each recursion level fixes one row, and the loop tries every possible column in that row.

Study record

Field	Value
Attempts	1
Mastery	❚
The Latest Attempt	September 5, 2026

Python solution¶

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        self.res = []
        self.backtrack(0, n, [['.'] * n for _ in range(n)])
        return self.res

    def backtrack(self, row, n, board):
        if row == n:
            self.res.append([''.join(r) for r in board])
            return

        for j in range(n):
            if self.isValid(row, j, board, n):
                board[row][j] = 'Q'

                self.backtrack(row + 1, n, board)

                board[row][j] = '.'

    def isValid(self, row, col, board, n):
        # 1. Check the same column
        for i in range(n):
            if board[i][col] == 'Q':
                return False

        # 2. Check upper-left diagonal
        rowIdx, colIdx = row - 1, col - 1

        while rowIdx >= 0 and colIdx >= 0:
            if board[rowIdx][colIdx] == 'Q':
                return False

            rowIdx -= 1
            colIdx -= 1

        # 3. Check upper-right diagonal
        rowIdx, colIdx = row - 1, col + 1

        while rowIdx >= 0 and colIdx < n:
            if board[rowIdx][colIdx] == 'Q':
                return False

            rowIdx -= 1
            colIdx += 1

        return True

Back to Day 22 Backtrack IV · All Algorithm notes

51. N-Queens¶

Approach: Backtracking¶

Core Idea¶

Board Representation¶

Meaning of row¶

Try Every Column¶

Base Case¶

Check the Same Column¶

Check the Upper-Left Diagonal¶

Check the Upper-Right Diagonal¶

One recursion level represents one row¶

The for loop represents column choices¶

Only check previously placed queens¶

Standard backtracking structure¶

isValid() is the pruning step¶

Python solution¶

Meaning of `row`¶

The `for` loop represents column choices¶

`isValid()` is the pruning step¶