N-Queens

A chess queen attacks every square in its row, its column and both of its diagonals. Given an integer n, find every way to put n queens on an n × n board so that no queen attacks another.

Describe each arrangement as a list of n strings, one per row from top to bottom, where "Q" marks a queen and "." an empty square. For example, ".Q.." is a row of a 4 × 4 board with a queen in the second column.

Return all distinct arrangements. The arrangements may be listed in any order (but the rows inside each one must be in top-to-bottom order). Return an empty list if none exist.

Example 1

Example 2

Example 3

Constraints

• 1 <= n <= 9

Pattern Path · Backtracking · problem 127 of 169

Start simple

Try every way to choose n squares out of n² and test each for attacks: C(n², n) boards, astronomically many even for n = 8.

The key idea

The row rule shrinks the search immediately: every row holds exactly one queen, so a board is just a choice of column for each row. Build that choice row by row with backtracking.

At row r, try each column c. The square is safe if no earlier queen shares its column or either diagonal. Diagonals have a neat signature: moving down-right changes row and column by the same amount, so r - c is the same for the whole diagonal; moving up-right keeps r + c fixed. Keeping three sets of used columns, used r - c values and used r + c values makes every check constant time.

If (r, c) is safe, record it, add its three keys to the sets, and recurse to row r + 1. When the recursion returns, remove the keys again so the next column starts from a clean state. Reaching row n means all queens are placed without conflict, so turn the column list into strings and save it.

Pruning unsafe columns early is what makes this practical: whole subtrees of hopeless boards are never explored.

Complexity

• Time: O(n!) placements explored, plus O(n²) to build each answer
• Space: O(n) for the recursion and sets, excluding the output

Python

class Solution:
    def solveNQueens(self, n):
        boards = []
        queen_col = [0] * n          # queen_col[r] = column of the queen in row r
        used_cols = set()
        used_diags = set()           # a down-right diagonal keeps row - col fixed
        used_anti = set()            # an up-right diagonal keeps row + col fixed

        def place(row):
            if row == n:
                boards.append(["." * c + "Q" + "." * (n - c - 1) for c in queen_col])
                return
            for c in range(n):
                if c in used_cols or row - c in used_diags or row + c in used_anti:
                    continue
                queen_col[row] = c
                used_cols.add(c)
                used_diags.add(row - c)
                used_anti.add(row + c)
                place(row + 1)
                used_cols.remove(c)
                used_diags.remove(row - c)
                used_anti.remove(row + c)

        place(0)
        return boards

JavaScript

var solveNQueens = function(n) {
  const boards = [];
  const queenCol = new Array(n).fill(0); // queenCol[r] = column of the queen in row r
  const usedCols = new Set();
  const usedDiags = new Set(); // a down-right diagonal keeps row - col fixed
  const usedAnti = new Set();  // an up-right diagonal keeps row + col fixed

  const place = (row) => {
    if (row === n) {
      boards.push(queenCol.map((c) => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1)));
      return;
    }
    for (let c = 0; c < n; c++) {
      if (usedCols.has(c) || usedDiags.has(row - c) || usedAnti.has(row + c)) continue;
      queenCol[row] = c;
      usedCols.add(c);
      usedDiags.add(row - c);
      usedAnti.add(row + c);
      place(row + 1);
      usedCols.delete(c);
      usedDiags.delete(row - c);
      usedAnti.delete(row + c);
    }
  };

  place(0);
  return boards;
};

What the interviewer is checking

This is a classic test of backtracking structure (choose, recurse, undo) and of spotting the row - col / row + col diagonal trick that turns the safety check into O(1).

Mistakes to avoid

• Forgetting to remove a queen's column and diagonals from the sets after the recursive call.
• Mixing up the two diagonal keys, or checking only one diagonal direction.
• Saving a reference to a mutable board that later changes, instead of building fresh strings for each answer.
• Assuming every n has a solution; 2 and 3 have none.

Follow-ups to expect

• How would you only count the solutions? (Same search, increment a counter.)
• Can bitmasks speed it up? (Free squares = ~(cols | d1 | d2).)
• How would you skip mirror-image solutions? (Restrict first-row column to left half.)

In real software

Scheduling and frequency-assignment tools place items so that no two conflict along several dimensions at once, using the same prune-early backtracking search.

Practice next