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: You need to count how many distinct ways n queens can be placed on an n x n chessboard so that no two queens attack each other. Queens attack horizontally, vertically, and diagonally, so every placement must guarantee unique rows, columns, and diagonals.
Approach 1: Backtracking with Sets for Column and Diagonal Validation (Time: O(N!), Space: O(N))
This approach places queens row by row using backtracking. For each row, iterate through all columns and check if placing a queen is valid. Maintain three sets: one for used columns, one for the main diagonals (row - col), and one for anti-diagonals (row + col). A placement is valid if the column and both diagonals are unused. If valid, place the queen, mark the sets, and recurse to the next row. When you reach row n, you found a valid configuration, so increment the count.
The key insight is that rows are inherently unique because the algorithm processes them sequentially. Only column and diagonal conflicts must be tracked. This pruning eliminates most invalid branches early. Backtracking then removes the queen and continues exploring other column choices.
Approach 2: Bitmasking for Efficient Column and Diagonal Checking (Time: O(N!), Space: O(1))
This optimized variant replaces sets with integer bitmasks, a common trick in competitive programming and bitmasking problems. Each bit represents whether a column or diagonal is occupied. Three masks track state: cols, diag1, and diag2. A bit set to 1 means the position is blocked.
At each row, compute available positions using bit operations: available = ~(cols | diag1 | diag2) & ((1 << n) - 1). Extract the rightmost available position using pos = available & -available, place the queen, then recursively update masks. Diagonals shift each recursive level: (diag1 | pos) << 1 and (diag2 | pos) >> 1.
Bit operations make validation constant-time and avoid hash set overhead. This significantly speeds up the search, especially for larger n. The algorithm still explores permutations of queen placements, so worst-case complexity remains factorial, but the constant factors are much smaller.
Recommended for interviews: Start with the classic backtracking solution using column and diagonal sets. It clearly demonstrates how you manage constraints in a search tree and shows strong understanding of recursion. After that, mention the bitmask optimization. Interviewers like seeing both: the first proves correctness and clarity, the second shows performance awareness.
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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
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 | 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Column and Diagonal Sets | O(N!) | O(N) | Best for explaining the algorithm clearly in interviews and understanding constraint pruning |
| Bitmasking with Recursive Backtracking | O(N!) | O(1) | Preferred for performance and competitive programming where bit operations reduce overhead |
N-Queens - Backtracking - Leetcode 51 - Python • NeetCode • 205,973 views views
Watch 9 more video solutions →Practice N-Queens II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor