Skip to main content

97. N-Queens

hardAsked at Reddit

Place n queens on an n×n board so none attack each other. Reddit uses this backtracking classic to test constraint-encoded DFS — the same shape they use when scheduling non-conflicting moderator-action sequences across overlapping subreddits.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit on-site backtracking favorite.

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 enumerate placements

Try all C(n^2, n) placements.

Time
huge
Space
O(n^2)
// Anti-pattern: too slow.

Tradeoff: TLE.

2. Backtracking row by row (optimal)

Place one queen per row. Track used columns, diagonals (col-row), anti-diagonals (col+row) in sets.

Time
O(n!)
Space
O(n)
function solveNQueens(n) {
  const out = [];
  const cols = new Set(), diag1 = new Set(), diag2 = new Set();
  const queens = new Array(n).fill(-1);
  function backtrack(row) {
    if (row === n) {
      out.push(queens.map(c => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1)));
      return;
    }
    for (let c = 0; c < n; c++) {
      if (cols.has(c) || diag1.has(row - c) || diag2.has(row + c)) continue;
      queens[row] = c;
      cols.add(c); diag1.add(row - c); diag2.add(row + c);
      backtrack(row + 1);
      cols.delete(c); diag1.delete(row - c); diag2.delete(row + c);
    }
  }
  backtrack(0);
  return out;
}

Tradeoff: n! upper bound but pruning by columns + diagonals cuts dramatically.

Reddit-specific tips

Reddit interviewers grade on the diagonal tracking. Bonus signal: explain why row - col and row + col uniquely identify the two diagonals through any cell.

Common mistakes

  • Tracking only columns and forgetting diagonals.
  • Confusing the two diagonals (one uses subtraction, one addition).
  • Forgetting to restore state on backtrack.

Follow-up questions

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

  • N-Queens II (LC 52) — just the count.
  • Sudoku solver (LC 37).
  • Bitmask version for n up to 32.

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 does row - col identify a diagonal?

Cells on the same '/' diagonal have constant row + col. Cells on the same '\' diagonal have constant row - col.

Bitmask speedup?

Use bits for cols, diag1, diag2. Bitwise tests replace set lookups — much faster.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →