How Many Solutions Does the N-Queens Problem Have?

A walkthrough of a backtracking algorithm for solving the n-queens problem using JavaScript.

What is the n-queens problem?

The n-queens problem was first presented as the “eight queens problem” by Max Bezzel in 1848. The puzzle asks that eight queens be placed on an 8×8 chessboard such that they are unable to attack each other. Over time, this problem developed into the more general n-queens problem, which asks for the placement of n non-attacking queens on an n×n chessboard.

A solution to the eight queens problem. Source: Yue Guo

As seen in the above image, a solution to the n-queens problem requires that each queen’s position is not horizontally, vertically, or diagonally away from that of another queen. A corollary of this fact is that no two queens can be placed in the same row, column, or diagonal — a characteristic which we will take advantage of while constructing our solution algorithm.

Finding the number of solutions for a specific n

The goal of this section is to create a function (countNQueensSolutions) that counts the number of possible solutions to the n-queens problem for a specific integer n. The beginning of the code is shown below:

function countNQueensSolutions(n) {
  if (n === 0) {
    return 1;
  }
  let solutionCount = 0;
  let emptyBoard = new Board({ n });

First off, we check whether the argument is 0. If it is, we return 1, which is the number of solutions to the 0-queens problem. The reason we do so is because we want to search for solutions on a two-dimensional, n×n “chessboard.” However, it doesn’t make much sense to deal with a 0×0 board (and indeed, the function yields an error for n=0 if we do not handle this case).

Afterwards, we create a variable called solutionCount that will increment as new solutions are found. We then create a new Board object, which holds a two-dimensional array (.rows()) that mimics a chessboard as well as various useful methods. For instance, if n=3, emptyBoard.rows() will have the following structure:

[[0, 0, 0]
[0, 0, 0]
[0, 0, 0]]

The zeroes indicate that the chessboard is empty. When a queen is placed at a specific spot on the board, the corresponding number will change to 1.

The next thing that needs to be done is the creation of a recursive function that will find all the possible solutions for a given n. This is shown below:

  function recursive(board, rowIndex) {
    for (let i = 0; i < n; i++) {
      let boardCopy = board.rows().map(function(value) {
        return value.slice();
      });
      let newBoard = new Board(boardCopy);
      newBoard.rows()[rowIndex][i] = 1;
      if (!newBoard.hasAnyQueenConflictsOn(rowIndex, i)) {
        if (rowIndex === n - 1) {
          solutionCount++;
        } else {
          recursive(newBoard, rowIndex + 1);
        }
      }
    }
  }
  recursive(emptyBoard, 0);
  return solutionCount;
}

The following is a step-by-step explanation of the recursive algorithm shown above. Note that “hasAnyQueenConflictsOn” is a pre-defined method for boards. The method returns true if a queen at (rowIndex, colIndex) can be attacked by another queen.

1. First, create a copy of the empty chessboard given as an argument (newBoard). This is done so that the same chessboard will not be continually modified as different queen placements are considered.
2. Add a queen at a certain index on the first row of the chessboard.
3. If there are no conflicts, check if the first row is the last row (i.e., if rowIndex equals n-1). If it is, queens exist on all rows without a conflict, so we have found a solution. Increase solutionCount by 1.
4. If the index of the last row is not equal to (n-1), there are more rows that we must add queens to (as a valid solution consists of one queen in each row and column). Run the recursive function again by passing the copied chessboard and the next rowIndex as arguments.
5. Within the recursive function call, create a copy of the newly modified chessboard and add a queen on the second row (which now corresponds to the new value of rowIndex).
6. If there is a conflict between the first queen and the second queen, the code automatically moves to the next iteration of the for loop and puts the queen at a different position on the second row. This is a process known as backtracking — if there is a conflict, don’t waste time going deeper with recursion. Simply go back and move onto the next possible case.
7. If there is no conflict, check if the second row is the last row. If it is, increase solutionCount by 1 (as all n queens have been placed without conflicts) and move to the next loop iteration. If not, run the recursive function again (this time moving on to the third row of the board).
8. Continue executing the recursive/iterative steps outlined in 5–7 until solutionCount is fully updated. Return solutionCount at the end.

Challenges and Room for Improvement

The biggest challenge that I had while writing this algorithm (and still have) is the issue of optimization. For instance, it did not occur to me at first that I should place the next queen on the next row — instead, I thought that I should try placing the next queen on every single open space. As I later realized, this was a naive approach, as (a) I would still have to place a queen on the next row at some point, and (b) open spaces on the current row would never work because a queen already exists on it.

The issue of having to deep copy the 2D chessboard array on every iteration was also something that I did not see at first. Once I realized that I shouldn’t be modifying the same array on every iteration, I tried copying the 2D array using Array.slice(). This method failed, as I could only achieve a shallow copy. I then tried using JSON.parse(JSON.stringify(array)), which took way too long. The method of copying with .map() and .slice() above was the most efficient solution I could come up with.

If I were to classify my algorithm on this chart, I would (optimistically) place it somewhere between Novice Backtracking and Optimized Backtracking. Of course, using only a one-dimensional array could speed this process up faster, and other techniques like bitwise operators and systematic & greedy search also exist. I hope you can take this algorithm even further and improve its complexity to be on par with some of these other algorithm types!