Skip to main content

51. N-Queens

hardAsked at HP

HP's enterprise scheduling and resource-allocation systems assign non-conflicting resources across dimensions — analogous to placing non-attacking queens on a chessboard. N-Queens is the canonical constraint-satisfaction problem HP uses to test backtracking discipline and pruning intuition in candidates for algorithm-heavy roles.

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

Source citations

Public interview reports confirming this problem appears in HP loops.

  • Glassdoor (2025-Q4)— HP senior SWE onsite rounds occasionally include N-Queens as a backtracking showcase problem in later rounds.
  • Blind (2025-09)— HP interview prep threads mention N-Queens as a hard constraint-satisfaction problem for algorithm-focused engineering roles at HP.

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.."]]

Explanation: Two distinct solutions exist for 4-queens.

Example 2

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

Explanation: A single queen on a 1×1 board is trivially a solution.

Approaches

1. Backtracking with set-based conflict detection

Place queens one row at a time. Track occupied columns, and both diagonal directions with sets. Backtrack when a conflict is detected. Build the board string only when a full solution is found.

Time
O(n!) — backtracking with pruning
Space
O(n)
function solveNQueens(n) {
  const results = [];
  const cols = new Set();
  const diag1 = new Set(); // row - col
  const diag2 = new Set(); // row + col
  const board = Array.from({ length: n }, () => Array(n).fill('.'));

  function backtrack(row) {
    if (row === n) {
      results.push(board.map(r => r.join('')));
      return;
    }
    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue;
      // Place queen
      cols.add(col); diag1.add(row - col); diag2.add(row + col);
      board[row][col] = 'Q';
      backtrack(row + 1);
      // Remove queen (backtrack)
      cols.delete(col); diag1.delete(row - col); diag2.delete(row + col);
      board[row][col] = '.';
    }
  }

  backtrack(0);
  return results;
}

Tradeoff: O(1) conflict lookup per cell using three sets. Generating the board only at leaf nodes avoids building invalid intermediate strings. This is the clean, production-quality backtracking solution.

HP-specific tips

HP interviewers want you to state the pruning invariants upfront: 'No two queens share a column, a / diagonal (row+col constant), or a \ diagonal (row-col constant).' Using three hash sets for O(1) lookup is the right optimization — avoid O(n) row/column scans. Since n ≤ 9, bit-masking is another valid approach worth mentioning if the interviewer pushes for micro-optimizations. Build the board representation only when a complete valid configuration is found — not at every recursive step.

Common mistakes

  • Checking columns and rows with O(n) scans instead of O(1) set lookups.
  • Using the wrong diagonal invariant — row-col for one diagonal and row+col for the other. Swap them and you'll miss conflicts.
  • Building the board string at every recursive level instead of only at the leaf (row === n).
  • Forgetting to remove the queen from all three sets during backtracking — partial state carries over to sibling branches.

Follow-up questions

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

  • N-Queens II (LC 52) — return the count of distinct solutions, not the boards themselves.
  • How would you check if a given n-queens placement is valid without solving the puzzle?
  • What is the time complexity precisely, and why is it bounded by n! rather than n^n?

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 use row - col and row + col for diagonals?

Along a '\' diagonal, row - col is constant for all cells. Along a '/' diagonal, row + col is constant. These invariants let you check diagonal conflicts in O(1) with a set.

Why is the time complexity O(n!) and not O(n^n)?

We place exactly one queen per row and prune any column already used. Row 0 has n choices, row 1 has at most n-1 remaining columns, etc. This gives O(n * (n-1) * ... * 1) = O(n!).

What is the maximum number of solutions for n=9?

There are 352 distinct solutions for n=9 — a manageable number even for an O(n!) traversal.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →