Skip to main content

92. N-Queens

hardAsked at Snowflake

Place n queens on an n x n chessboard so none attack each other. Snowflake asks this as the canonical backtracking-with-constraint-bitmask — relevant to constraint solving during query rewrite where multiple non-conflicting predicates must be selected.

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 constraint-propagation discussion.
  • 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 all distinct solutions to the n-queens puzzle. You may return the answer in any order. Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Constraints

  • 1 <= n <= 9

Examples

Example 1

Input
n = 4
Output
[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Example 2

Input
n = 1
Output
[["Q"]]

Approaches

1. Backtracking with set-based validation

Sets for columns, two diagonals. Place row-by-row.

Time
O(n!)
Space
O(n^2)
// outline — sets capture column + two diagonals.

Tradeoff: Works.

2. Backtracking with bitmask (optimal)

Three bitmasks: cols, diag1 (row+col), diag2 (row-col). On each row, valid positions = ~(cols | diag1 | diag2). Pick lowest set bit, recurse.

Time
O(n!)
Space
O(n)
function solveNQueens(n) {
  const result = [];
  const positions = new Array(n);
  function backtrack(row, cols, diag1, diag2) {
    if (row === n) {
      const board = positions.map(c => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1));
      result.push(board);
      return;
    }
    let available = ((1 << n) - 1) & ~(cols | diag1 | diag2);
    while (available) {
      const bit = available & -available;
      const col = Math.log2(bit);
      positions[row] = col;
      backtrack(row + 1, cols | bit, (diag1 | bit) << 1, (diag2 | bit) >>> 1);
      available &= available - 1;
    }
  }
  backtrack(0, 0, 0, 0);
  return result;
}

Tradeoff: Bitmask is the standard fast solution. Diag1 shifts left, diag2 shifts right — both propagate constraints to the next row.

Snowflake-specific tips

Snowflake interviewers want the bitmask version and the diagonal propagation explained. Bonus signal: pivot to constraint propagation in query rewrite — picking non-conflicting predicate pushdowns into a join uses bitmask-style constraint tracking.

Common mistakes

  • Using row+col and row-col as Set keys — works but slower than bitmask.
  • Forgetting that diagonals shift differently for each direction.
  • Computing log2 of a bit instead of using a bit-position lookup.

Follow-up questions

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

  • N-Queens II (LC 52) — count solutions only.
  • Generalize to constraint problems with non-attacking patterns.
  • How does Snowflake's query rewrite resolve conflicting predicates?

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 shift diag1 left and diag2 right?

diag1 = row + col. Moving to the next row increments row by 1, so the diagonal position shifts left by 1. diag2 = row - col; same logic with right shift.

How does this map to query rewrite?

When rewriting a query, the optimizer must choose predicates that don't conflict. Tracking 'used' predicates and their implied conflicts as bitmasks gives O(1) compatibility checks.

Practice these live with InterviewChamp.AI

Drill N-Queens 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 →