The N-Queens Problem

Eight queens on a chessboard, none of them attacking another. A queen covers her whole row, her whole column, and both diagonals, so fitting eight of them onto 64 squares is a tight squeeze. There are exactly 92 solutions, and this problem is the standard demonstration of backtracking for a good reason: the naive approach is hopeless, and one good idea plus one cheap check makes it instant.

Choosing what a decision is

Before writing any code, the framing decides almost everything. The obvious statement of the problem is "choose 8 squares out of 64," which gives you about 4.4 billion arrangements.

Now use something you actually know about the answer. Two queens in the same row always attack each other, so any valid solution has exactly one queen per row. That's not a heuristic, it's a fact about every solution, so restricting to it loses nothing.

Reframed, the question becomes "which column does each row's queen go in," which is 8 choices repeated 8 times: 16.7 million. Nearly three hundred times smaller, and it came from thinking rather than from code.

This generalizes way past eight queens. Before reaching for a faster search, it's worth asking whether the representation itself can be made smaller, since a better encoding usually beats a better search.

Checking a square quickly

With one queen per row, rows take care of themselves, columns are easy since you just keep a set of used columns, and diagonals are the part that looks fiddly but actually isn't.

Two squares are on the same "\\" diagonal exactly when row - col matches, and on the same "/" diagonal exactly when row + col matches. So each diagonal has a single number naming it, and checking one is just a set lookup, same as the column check.

row - col is constant down a "\" diagonal      row + col is constant down a "/" diagonal

     c0 c1 c2 c3                                   c0 c1 c2 c3
 r0   0  -1 -2 -3                              r0   0   1  2  3
 r1   1   0 -1 -2                              r1   1   2  3  4
 r2   2   1  0 -1                              r2   2   3  4  5
 r3   3   2  1  0                              r3   3   4  5  6

Three sets, three constant-time lookups, and a square is either safe or it isn't. Without this you'd scan the placed queens every time, which is fine at n = 8 and starts to hurt as the board grows.

The first stretch, written out

Below is the search running on a 4 by 4 board. Use Step rather than Play, so each placement and backtrack gets its own moment instead of blurring past. Columns are lettered a to d, rows numbered 1 to 4, filling one row at a time from the top.

Watch what happens once queens are sitting on a1 and c2. Every column in row 3 is attacked, so the loop finishes having placed nothing and the call just returns. That return is the backtrack. There's no special instruction for it, just a function running out of columns to try.

Keep watching after that, and the search eventually abandons row 1 entirely: once every arrangement starting with a queen on a1 has failed, it concludes nothing beginning there can work, and moves on to b1. Twenty tries proved a single fact about the first row, and every one of them was necessary. Skip any of it and you risk throwing away a real solution along with the dead ends.

It reaches the first solution only after backing all the way out of the a1 branch and restarting from b1. Brute force over all 4-square placements would test 1,820 arrangements just to get there.

Drive it

Change the board size and watch the node counter. Between 6 and 8 the work grows fast, and the gap between the pruned search and the raw arrangement count grows even faster.

The implementation

function solveNQueens(n) {
  const solutions = [];
  const queenInRow = [];              // queenInRow[r] = the column used

  const usedCols  = new Set();
  const usedDown  = new Set();        // row - col
  const usedUp    = new Set();        // row + col

  function place(row) {
    if (row === n) {
      solutions.push([...queenInRow]);
      return;
    }

    for (let col = 0; col < n; col++) {
      const down = row - col, up = row + col;
      if (usedCols.has(col) || usedDown.has(down) || usedUp.has(up)) continue;

      usedCols.add(col); usedDown.add(down); usedUp.add(up);
      queenInRow.push(col);

      place(row + 1);

      queenInRow.pop();
      usedCols.delete(col); usedDown.delete(down); usedUp.delete(up);
    }
  }

  place(0);
  return solutions;
}

Compare it against the template. The stopping test is row === n, the choices are the n columns of the current row, the prune is the three-set lookup, and the un-choose removes exactly what the choose added. Four pieces of state go up, four come back down.

How the numbers grow

The solution counts are worth having in front of you, partly as a check on your own implementation.

The dip at 6 is real, and it surprises people. There's no simple formula for these numbers, which is part of why the problem stayed interesting: for larger boards, you count the solutions by running a search rather than by evaluating an expression.

If your solver returns 88 rather than 92 on the 8 by 8 board, the search isn't broken. A prune is rejecting placements that were actually legal, and the diagonal arithmetic is the first place to look.

Where it goes wrong

Getting a diagonal formula backwards. Using row + col for both diagonals is the classic slip. It runs, it produces fewer solutions than it should, and nothing looks wrong at a glance. Check against the table above.

Removing only some of the state on the way out. Four things were added, and all four have to be removed. Miss one and you leave a phantom queen blocking squares in sibling branches.

Checking safety after placing rather than before. It works, and it wastes the prune, since you build the state and then immediately tear it back down.

Storing a reference to the working board is the same copying bug as everywhere else in this section, so take a snapshot when you record a solution.

Check yourself