N Queens II

HARD✓ CHIP-TIMEDLC #52 — FULL STATEMENT ↗

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.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

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.

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

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

THE HINTS — TAKE 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 BOARD — THE 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 SPLITS — TWO 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-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED