Skip to main content

91. N-Queens

hardAsked at Salesforce

Place n queens on an n x n chessboard so no two attack each other; return all distinct solutions. Salesforce uses this as the canonical hard backtracking problem.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses constraint-satisfaction patterns in their resource allocation.
  • Blind (2025)— Salesforce hard onsite stretch.

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. Brute force place all

Try all n! placements; check validity at the end.

Time
O(n!)
Space
O(n)
// Too slow without pruning.

Tradeoff: Salesforce wants pruning.

2. Backtracking with column/diagonal sets

Place row by row. Track three sets: occupied columns, anti-diagonals (r+c), main-diagonals (r-c).

Time
O(n!) with strong pruning
Space
O(n)
function solveNQueens(n) {
  const result = [];
  const cols = new Set(), pos = new Set(), neg = new Set();
  const board = Array.from({ length: n }, () => new Array(n).fill('.'));
  function dfs(r) {
    if (r === n) { result.push(board.map(row => row.join(''))); return; }
    for (let c = 0; c < n; c++) {
      if (cols.has(c) || pos.has(r + c) || neg.has(r - c)) continue;
      cols.add(c); pos.add(r + c); neg.add(r - c);
      board[r][c] = 'Q';
      dfs(r + 1);
      cols.delete(c); pos.delete(r + c); neg.delete(r - c);
      board[r][c] = '.';
    }
  }
  dfs(0);
  return result;
}

Tradeoff: Three sets give O(1) conflict-check. Salesforce's preferred answer.

Salesforce-specific tips

Salesforce uses constraint-satisfaction patterns in their resource allocation (e.g., assigning service appointments to technicians under time/skill constraints). They grade on the diagonal-tracking trick: r+c for anti-diagonal (slash), r-c for main diagonal (backslash). Bonus signal: mention that these sets allow O(1) conflict checks vs O(n) row scan.

Common mistakes

  • Tracking only columns — misses diagonal conflicts.
  • Using a 2D grid for diagonal lookup — wastes O(n^2) when two sets suffice.
  • Forgetting to restore state on backtrack.

Follow-up questions

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

  • N-Queens II (LC 52) — count solutions only.
  • Sudoku Solver (LC 37).
  • Symmetry pruning to halve the search.

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 for diagonals?

All cells on the same anti-diagonal have constant r+c. All cells on the same main diagonal have constant r-c. These give cheap conflict checks.

Could I use symmetry to prune?

Yes — the chessboard has reflection/rotation symmetries. Only iterating the first row's left half and reflecting captures all solutions. Useful but not required.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →