Skip to main content

93. N-Queens II

hardAsked at Snowflake

Count the number of distinct n-queens solutions. Snowflake asks this for pure constraint counting — directly relevant to counting valid plan configurations during planner exploration.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake compiler-team uses this for plan-enumeration counting.
  • LeetCode Discuss (2025-09)— Reported at Snowflake SDE-II screens.

Problem

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other. Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Constraints

  • 1 <= n <= 9

Examples

Example 1

Input
n = 4
Output
2

Example 2

Input
n = 1
Output
1

Approaches

1. Reuse n-queens, count results

Run the n-queens solver, return result.length.

Time
O(n!)
Space
O(n!)
// outline — reuse LC 51 and return count.

Tradeoff: Same complexity, more memory.

2. Bitmask backtracking with counter (optimal)

Same bitmask backtracking but only increment a count.

Time
O(n!)
Space
O(n)
function totalNQueens(n) {
  let count = 0;
  function backtrack(row, cols, diag1, diag2) {
    if (row === n) { count++; return; }
    let available = ((1 << n) - 1) & ~(cols | diag1 | diag2);
    while (available) {
      const bit = available & -available;
      backtrack(row + 1, cols | bit, (diag1 | bit) << 1, (diag2 | bit) >>> 1);
      available &= available - 1;
    }
  }
  backtrack(0, 0, 0, 0);
  return count;
}

Tradeoff: O(n) space (recursion only). The 'tightest' n-queens solution.

Snowflake-specific tips

Snowflake interviewers may follow up with this after LC 51, looking for whether you can strip the board reconstruction. Bonus signal: discuss precomputing values for small n (the famous sequence: 1, 0, 0, 2, 10, 4, 40, 92, 352, ...) and how a precomputed lookup beats any algorithm for n <= 12.

Common mistakes

  • Storing the board even though it's not needed — wastes memory.
  • Forgetting to use the bit-iteration loop pattern (available & -available, available &= available - 1).
  • Using floats for log2 — for n <= 9 it's fine, but bit-position via De Bruijn sequence is safer for larger n.

Follow-up questions

An interviewer at Snowflake may pivot to one of these next:

  • Precompute all answers for n <= 17.
  • Symmetric counting via fundamental solutions.
  • How does Snowflake count valid join plans?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why drop the board storage?

If you only need the count, building strings per solution wastes time and memory. For n = 13 there are 73712 solutions — that's a lot of throwaway strings.

Is there a closed form?

No known closed form. The sequence (OEIS A000170) is computed by exactly this kind of backtracking, sometimes parallelized.

Practice these live with InterviewChamp.AI

Drill N-Queens II and other Snowflake interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →