How do you approach N-Queens II?

Place one queen per row, tracking occupied columns and both diagonals.

What are common mistakes on N-Queens II?

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.

gitGood.dev

← Back to problems

N-Queens II

HardAlgorithms

Description

The n-queens puzzle places n queens on an n x n chessboard so that no two queens attack each other (same row, column, or diagonal).

Given n, return the number of distinct solutions.

Example 1

Input: n = 4

Output: 2

Explanation: There are two distinct placements.

Example 2

Input: n = 1

Output: 1

Explanation: A single queen on a 1x1 board.

Constraints

- 1 <= n <= 9

N-Queens II: approach, complexity and pitfalls

A hard backtracking problem, graded against 5 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.

If you are stuck

Show the 2-step hint ladder

Place one queen per row, tracking occupied columns and both diagonals.
A cell (row, col) is attacked if col, row-col, or row+col is already used.

The optimal approach

Show the approach: The approach

Row-by-row backtracking with diagonal sets. Track used columns, used `row - col` diagonals, and used `row + col` anti-diagonals. Place a queen in each safe column, recurse to the next row, and count completed boards.

Time: O(n!). Space: O(n).

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.