The N-Queens Problem

Place eight queens on a chessboard so that no two attack each other. A queen covers her whole row, her whole column and both diagonals, so this is harder than it sounds and easier than it looks.

The puzzle is not new. The chess composer Max Bezzel published it in 1848, and Franz Nauck published the first solutions in 1850. Gauss worked on it too. It survives as a teaching problem because the search is small enough to watch and the pruning is dramatic enough to feel.

How big is the naive search?

Choosing 8 squares out of 64 gives 64 choose 8, which is 4,426,165,368 arrangements. Testing all of them is possible and pointless.

Two observations collapse that number, and neither is an algorithm. They are reformulations, which is usually where the real speedup in a backtracking problem comes from.

From four billion to a couple of thousand, and only the last row is backtracking. The first two are just noticing what the constraints already told you.

Try it by hand first

Switch the widget to "Place them yourself" and try to solve the 6 by 6 board without help. Nothing stops you putting two queens in one row, and it is worth doing that once to see the tool report it.

Then switch to "Watch it solve" and step through. Red squares are attacked by a queen already placed. A square marked with a cross is one the solver considered and rejected before building anything underneath it.

The moment to watch for is a row where every column is attacked. The solver has nothing to try, so it returns, lifts the queen from the row above, and continues from there. That is the backtrack, and on a 6 by 6 board it happens constantly.

Try n = 4 as well. It has only two solutions and they are mirror images, so the whole search is short enough to follow end to end without losing your place.

Solution counts

The number of solutions does not grow smoothly, which surprises people expecting something tidy.

Six has fewer solutions than five, which is a good reminder that these counts come from the structure of the board rather than from any formula worth memorising. There is no known closed form. The values above are from Wikipedia's eight queens puzzle article, which also covers the history and the symmetry classes.

Checking diagonals without a loop

The naive conflict test walks every previously placed queen. It is O(row) per check, which is fine, and there is a neater way that is O(1).

Two squares are on the same descending diagonal exactly when row - col matches, and on the same ascending diagonal when row + col matches. So three sets, one for columns and one for each diagonal direction, answer the question immediately.

Add n - 1 to the row - col value if you want to index an array rather than use a hash set. That is the usual competitive-programming form.

In code

function solveNQueens(n) {
  const solutions = [];
  const queens = [];                 // queens[row] = column
  const cols = new Set();
  const diag = new Set();            // row - col
  const anti = new Set();            // row + col

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

    for (let col = 0; col < n; col++) {
      // O(1) conflict test, no loop over placed queens.
      if (cols.has(col) || diag.has(row - col) || anti.has(row + col)) continue;

      queens.push(col);                                     // choose
      cols.add(col); diag.add(row - col); anti.add(row + col);

      backtrack(row + 1);                                   // explore

      queens.pop();                                         // un-choose
      cols.delete(col); diag.delete(row - col); anti.delete(row + col);
    }
  }

  backtrack(0);
  return solutions;
}

// solveNQueens(8).length -> 92

How far this scales

Counting solutions stays feasible into the high twenties with good pruning and bitmask representations, and stops being feasible shortly after. There is no polynomial algorithm for counting them.

Finding a single solution is a different question, and much easier: there are direct constructions that place n non-attacking queens without any search at all. If a problem only needs one arrangement, searching for it is the wrong tool.

For the state of the art on the search side, Donald Knuth's Dancing Links paper is the standard reference. It reframes problems like this as exact cover and uses reversible operations on doubly linked lists to make the undo step nearly free, and the paper reports results for n-queens up to n = 18.

Check yourself