Frontend Beauty
ESC

Type to search the knowledge base.

N-Queens

Place n queens so none attack — backtracking with column and diagonal masks, return all board layouts.

advanced3 min read
  • dsa
  • backtracking
  • interview
  • Google
  • Meta
  • Amazon
  • Microsoft

The problem

Place n queens on an n × n chessboard so no two share a row, column, or diagonal. Return all distinct solutions as boards of 'Q' and '.'.

Input: n = 4
Output: [
 [".Q..","...Q","Q...","..Q."],
 ["..Q.","Q...","...Q",".Q.."]
]

Mental model: one queen per row. For row r, try each free column; track attacked columns and both diagonal directions.

Brute force

Generate all permutations of column placements (one per row) and filter safe diagonals. Correct but same exponential family; still enumerate. Backtracking prunes earlier.

Optimal: backtracking with sets

Diagonals:

  • diag1 = row - col (or row - col + n as index)
  • diag2 = row + col
function solveNQueens(n: number): string[][] {
  const cols = new Set<number>();
  const diag1 = new Set<number>(); // r - c
  const diag2 = new Set<number>(); // r + c
  const board = Array.from({ length: n }, () => Array(n).fill("."));
  const res: string[][] = [];

  function place(r: number): void {
    if (r === n) {
      res.push(board.map((row) => row.join("")));
      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);
      board[r][c] = "Q";
      place(r + 1);
      board[r][c] = ".";
      cols.delete(c);
      diag1.delete(r - c);
      diag2.delete(r + c);
    }
  }

  place(0);
  return res;
}

Bitmask version for n ≤ 32 is a flex: bits for free columns/diagonals. Sets are clearer in JS interviews.
Time O(n!) roughly — pruned permutations
Space O(n) recursion + O(n²) for solutions storage

Why three constraints

Row is free (we place one per row). Column: classic. Diagonals: same r-c or r+c means same diagonal.

Edge cases

  • n = 1 → [["Q"]]
  • n = 2, n = 3 → no solutions []
  • n = 4 → two solutions
  • Large n blows up — problem usually n ≤ 9

Common bugs

  • Forgetting to backtrack (leave Q on board)
  • Wrong diagonal key (r-c vs c-r)
  • Allowing two queens same column
  • Returning count when asked for boards (LC 52 is N-Queens II)

Interview delivery

  1. One queen per row.
  2. Track cols + two diagonal sets.
  3. Place / recurse / undo.
  4. Complexity factorial-ish.
  5. Offer N-Queens II (count only) as follow-up.

Diagonal numbering

For n=4, cell (r,c):

  • r - c ranges from -(n-1)..(n-1)
  • r + c ranges from 0..2n-2

Sets handle negative keys fine in JS. Arrays need an offset for r-c.

Counting vs listing

N-Queens II asks only for the count — same search, increment instead of deep-copying boards. Mention you can avoid building strings until needed.

Symmetry optimizations

Advanced: only place first-row queens in half and mirror. Optional flex; not required for correctness.

Further reading