N-Queens

The N-Queens problem asks: place n queens on an n × n chessboard so that no two queens share a row, column, or diagonal. It is the canonical example of constraint satisfaction via backtracking — place a queen, check constraints, recurse, remove the queen if the branch fails.

Key Insight: Three Conflict Sets

Because we place exactly one queen per row (top to bottom), rows never conflict. We only need to track:

• Columns — which columns already have a queen.
• Left diagonals — identified by col - row (constant along each diagonal going top-left to bottom-right).
• Right diagonals — identified by col + row (constant along each diagonal going top-right to bottom-left).

Using JavaScript Set objects, all three checks are O(1).

Implementation

function solveNQueens(n) {
  const solutions = [];
  const cols = new Set();
  const diagL = new Set(); // col - row
  const diagR = new Set(); // col + row

  function backtrack(row, board) {
    // Base case: placed a queen in every row
    if (row === n) {
      solutions.push([...board]);
      return;
    }

    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diagL.has(col - row) || diagR.has(col + row)) {
        continue; // this square is under attack — skip it
      }

      // Place queen
      cols.add(col);
      diagL.add(col - row);
      diagR.add(col + row);
      board.push(col);

      backtrack(row + 1, board);

      // Remove queen (backtrack)
      cols.delete(col);
      diagL.delete(col - row);
      diagR.delete(col + row);
      board.pop();
    }
  }

  backtrack(0, []);
  return solutions; // each solution is an array of column indices per row
}

console.log(solveNQueens(4).length); // 2
console.log(solveNQueens(8).length); // 92

Each element of solutions is an array where solution[r] is the column of the queen in row r. Converting to the traditional board string is an optional formatting step.

Why the Diagonal Keys Work

Two squares (r1, c1) and (r2, c2) share a left diagonal when c1 - r1 === c2 - r2, and a right diagonal when c1 + r1 === c2 + r2. Storing the keys col - row and col + row in sets encodes exactly these relationships without needing a 2-D boolean grid.

Complexity

The worst-case time is O(n!) — in the first row we try n columns, in the second at most n-1, and so on. The set-based constraint checks reduce the constant factor significantly compared to a naive board scan, but the fundamental factorial growth remains. N-Queens has no known polynomial-time algorithm and is NP-complete in its generalized decision form.

Up Next

With backtracking mastered, the next section covers comparison-based sorting algorithms — starting with an overview of the full sorting landscape.