N Queens II

The briefingthe full drill, in my own words

The drill: Same board, no boards to draw — just count how many ways n queens can occupy an n×n grid with none attacking another along any row, column, or diagonal.

A board size n arrives, and the task is the counting twin of the classic queens puzzle: instead of drawing every valid board, just report how many ways n queens can be placed on an n×n board with none attacking another.

The same rules apply as always — no two queens sharing a row, a column, or either diagonal — but nothing about the boards themselves needs to be produced or stored, only their total count.

Some sizes of n admit no valid arrangement at all, in which case the honest count is zero.

n is small, typically under ten
no two queens may share a row, column, or either diagonal
only the total count of valid arrangements is needed, not the arrangements
a board with no valid arrangement reports a count of zero

EX 01

n = 1

→ 1

minimum size, one queen alone

EX 02

n = 2

→ 0

no placement escapes attack on a 2x2 board

EX 03

n = 3

→ 0

still no valid placement on a 3x3 board

The hintstake only what you need

HINT 1 THE NUDGE

The placement logic here is identical to arranging n non-attacking queens — the only thing that changes is what you keep at the end. What's cheaper to build when the boards themselves are never needed?

HINT 2 THE STRUCTURE

Columns and diagonals are each just a range of n positions — instead of three sets of used values, represent 'taken' as bits in three integers, and 'free right now' is the complement of their union.

HINT 3 ONE STEP FROM THE ANSWER

Backtrack row by row over an integer bitmask: peel off one available bit at a time with avail & -avail, recurse with that column and both diagonals marked (shifting the diagonal masks by one row as you descend), and bump the counter only when every row is filled.

Coach's boardthe pattern, step by step

THE BIT COUNTPATTERN · BITMASK BACKTRACKINGn = 4 · count only, no boards stored

STEP 1

n = 4. No board is built — cols, diag1, diag2 pack into three integers, and avail = full & ~(cols|diag1|diag2).

STEP 1 / 10 · ← → WORK TOO

The splitstwo paces, two languages

grind/n-queens-ii.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def totalNQueens(self, n: int) -> int:
        full = (1 << n) - 1
        count = 0

        def backtrack(cols: int, diag1: int, diag2: int) -> None:
            nonlocal count
            if cols == full:
                count += 1
                return
            avail = full & ~(cols | diag1 | diag2)
            while avail:
                bit = avail & (-avail)
                avail -= bit
                backtrack(cols | bit, (diag1 | bit) << 1 & full, (diag2 | bit) >> 1)

        backtrack(0, 0, 0)
        return count

TIME O(N!)SPACE O(N)PYTHON · RACE PACE · 18 LN

class Solution:
    def totalNQueens(self, n: int) -> int:
        count = 0

        def is_safe(cols: List[int]) -> bool:
            for r1 in range(len(cols)):
                for r2 in range(r1 + 1, len(cols)):
                    if abs(cols[r1] - cols[r2]) == abs(r1 - r2):
                        return False
            return True

        def permute(chosen: List[int], remaining: List[int]) -> None:
            nonlocal count
            if not remaining:
                if is_safe(chosen):
                    count += 1
                return
            for i in range(len(remaining)):
                permute(chosen + [remaining[i]], remaining[:i] + remaining[i + 1:])

        permute([], list(range(n)))
        return count

TIME O(N! · N²)SPACE O(N)PYTHON · TRAINING PACE · 22 LN

class Solution {
    private int count = 0;
    private int full;

    public int totalNQueens(int n) {
        full = (1 << n) - 1;
        backtrack(0, 0, 0);
        return count;
    }

    private void backtrack(int cols, int diag1, int diag2) {
        if (cols == full) {
            count++;
            return;
        }
        int avail = full & ~(cols | diag1 | diag2);
        while (avail != 0) {
            int bit = avail & (-avail);
            avail -= bit;
            backtrack(cols | bit, (diag1 | bit) << 1 & full, (diag2 | bit) >> 1);
        }
    }
}

TIME O(N!)SPACE O(N)JAVA · RACE PACE · 23 LN

class Solution {
    private int count = 0;

    public int totalNQueens(int n) {
        List<Integer> remaining = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            remaining.add(i);
        }
        permute(new ArrayList<>(), remaining);
        return count;
    }

    private void permute(List<Integer> chosen, List<Integer> remaining) {
        if (remaining.isEmpty()) {
            if (isSafe(chosen)) {
                count++;
            }
            return;
        }
        for (int i = 0; i < remaining.size(); i++) {
            List<Integer> nextChosen = new ArrayList<>(chosen);
            nextChosen.add(remaining.get(i));
            List<Integer> nextRemaining = new ArrayList<>(remaining);
            nextRemaining.remove(i);
            permute(nextChosen, nextRemaining);
        }
    }

    private boolean isSafe(List<Integer> cols) {
        for (int r1 = 0; r1 < cols.size(); r1++) {
            for (int r2 = r1 + 1; r2 < cols.size(); r2++) {
                if (Math.abs(cols.get(r1) - cols.get(r2)) == r2 - r1) {
                    return false;
                }
            }
        }
        return true;
    }
}

TIME O(N! · N²)SPACE O(N)JAVA · TRAINING PACE · 39 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED