Skip to main content

91. N-Queens

hardAsked at Plaid

Place N queens on an NxN board such that no two attack each other; return all solutions. Plaid asks this as a backtracking classic before harder constraint-satisfaction problems.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE III backtracking hard.
  • LeetCode Discuss (2026)— Plaid constraint problem.

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.

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. Enumerate all placements

Try every combination of n positions across n rows.

Time
O(n^n)
Space
O(n)
// Brute. Mention only.

Tradeoff: TLE.

2. Backtracking with three sets

Place queens row by row. Track used cols, diagonals (r-c), anti-diagonals (r+c). On placement, add to all three sets; backtrack removes.

Time
O(n!)
Space
O(n)
function solveNQueens(n) {
  const out = [];
  const cols = new Set(), diag = new Set(), anti = new Set();
  const pos = [];
  function bt(r) {
    if (r === n) {
      out.push(pos.map(c => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1)));
      return;
    }
    for (let c = 0; c < n; c++) {
      if (cols.has(c) || diag.has(r - c) || anti.has(r + c)) continue;
      cols.add(c); diag.add(r - c); anti.add(r + c);
      pos.push(c);
      bt(r + 1);
      pos.pop();
      cols.delete(c); diag.delete(r - c); anti.delete(r + c);
    }
  }
  bt(0);
  return out;
}

Tradeoff: n! worst case but heavy pruning. Three sets give O(1) conflict checks.

Plaid-specific tips

Plaid grades this on the three-set representation (cols, diag, anti-diag). Bonus signal: explain why r-c is the main diagonal and r+c is the anti-diagonal. Connect to multi-constraint scheduling where each shift has row, column, and diagonal constraints (time, resource, region).

Common mistakes

  • Using a 2D grid to check conflicts — O(n) per check instead of O(1).
  • Forgetting to backtrack-remove from all three sets.
  • Off-by-one on the diagonal formulas.

Follow-up questions

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

  • N-Queens II (LC 52) — count solutions only.
  • Bit-mask variant — even faster.
  • Generalized constraint satisfaction (CSP).

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 r-c and r+c?

Two queens on the same main diagonal have equal r-c. Two on the same anti-diagonal have equal r+c. Both are invariants.

Bitmask vs sets?

Bitmask is faster (single machine word) for n <= 30. Sets are clearer to write. For Plaid's n <= 9, sets are fine.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →