N-Queens

Examples

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

There are exactly two ways to place 4 non-attacking queens on a 4x4 board. In the first, the queens sit at row 0 col 1, row 1 col 3, row 2 col 0, and row 3 col 2.

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

A single queen on a 1x1 board never conflicts with anything.

Constraints

• 1 <= n <= 9

Approach

Since no two queens can ever share a row, you can decide the placement one row at a time: for row 0, choose a column; for row 1, choose a column that doesn't conflict with row 0's queen; and so on. Once every row has a queen placed without conflicts, you have one complete, valid solution.

A straightforward way to check "does this column conflict with an earlier queen" is to look back at every queen already placed in previous rows and compare columns and diagonals directly - simple to write, but it re-scans all previously placed queens on every single attempt.

A faster way keeps three running trackers as you go: which columns already have a queen, and which of the two diagonal directions already have a queen (a cell's "diagonal identity" in one direction is row minus column, and in the other direction it's row plus column - two cells on the same diagonal always share one of these two values). Checking a candidate column against these trackers is then a single lookup instead of a scan, and un-placing a queen is just removing its column and diagonals from the trackers again before trying the next column.

Solutions

Backtracking — Scan Previously Placed Queens

Place queens row by row. For each row, try every column; before committing, check every queen already placed in earlier rows to make sure none of them shares this column or either diagonal. If a column is safe, place the queen there, recurse into the next row, then remove it and try the next column.

function solveNQueens(n) {
  const result = [];
  const queenCol = new Array(n).fill(-1); // queenCol[row] = column of the queen in that row

  function isSafe(row, col) {
    for (let prevRow = 0; prevRow < row; prevRow++) {
      const prevCol = queenCol[prevRow];
      const sameCol = prevCol === col;
      const sameDiagonal = Math.abs(prevRow - row) === Math.abs(prevCol - col);
      if (sameCol || sameDiagonal) return false;
    }
    return true;
  }

  function buildBoard() {
    return queenCol.map((col) => ".".repeat(col) + "Q" + ".".repeat(n - col - 1));
  }

  function backtrack(row) {
    if (row === n) {
      result.push(buildBoard());
      return;
    }

    for (let col = 0; col < n; col++) {
      if (isSafe(row, col)) {
        queenCol[row] = col;
        backtrack(row + 1);
        queenCol[row] = -1; // undo
      }
    }
  }

  backtrack(0);
  return result;
}

Time: O(n! * n) - roughly n! branching once pruning kicks in, times O(n) per safety scan · Space: O(n) for the queenCol array and recursion depth (output is separate)

Optimal — Track Columns and Diagonals with Sets

Instead of re-scanning earlier queens on every check, maintain three sets as you go: used columns, used "row minus column" diagonals, and used "row plus column" diagonals. Placing or removing a queen just adds or deletes one entry from each of the three sets, and checking whether a column is safe becomes three constant-time lookups instead of a scan back through every earlier row.

function solveNQueens(n) {
  const result = [];
  const queenCol = new Array(n).fill(-1);
  const usedCols = new Set();
  const usedDiag1 = new Set(); // row - col
  const usedDiag2 = new Set(); // row + col

  function buildBoard() {
    return queenCol.map((col) => ".".repeat(col) + "Q" + ".".repeat(n - col - 1));
  }

  function backtrack(row) {
    if (row === n) {
      result.push(buildBoard());
      return;
    }

    for (let col = 0; col < n; col++) {
      const d1 = row - col;
      const d2 = row + col;
      if (usedCols.has(col) || usedDiag1.has(d1) || usedDiag2.has(d2)) continue;

      queenCol[row] = col;
      usedCols.add(col);
      usedDiag1.add(d1);
      usedDiag2.add(d2);

      backtrack(row + 1);

      usedCols.delete(col);
      usedDiag1.delete(d1);
      usedDiag2.delete(d2);
    }
  }

  backtrack(0);
  return result;
}

Time: O(n!) - each placement check is now O(1) instead of O(n) · Space: O(n) for the tracking sets and recursion depth (output is separate)