N-Queens II

N-Queens II

What is this problem about?

The N-Queens II problem is the counting variant of the classic N-Queens puzzle. Instead of returning all valid board configurations, you simply count how many distinct solutions exist for placing n non-attacking queens on an n×n chessboard. This N-Queens II coding problem focuses on efficient backtracking with constraint tracking, minimizing memory by not storing the actual boards.

Why is this asked in interviews?

Zenefits, Microsoft, Meta, Amazon, Google, and Bloomberg ask this to test pure backtracking optimization. Since you only need a count (not the configurations), candidates can focus entirely on pruning efficiency. The backtracking interview pattern is perfectly demonstrated, and the problem reveals whether candidates can recognize when to optimize by dropping the solution storage overhead.

Algorithmic pattern used

Backtracking with bitmask optimization. Instead of storing board states, track three integer bitmasks: cols (occupied columns), diag1 (occupied left-diagonals, row-col), diag2 (occupied right-diagonals, row+col). For each row, try each valid column using bitwise operations to check all three constraints simultaneously. Increment counter when all n queens are placed.

Example explanation

n=4. Row 0: try col 0 → constraints updated. Row 1: cols 0 blocked, try col 2. Row 2: blocked options, try col... After exhaustive backtracking, find exactly 2 valid configurations for n=4.

The bitmask approach: valid positions = ~(cols | diag1 | diag2) & all_ones_mask. Iterate set bits for valid column choices.

Common mistakes candidates make

• Storing board configurations (unnecessary for a count-only problem).
• Not using bitmasks — tracking column/diagonal sets separately as arrays is slower.
• Off-by-one: bitmask shifts depend on n and direction.
• Not masking to n bits (extra high bits remain set and falsely block positions).

Interview preparation tip

N-Queens II is the performance-optimized variant of N-Queens. After solving N-Queens I with sets, convert to bitmask operations for N-Queens II. Bitmask operations reduce per-step work from O(n) set lookups to O(1). Practice counting backtracking variants — they require the same structure but without result collection overhead. This skill generalizes to counting valid sudoku fills, combinations with constraints, and partition counting.