Skip to main content

99. N-Queens

hardAsked at Datadog

Place N queens on an N x N board such that none attack each other. Datadog uses this as the canonical backtracking + constraint encoding question — same shape as multi-dim CSP they use for capacity placement.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite hard.

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 all C(n^2, n); check each.

Time
horrendous
Space
O(n)
// Pure enumeration. Never ship.

Tradeoff: Combinatorial explosion.

2. Backtracking row-by-row with three sets (optimal)

Place one queen per row. Track used columns, used (r+c) anti-diagonals, used (r-c) diagonals.

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

Tradeoff: O(1) per constraint check via Set. Datadog-canonical backtracking + multi-dim constraint encoding.

Datadog-specific tips

Datadog grades on the diagonal encoding: r+c uniquely identifies an anti-diagonal; r-c uniquely identifies a main diagonal. Articulate this BEFORE coding. The three-Set check is the same shape as their multi-dim resource conflict check.

Common mistakes

  • Encoding only column conflicts — misses diagonals.
  • Using O(n^2) Sets — O(n) is enough (one per dimension).
  • Forgetting to unmark on backtrack — corrupts state.

Follow-up questions

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

  • N-Queens II (LC 52) — count only.
  • Datadog-style: multi-dim resource placement.
  • Sudoku Solver (LC 37) — similar CSP shape.

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 an anti-diagonal share r+c; main-diagonal share r-c. So one Set per dimension tracks all conflicts.

Why row-by-row?

One queen per row by construction — no row conflict possible. Reduces the search space dramatically.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →