Get started

N-Queens II — Hard Problem & Solution

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).

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

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)

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 125 bit manipulation problems · the whole catalogue

Learn the technique: Bit Manipulation · Backtracking