How do you approach N-Queens?

Use backtracking to place queens row by row.

What is the time complexity of N-Queens?

Time complexity: O(n!). Space complexity: O(n^2).

What are common mistakes on N-Queens?

Pushing the working array into the results without copying it, so every entry aliases the same array. Forgetting to undo the choice after the recursive call returns. Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.

← Back to problems

N-Queens

HardAlgorithms

Description

The **N-Queens** puzzle is the problem of placing `n` queens on an `n x n` chessboard such that no two queens attack each other. Given an integer `n`, return **all distinct solutions** to the N-Queens puzzle. You may return the answer in **any order**. Each solution contains a distinct board configuration of the N-Queens' placement, where `'Q'` indicates a queen and `'.'` indicates an empty space.

Example 1

Input: n = 4

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

Explanation: There are two distinct solutions to the 4-queens puzzle.

Example 2

Input: n = 1

Output: [["Q"]]

Constraints

- 1 <= n <= 9

N-Queens: approach, complexity and pitfalls

A hard backtracking problem, graded against 6 test cases (3 of them hidden).

The pattern: Backtracking

Systematic exploration of all candidates, abandoning partial ones that cannot work.

Reach for it when you see: "All permutations/combinations/subsets", or constraint puzzles like N-Queens and Sudoku.

More Backtrackingproblems →

If you are stuck

Show the 3-step hint ladder

Use backtracking to place queens row by row.
Track which columns and diagonals are already attacked.
Two types of diagonals: row-col (top-left to bottom-right) and row+col (top-right to bottom-left).

The optimal approach

Show the approach: Backtracking

Place queens one row at a time. For each row, try every column. Use sets to track occupied columns, forward diagonals (row - col), and backward diagonals (row + col). If a placement is valid, recurse to the next row. When all rows are filled, save the board configuration.

Time: O(n!)
Space: O(n^2)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Backtracking mistakes

These apply to the pattern as a whole, not just this problem.

Pushing the working array into the results without copying it, so every entry aliases the same array.
Forgetting to undo the choice after the recursive call returns.
Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.