N-Queens II solution and explanation
Google
9 more videos on this problem
N-Queens II - Leetcode 52 - PythonNeetCode · 13:58 · 42K views
LEETCODE 51 & 52 (JAVASCRIPT) | N QUEENS I & IIAndy Gala · 25:51 · 3K views
N Queens II | N Queens 2 | Leetcode 52 | Live coding session | Leetcode HardCoding Decoded · 9:43 · 2K views
Leetcode 51 & 52 N-Queens (Backtracking) - javascriptThe Code Show · 20:29 · 955 views
N-Queens II | LeetCode 52 | Coders CampCoders Camp · 9:46 · 784 views
N-Queens II - LeetCode 52 - JavaScriptAlgoJS · 7:59 · 781 views
LeetCode 52. N-Queens IIHappy Coding · 10:04 · 742 views
52. N-Queens II (Leetcode Hard)Programming Live with Larry · 20:44 · 623 views
52. N-Queens II | Leetcode HardJOY of LIFE · 24:15 · 618 views
leetCode 52 N-Queens II (Backtracking) | JSer - algorithm and JavaScriptJSer · 1:41 · 609 views
The problem
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.
class Solution:
def totalNQueens(self, n: int) -> int:
def backtrack(row = 0):
if row == n:
return 1
count = 0
for col in range(n):
if col in cols or (row + col) in diag1 or (row - col) in diag2:
continue
cols.add(col)
diag1.add(row + col)
diag2.add(row - col)
count += backtrack(row + 1)
cols.remove(col)
diag1.remove(row + col)
diag2.remove(row - col)
return count
cols = set()
diag1 = set()
diag2 = set()
return backtrack()import java.util.HashSet;
public class Solution {
public int totalNQueens(int n) {
HashSet<Integer> cols = new HashSet<>();
HashSet<Integer> diag1 = new HashSet<>();
HashSet<Integer> diag2 = new HashSet<>();
return backtrack(0, n, cols, diag1, diag2);
}
private int backtrack(int row, int n, HashSet<Integer> cols, HashSet<Integer> diag1, HashSet<Integer> diag2) {
if (row == n) return 1;
int count = 0;
for (int col = 0; col < n; col++) {
if (cols.contains(col) || diag1.contains(row + col) || diag2.contains(row - col)) continue;
cols.add(col);
diag1.add(row + col);
diag2.add(row - col);
count += backtrack(row + 1, n, cols, diag1, diag2);
cols.remove(col);
diag1.remove(row + col);
diag2.remove(row - col);
}
return count;
}
}#include <vector>
#include <unordered_set>
class Solution {
public:
int totalNQueens(int n) {
std::unordered_set<int> columns, diag1, diag2;
return backtrack(0, n, columns, diag1, diag2);
}
private:
int backtrack(int row, int n, std::unordered_set<int>& columns, std::unordered_set<int>& diag1, std::unordered_set<int>& diag2) {
if (row == n) return 1;
int count = 0;
for (int col = 0; col < n; ++col) {
if (columns.count(col) || diag1.count(row + col) || diag2.count(row - col)) continue;
columns.insert(col);
diag1.insert(row + col);
diag2.insert(row - col);
count += backtrack(row + 1, n, columns, diag1, diag2);
columns.erase(col);
diag1.erase(row + col);
diag2.erase(row - col);
}
return count;
}
};var totalNQueens = function(n) {
let cols = new Set();
let diag1 = new Set();
let diag2 = new Set();
const backtrack = (row) => {
if (row === n) return 1;
let count = 0;
for (let col = 0; col < n; col++) {
if (cols.has(col) || diag1.has(row + col) || diag2.has(row - col)) continue;
cols.add(col);
diag1.add(row + col);
diag2.add(row - col);
count += backtrack(row + 1);
cols.delete(col);
diag1.delete(row + col);
diag2.delete(row - col);
}
return count;
};
return backtrack(0);
};#include <stdbool.h>
#include <stdlib.h>
int totalNQueens(int n) {
int count = 0;
bool *columns = calloc(n, sizeof(bool));
bool *diag1 = calloc(2 * n, sizeof(bool));
bool *diag2 = calloc(2 * n, sizeof(bool));
solve(0, n, columns, diag1, diag2, &count);
free(columns);
free(diag1);
free(diag2);
return count;
}
void solve(int row, int n, bool *columns, bool *diag1, bool *diag2, int *count) {
if (row == n) {
(*count)++;
return;
}
for (int col = 0; col < n; col++) {
if (!columns[col] && !diag1[row + col] && !diag2[row - col + n]) {
columns[col] = diag1[row + col] = diag2[row - col + n] = true;
solve(row + 1, n, columns, diag1, diag2, count);
columns[col] = diag1[row + col] = diag2[row - col + n] = false;
}
}
}using System.Collections.Generic;
public class Solution {
public int TotalNQueens(int n) {
var cols = new HashSet<int>();
var diag1 = new HashSet<int>();
var diag2 = new HashSet<int>();
return Backtrack(0, n, cols, diag1, diag2);
}
private int Backtrack(int row, int n, HashSet<int> cols, HashSet<int> diag1, HashSet<int> diag2) {
if (row == n) return 1;
int count = 0;
for (int col = 0; col < n; col++) {
if (cols.Contains(col) || diag1.Contains(row + col) || diag2.Contains(row - col)) continue;
cols.Add(col);
diag1.Add(row + col);
diag2.Add(row - col);
count += Backtrack(row + 1, n, cols, diag1, diag2);
cols.Remove(col);
diag1.Remove(row + col);
diag2.Remove(row - col);
}
return count;
}
}The Python approach uses sets for columns and diagonals to check availability and recursively attempts to place queens one row at a time. It handles constraints by dynamically updating and rolling back changes in the sets.
Time Complexity: O(n!), due to comprehensive exploration.
Space Complexity: O(n) for recursion depth and sets handling.
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.
class Solution:
def totalNQueens(self, n: int) -> int:
def solve(row, columns, diag1, diag2):
if row == n:
return 1
count = 0
for col in range(n):
if not (columns & (1 << col)) and not (diag1 & (1 << (row + col))) and not (diag2 & (1 << (row - col + n - 1))):
count += solve(row + 1, columns | (1 << col), diag1 | (1 << (row + col)), diag2 | (1 << (row - col + n - 1)))
return count
return solve(0, 0, 0, 0)public class Solution {
public int totalNQueens(int n) {
return solve(n, 0, 0, 0, 0);
}
private int solve(int n, int row, int columns, int diag1, int diag2) {
if (row == n) return 1;
int count = 0;
for (int col = 0; col < n; col++) {
int colMask = 1 << col;
if ((columns & colMask) == 0 && (diag1 & (1 << (row + col))) == 0 && (diag2 & (1 << (row - col + n - 1))) == 0) {
count += solve(n, row + 1, columns | colMask, diag1 | (1 << (row + col)), diag2 | (1 << (row - col + n - 1)));
}
}
return count;
}
}#include <vector>
class Solution {
public:
int totalNQueens(int n) {
return solve(n, 0, 0, 0, 0);
}
int solve(int n, int row, int columns, int diag1, int diag2) {
if (row == n) return 1;
int count = 0;
for (int col = 0; col < n; ++col) {
int colMask = 1 << col;
if (!(columns & colMask) && !(diag1 & (1 << (row + col))) && !(diag2 & (1 << (row - col + n - 1)))) {
count += solve(n, row + 1, columns | colMask, diag1 | (1 << (row + col)), diag2 | (1 << (row - col + n - 1)));
}
}
return count;
}
};var totalNQueens = function(n) {
const solve = (row, columns, diag1, diag2) => {
if (row === n) return 1;
let count = 0;
for (let col = 0; col < n; col++) {
if ((columns & (1 << col)) === 0 && (diag1 & (1 << (row + col))) === 0 && (diag2 & (1 << (row - col + n - 1))) === 0) {
count += solve(row + 1, columns | (1 << col), diag1 | (1 << (row + col)), diag2 | (1 << (row - col + n - 1)));
}
}
return count;
};
return solve(0, 0, 0, 0);
};#include <stdbool.h>
int totalNQueens(int n) {
return solve(0, n, 0, 0, 0);
}
int solve(int row, int n, int columns, int diag1, int diag2) {
if (row == n) return 1;
int count = 0;
for (int col = 0; col < n; col++) {
int colMask = 1 << col;
if (!(columns & colMask) && !(diag1 & (1 << (row + col))) && !(diag2 & (1 << (row - col + n - 1)))) {
count += solve(row + 1, n, columns | colMask, diag1 | (1 << (row + col)), diag2 | (1 << (row - col + n - 1)));
}
}
return count;
}public class Solution {
public int TotalNQueens(int n) {
return Solve(n, 0, 0, 0, 0);
}
private int Solve(int n, int row, int columns, int diag1, int diag2) {
if (row == n) return 1;
int count = 0;
for (int col = 0; col < n; col++) {
int colMask = 1 << col;
if ((columns & colMask) == 0 && (diag1 & (1 << (row + col))) == 0 && (diag2 & (1 << (row - col + n - 1))) == 0) {
count += Solve(n, row + 1, columns | colMask, diag1 | (1 << (row + col)), diag2 | (1 << (row - col + n - 1)));
}
}
return count;
}
}The Python method focuses on bitwise operations to manage placements, making column and diagonal checks very fast. Even across a relatively small n=9 board, bit manipulations provide a clear advantage in processing speed.
Time Complexity: O(n!). Operations within recursion are highly optimized via bit manipulations.
Space Complexity: O(n) for recursive handling.
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.
function totalNQueens(n: number): number {
const cols: boolean[] = Array(10).fill(false);
const dg: boolean[] = Array(20).fill(false);
const udg: boolean[] = Array(20).fill(false);
let ans = 0;
const dfs = (i: number) => {
if (i === n) {
++ans;
return;
}
for (let j = 0; j < n; ++j) {
let [a, b] = [i + j, i - j + n];
if (cols[j] || dg[a] || udg[b]) {
continue;
}
cols[j] = dg[a] = udg[b] = true;
dfs(i + 1);
cols[j] = dg[a] = udg[b] = false;
}
};
dfs(0);
return ans;
}func totalNQueens(n int) (ans int) {
cols := [10]bool{}
dg := [20]bool{}
udg := [20]bool{}
var dfs func(int)
dfs = func(i int) {
if i == n {
ans++
return
}
for j := 0; j < n; j++ {
a, b := i+j, i-j+n
if cols[j] || dg[a] || udg[b] {
continue
}
cols[j], dg[a], udg[b] = true, true, true
dfs(i + 1)
cols[j], dg[a], udg[b] = false, false, false
}
}
dfs(0)
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Backtracking using Sets for Column and Diagonals Validation | Time Complexity: O(n!), due to comprehensive exploration. |
| Bitmasking for Efficient Column and Diagonal Checking | Time Complexity: O(n!). Operations within recursion are highly optimized via bit manipulations. |
| Backtracking | – |
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 |
Frequently asked questions
Is N-Queens II easy or hard?
N-Queens II is classified as a Hard problem because it requires designing a backtracking search with efficient pruning. Understanding how diagonals are represented and optimized using sets or bitmasks is the key difficulty.
N-Queens II Python/Java solution
Python and Java implementations usually use recursive backtracking. Python solutions often rely on sets or bitmasks for column and diagonal tracking, while Java solutions commonly use boolean arrays or bit operations for better performance.
How to solve N-Queens II in O(n)?
N-Queens II cannot be solved in O(n) time because the problem requires exploring combinations of queen placements. The best known approaches use backtracking with pruning, which runs in roughly O(n!) time. Bitmasking reduces constant overhead but does not change the theoretical complexity.
What is the best approach for N-Queens II?
Backtracking with pruning is the standard solution. Track used columns, main diagonals, and anti-diagonals while placing queens row by row. This reduces the search space dramatically compared to brute force. An optimized variant uses bitmasking for faster conflict checks.
Is N-Queens II asked at Google/Amazon/Meta?
N-Queens style problems frequently appear in technical interviews at companies like Google, Amazon, and Meta because they test backtracking, recursion, and constraint pruning. Variants may ask for the number of solutions or the actual board configurations.
What data structure is used in N-Queens II?
Typical implementations use sets or boolean arrays to track occupied columns and diagonals. Optimized solutions replace these structures with integer bitmasks so column and diagonal conflicts can be checked using fast bit operations.
What is the time complexity of N-Queens II?
The time complexity is approximately O(n!) because each row tries multiple column placements and recursively explores valid configurations. Pruning with column and diagonal checks prevents exploring invalid branches, which significantly reduces the practical search space.