hard

N-Queens

Place queens on a chessboard so that no two queens attack each other.

1. Define the problem

N-Queens

The n-queens puzzle is the problem of placing n queens on an n x n chessboard so that no two queens attack each other — meaning no two share a row, a column, or a diagonal . Given an integer n, return all distinct solutions, each represented as a board where "Q" marks a queen and "." marks an empty space. Use backtracking that places one queen per row: try every column in the current row, and prune any column already under attack from a queen placed in an earlier row — undoing the placement after each recursive call to free that column and its diagonals back up.

Constraints

  • 1 ≤ n ≤ 9

Example

Inputn = 4
Output[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Explanation Exactly two distinct arrangements place 4 non-attacking queens on a 4x4 board.

2. Know the words first

In plain terms

Diagonal
A line of cells running at a 45° angle — two cells share a diagonal whenever the difference, or the sum, of their row and column indices is equal.
3. Visualize the solution

Place one queen per row, prune any column already under attack

Place one queen per row, prune any column already under attack
Statustry

Row 0: place a queen in column 1 (no earlier queens to conflict with).

What happens in this step

row 0, col 1 — first queen, board empty
cols = {}    diag1 (row-col) = {}    diag2 (row+col) = {}

No sets have any entries yet, so every column is open. Column 1 is chosen and placed: cols={1}, diag1={-1}, diag2={1}. path=[1], recurse into row 1.
Step 1 of 5

Steps to visualize

  1. Move to the next row and try each column in turn.
  2. Skip a column immediately if it — or either of its diagonals — is already occupied by an earlier queen: that branch is pruned before it even starts.
  3. Place the queen, recurse into the next row, then undo the placement to free the column and diagonals back up.
  4. Once every row has a queen, record the board as one solution.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Place one queen per row, prune any column already under attack
Statustry

Row 0: place a queen in column 1 (no earlier queens to conflict with).

What happens in this step

row 0, col 1 — first queen, board empty
cols = {}    diag1 (row-col) = {}    diag2 (row+col) = {}

No sets have any entries yet, so every column is open. Column 1 is chosen and placed: cols={1}, diag1={-1}, diag2={1}. path=[1], recurse into row 1.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function solveNQueens(n) {
  const result = [];
  const cols = new Set();
  const diag1 = new Set(); // row - col
  const diag2 = new Set(); // row + col
  const positions = [];

  function backtrack(row) {
    if (row === n) {
      const board = positions.map((col) => '.'.repeat(col) + 'Q' + '.'.repeat(n - col - 1));
      result.push(board);
      return;
    }

    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) {
        continue; // prune — this column is already under attack
      }

      cols.add(col);
      diag1.add(row - col);
      diag2.add(row + col);
      positions.push(col);

      backtrack(row + 1);

      cols.delete(col);
      diag1.delete(row - col);
      diag2.delete(row + col);
      positions.pop();
    }
  }

  backtrack(0);
  return result;
}
Time
O(n!)
Space
O(n)
6. Test cases

Test cases

InputExpectedCovers
n = 4[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]example from the docstring, the two 4x4 solutions
n = 1[["Q"]]smallest valid input, a single queen with no conflicts possible
n = 2[]a 2x2 board has no arrangement of two non-attacking queens
n = 3[]a 3x3 board also has no valid arrangement

Keep reading