N-Queens II — Solution in Python, Java & C++
N-Queens II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon and Google.
N-Queens II is a hard coding problem on bit manipulation and backtracking, asked in Amazon, Google, Microsoft and Mphasis interviews.
- Difficulty: Hard
- Topics: Bit Manipulation, Backtracking
- Asked at: Amazon, Google, Microsoft, Mphasis
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Place n chess queens on an n x n board so that no two of them attack each other: no two queens may share a row, a column, or a diagonal (in either direction).
Return the number of different placements. Two placements are different when some square holds a queen in one and not in the other — mirror images and rotations count separately.
Example 1
Input: n = 4
Output: 2
Explanation: The two placements put the queens in columns `[1,3,0,2]` and `[2,0,3,1]` of rows 0..3.
Example 2
Input: n = 1
Output: 1
Example 3
Input: n = 6
Output: 4
Constraints
1 <= n <= 9
Hints for N-Queens II
Hint 1
Every row holds exactly one queen, so place them row by row and only choose the column.
Hint 2
A square is attacked when its column, its
row - coldiagonal or itsrow + colanti-diagonal is already taken. Keep three sets (or three bitmasks).Hint 3
With bitmasks, shift the diagonal masks by one bit when moving to the next row; the free columns are
~(cols | diag | anti) & full, and the lowest set bit isx & -x.
How to solve N-Queens II
Place one queen per row and backtrack over the column choice. Bitmasks for the occupied columns and both diagonal directions make each "is this square free?" test a single AND.
Approach
- Let
full = (1 << n) - 1.solve(cols, d1, d2)returns the number of completions; whencols == full, every row has a queen, so return 1. - The free squares of the current row are
full & ~(cols | d1 | d2). - For each free bit
b(takefree & -free, then clear it), addsolve(cols | b, ((d1 | b) << 1) & full, (d2 | b) >> 1). - Return
solve(0, 0, 0).
Why it works
A queen in column c of the current row attacks column c - 1 (or c + 1) of the next row along its diagonals, and one further per row after that — shifting the diagonal masks by one bit per row tracks exactly those squares. So the search visits exactly the valid partial placements, and every complete one is counted once because each row's column is chosen once.
Complexity
- Time —
O(n!) in the worst case — far less in practice thanks to pruning - Space —
O(n) recursion depth
Pitfalls
- Shift the two diagonal masks in opposite directions.
- Mask the left-shifted diagonal (or the free set) with
full, or bits beyond the board look occupied or free. - n = 2 and n = 3 have no solution: the answer is 0, not an error.
Reference solution
Python
def totalNQueens(n: int) -> int:
full = (1 << n) - 1
def solve(cols, d1, d2):
if cols == full:
return 1
count = 0
avail = full & ~(cols | d1 | d2)
while avail:
bit = avail & -avail
avail ^= bit
count += solve(cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1)
return count
return solve(0, 0, 0)Java
public static int totalNQueens(int n) {
return queensSolve((1 << n) - 1, 0, 0, 0);
}
static int queensSolve(int full, int cols, int d1, int d2) {
if (cols == full) return 1;
int count = 0;
int avail = full & ~(cols | d1 | d2);
while (avail != 0) {
int bit = avail & -avail;
avail ^= bit;
count += queensSolve(full, cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1);
}
return count;
}C++
int queensSolve(int full, int cols, int d1, int d2) {
if (cols == full) return 1;
int count = 0;
int avail = full & ~(cols | d1 | d2);
while (avail != 0) {
int bit = avail & -avail;
avail ^= bit;
count += queensSolve(full, cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1);
}
return count;
}
int totalNQueens(int n) {
return queensSolve((1 << n) - 1, 0, 0, 0);
}JavaScript
var totalNQueens = function(n) {
var full = (1 << n) - 1;
var solve = function(cols, d1, d2) {
if (cols === full) return 1;
var count = 0;
var avail = full & ~(cols | d1 | d2);
while (avail !== 0) {
var bit = avail & -avail;
avail ^= bit;
count += solve(cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1);
}
return count;
};
return solve(0, 0, 0);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 146 bit manipulation problems · the whole catalogue
Learn the technique: Bit Manipulation · Backtracking