N-Queens (Backtracking)

How it works, step by step

1. 1

   Work row by row. Each row must hold exactly one queen, so a partial answer is just a list of columns - one per filled row.

2. 2

   In the current row, scan squares left to right. For each square, check the queens above: does any share this column or a diagonal?

3. 3

   If the square is attacked, skip it. This is pruning: fail now, before wasting any work on the rows below.

4. 4

   If the square is safe, place a queen there and move down to the next row.

5. 5

   If no square in a row is safe, that branch is dead. Backtrack: remove the queen in the row above and keep scanning from the square after it. This undo step is what makes it backtracking.

6. 6

   When the last row gets a queen, you have a solution. Return it - or record it and keep searching if you want all of them.

The code, in JavaScript

function solveNQueens(n) {
  const queens = [];   // queens[r] = column of the queen in row r

  function isSafe(row, col) {
    for (let r = 0; r < row; r++) {
      const c = queens[r];
      // same column, or same diagonal (row gap === column gap)
      if (c === col || Math.abs(c - col) === row - r) return false;
    }
    return true;
  }

  function fillRow(row) {
    if (row === n) return true;            // every row has a queen - done
    for (let col = 0; col < n; col++) {
      if (!isSafe(row, col)) continue;     // prune: fail before recursing
      queens.push(col);                    // try this square
      if (fillRow(row + 1)) return true;   // solved below? bubble up
      queens.pop();                        // UNDO - the heart of backtracking
    }
    return false;                          // dead end: nothing in this row worked
  }

  return fillRow(0) ? queens : null;
}

solveNQueens(6);   // → [1, 3, 5, 0, 2, 4]  (row 0's queen in column 1, ...)
solveNQueens(3);   // → null - a 3x3 board has no solution

Dry run: 6 queens on a 6x6 board, first solution

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

• Forgetting the UNDO after the recursive call is THE backtracking bug. The queen (or the Set entries) leaks into sibling branches, and the search misses valid answers in ways that are miserable to debug. Every add needs a matching delete on the same path.
• The diagonal trick trips everyone once: row - col is constant on "\" diagonals, row + col on "/" diagonals. Mixing them up passes small tests and fails later - draw the two little grids in a comment and check one square by hand.
• Prune before recursing, not after. Checking safety per square kills bad branches at depth 1; generating full boards and validating them at the end does n^n work. On 8x8 that is the difference between milliseconds and hours.
• N = 2 and N = 3 have NO solutions. If your function returns undefined, an empty array, or the unchanged input there, callers will crash - decide on null (or an empty list for "all solutions") and test it.

N-Queens (Backtracking) vs. its closest relatives