N-Queens II - Solution & Explanation
Problem Statement
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 the number of distinct solutions to the n-queens puzzle.
Example 1:
Input: n = 4 Output: 2 Explanation: There are two distinct solutions to the 4-queens puzzle as shown.
Example 2:
Input: n = 1 Output: 1
Constraints:
1 <= n <= 9
Approach Overview
Problem Overview: N-Queens II asks you to count how many distinct ways you can place n queens on an n × n chessboard so that no two queens attack each other. Queens attack along rows, columns, and diagonals, so every placement must avoid conflicts in all three directions.
Approach 1: Backtracking with Column and Diagonal Sets (Time: O(n!), Space: O(n))
This approach builds the board row by row using backtracking. For each row, iterate through every column and check if placing a queen causes a conflict. Three sets track occupied positions: one for columns, one for the main diagonals (row - col), and one for anti-diagonals (row + col). If a position is safe, place the queen, recurse to the next row, and remove it after returning. The search tree explores permutations of column placements, but pruning using these sets eliminates invalid branches early. Time complexity is roughly O(n!) due to the branching nature, while space complexity is O(n) for recursion depth and tracking structures.
Approach 2: Bitmasking for Efficient Column and Diagonal Checking (Time: O(n!), Space: O(n))
This version replaces sets with integer bitmasks to represent occupied columns and diagonals. Each bit position corresponds to a column on the board. During recursion, compute available positions using bit operations: available = ~(cols | diag1 | diag2) & ((1 << n) - 1). Extract the rightmost available bit, place the queen, and update masks for the next row. Diagonal masks shift left or right to represent how attacks move across rows. Bit operations are extremely fast and avoid hash lookups, which makes this approach significantly faster in practice. It still performs a backtracking search, but the constant factors are smaller due to efficient bit manipulation from bitmasking and recursive exploration using recursion.
Recommended for interviews: The classic set-based backtracking solution is the most common interview answer because it clearly demonstrates pruning logic and constraint tracking. Interviewers want to see how you model column and diagonal conflicts. The bitmask approach is the optimized version and shows deeper algorithmic maturity. Implementing both shows strong mastery of backtracking search problems.
Approach 1: Backtracking using Sets for Column and Diagonals Validation
This approach involves using backtracking to explore all possible ways of placing queens on the board. We maintain three sets to keep track of which columns and diagonals are already occupied by queens, ensuring no two queens threaten each other.
This C implementation uses arrays (`columns`, `diag1`, and `diag2`) to mark the columns and diagonals that are occupied. The function recursively attempts to place a queen in each row and calls itself for the next row if successful. The base case is when all queens are placed (`row == n`), at which point we increment the solution count.
Complexity
Time Complexity: O(n!), where n is the number of queens. Each queen has n options initially, and it decreases with increasing constraints.
Space Complexity: O(n) for the call stack and additional space for tracking columns and diagonals.
Approach 2: Bitmasking for Efficient Column and Diagonal Checking
This approach leverages bitmasking to store state information about occupied columns and diagonals. By using integer variables as bit masks, we can efficiently check and update occupation states, which is particularly useful for handling small fixed-size constraints like n <= 9.
The C implementation utilizes bitmasking for columns and diagonals, enabling efficient checking and updating of states. The code iterates over possible columns, shifting bit positions to represent occupation and recursively exploring valid paths.
Complexity
Time Complexity: O(n!). Recursive full exploration, though bitwise operations are computationally efficient.
Space Complexity: O(n) due to recursion depth and bitmask integers.
Approach 3: Backtracking
We design a function dfs(i), which represents starting the search from the ith row, and the results of the search are added to the answer.
In the ith row, we enumerate each column of the ith row. If the current column does not conflict with the queens placed before, then we can place a queen, and then continue to search the next row, that is, call dfs(i + 1).
If a conflict occurs, then we skip the current column and continue to enumerate the next column.
To determine whether a conflict occurs, we need to use three arrays to record whether a queen has been placed in each column, each positive diagonal, and each negative diagonal, respectively.
Specifically, we use the cols array to record whether a queen has been placed in each column, the dg array to record whether a queen has been placed in each positive diagonal, and the udg array to record whether a queen has been placed in each negative diagonal.
The time complexity is O(n!), and the space complexity is O(n). Here, n is the number of queens.
Code
Python
Java
C++
Go
TypeScript
JavaScript
C#
Complexity Comparison
| Approach | Complexity |
|---|---|
| Backtracking using Sets for Column and Diagonals Validation | Time Complexity: O(n!), where n is the number of queens. Each queen has n options initially, and it decreases with increasing constraints. |
| Bitmasking for Efficient Column and Diagonal Checking | Time Complexity: O(n!). Recursive full exploration, though bitwise operations are computationally efficient. |
| Backtracking | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Column and Diagonal Sets | O(n!) | O(n) | Standard interview solution; easy to explain and implement with clear pruning logic |
| Bitmasking Backtracking | O(n!) | O(n) | Performance‑optimized approach using bit operations; useful for larger n or competitive programming |
Video Solution
N-Queens II - Leetcode 52 - Python • NeetCode • 42,511 views views
Watch 9 more video solutions →Frequently Asked Questions
Is N-Queens II easy or hard?
N-Queens II Python/Java solution
How to solve N-Queens II in O(n)?
What is the best approach for N-Queens II?
Is N-Queens II asked at Google/Amazon/Meta?
What data structure is used in N-Queens II?
What is the time complexity of N-Queens II?
Ready to solve this problem?
Practice N-Queens II with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor