# N-Queens

> How to solve N-Queens: place one queen per row via backtracking, pruning columns and diagonals already under attack.

- Difficulty: Hard
- Category: Backtracking
- Topics: Array, Backtracking
- Published 2026-08-21

## Problem

Place n chess queens on an n-by-n board so that no two attack each other, meaning no two share a row, a column, or a diagonal. Return every distinct arrangement, describing each as the column position of the queen placed in every row.

**Example.** For `n = 4`, there are exactly two valid arrangements: one with queens at columns `[1, 3, 0, 2]` (row 0's queen in column 1, row 1's in column 3, and so on), and its mirror image `[2, 0, 3, 1]`.

## Key idea

Since no two queens can share a row, exactly one queen belongs in each row, reducing the problem to choosing a column for each row in turn, while ruling out choices that conflict with queens already placed.

Process rows top to bottom. At each row, try every column; a column is legal if no previously placed queen shares it, and if none sits on either diagonal running through this cell. The two diagonals a cell lies on are identified in constant time as `row - column` and `row + column`, both constant along a diagonal. Track used columns and the two diagonal sets, place a queen once a column checks out, recurse to the next row, and undo the placement before trying the next column. Filling all n rows without conflict yields one complete arrangement to record.

## Solution

```typescript
function solveNQueens(n: number): number[][] {
  const result: number[][] = [];
  const columns: number[] = [];
  const usedColumns = new Set<number>();
  const usedDiagonals1 = new Set<number>();
  const usedDiagonals2 = new Set<number>();

  function backtrack(row: number): void {
    if (row === n) {
      result.push([...columns]);
      return;
    }

    for (let col = 0; col < n; col++) {
      // row - col is constant along one diagonal, row + col along the other.
      const diagonal1 = row - col;
      const diagonal2 = row + col;
      // Skip columns already attacked by column or either diagonal.
      if (usedColumns.has(col) || usedDiagonals1.has(diagonal1) || usedDiagonals2.has(diagonal2)) {
        continue;
      }

      usedColumns.add(col);
      usedDiagonals1.add(diagonal1);
      usedDiagonals2.add(diagonal2);
      columns.push(col);

      backtrack(row + 1);

      // Undo this placement before trying the next column.
      columns.pop();
      usedColumns.delete(col);
      usedDiagonals1.delete(diagonal1);
      usedDiagonals2.delete(diagonal2);
    }
  }

  backtrack(0);
  return result;
}
```

## Complexity

- **Time:** bounded by the number of column arrangements explored, worst case O(n!), sharply reduced by column and diagonal pruning at every row.
- **Space:** O(n). The row-by-row placement plus the tracking structures.

## Watch out for

- Track both diagonal directions separately (`row - column` and `row + column`); checking only one misses half of the attacking diagonals.
- Clear the column and diagonal markers when backtracking out of a placement, or later branches will see phantom conflicts.

## Pattern

This is constrained row-by-row backtracking, where the one-queen-per-row structure collapses placement into a single per-row choice validated against running constraint sets. The same idea, choosing one element per row and validating against cumulative constraints, applies to related constraint-satisfaction placement puzzles.

---

Canonical URL: https://www.marauderbot.com/questions/n-queens
