52/670

52. N-Queens II

Hard

This is the counting variant of the n-queens puzzle. A placement of n chess queens on an n × n board is safe when no two queens share a row, a column, or either diagonal.

Your function receives the integer n and returns a single number: how many distinct safe placements exist. You never have to build or output the boards themselves — only count them — which opens the door to representations far leaner than an actual grid.

For n = 2 and n = 3 the answer is 0; every other n in range has at least one safe placement.

A queen's attack coverageOne queen at (1, 1) pins down a column, a row, and the two diagonals row − col = 0 and row + col = 2. Each dashed family becomes one entry in an attack set — or one bit in a bitmask.

Example 1:

Input: n = 4

Output: 2

Explanation: Only two boards work on 4×4 — mirror images of each other with column sequences [1, 3, 0, 2] and [2, 0, 3, 1].

Example 2:

Input: n = 1

Output: 1

Explanation: One queen, one square, nothing to attack.

Constraints:

1 ≤ n ≤ 9

Hints:

Any safe board has one queen per row and per column, so candidates are permutations of columns — n! of them, not n² choose n.

Search row by row, tracking attacked columns and both diagonal families (row − col and row + col). Since only the count matters, you never need to materialize a board.

For the fastest version, pack the three attack sets into three bitmasks. free = ~(cols | leftDiag | rightDiag) masked to n bits gives every legal column of the current row at once; peel bits with free & -free. Shifting the diagonal masks by one when descending a row keeps them aligned.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

Input: n = 4

Expected output: 2