Watch 10 video solutions for N-Queens II, a hard level problem involving Backtracking. This walkthrough by NeetCode has 205,973 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 9Problem 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 | 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 |