N-Queens II

Hard
1578.

N-Queens II

N-Queens II is a hard coding problem on bit manipulation and backtracking, asked in Amazon, Google, Microsoft and Mphasis interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var totalNQueens = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

  1. Hint 1

    Every row holds exactly one queen, so place them row by row and only choose the column.

  2. Hint 2

    A square is attacked when its column, its row - col diagonal or its row + col anti-diagonal is already taken. Keep three sets (or three bitmasks).

  3. 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 is x & -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

  1. Let full = (1 << n) - 1. solve(cols, d1, d2) returns the number of completions; when cols == full, every row has a queen, so return 1.
  2. The free squares of the current row are full & ~(cols | d1 | d2).
  3. For each free bit b (take free & -free, then clear it), add solve(cols | b, ((d1 | b) << 1) & full, (d2 | b) >> 1).
  4. 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