Marauder Bot

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

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.

N-Queens