Solving n-Queens using Bitwise Operators

N-queens is a classic algorithm problem that can be solved with a bunch different implementations (with varying degrees of efficiency). In case you’ve never heard of the n-queens problem before, the question we are trying to answer is: Given a chessboard of size nxn, how many ways can we position n queens so that they are all unable to attack each other?

Here, I’m going to describe my solution to this problem using bitwise operations. Bitwise operators act on binary numbers, which are just the log-base-2 representation of regular integers we’re used to seeing everyday. The fact that these ones and zeros combine to represent a log-base-10 number is ultimately not central to understanding this implementation, and I find it easier to think of the binary numbers in this function as “maps” of open spots (zeros) and spots threatened by a previously-placed queen (ones).

Let me show you what I mean:

var countSolutions = function(n) {  
  var complete = Math.pow(2,n) - 1;
  var counter = 0;
  var recursiveChecker = function (colBit, mjBit, mnBit) {
    if ( colBit === complete ) { 
      return ++counter;
    var possibleSpaces = ~(colBit|mjBit|mnBit);
    while (possibleSpaces & complete) {
      var currentBit = possibleSpaces & -possibleSpaces;
      possibleSpaces -= currentBit;
      newColBit = colBit|currentBit;
      newMJBit = (mjBit|currentBit) << 1;
      newMNBit = (mnBit|currentBit) >> 1;
      recursiveChecker(newColBit, newMJBit, newMNBit);
  return counter;

In this implementation, each call to the recursiveChecker function handles one row of the nxn board. The function is called recursively within the while-loop for every position on that row that is not threatened by a previously-placed queen.

When placing a queen, you have to consider the possibility of an attack along a row, a column, a right-to-left diagonal (which I call a major diagonal), and a left-to-right diagonal (minor diagonal).
By only placing one queen in every row before passing the board “map” back to the recursive checker, I can ignore the possibility of a row-attack. Now, I can keep track of positions threatened by the remaining attack-types using three binary numbers with length of n.

For columns, this is pretty easy to intuit. As I move down the rows to place more queens, the relative index of the columns where I have already placed queens remains the same. For diagonals, something more complicated happens. Consider the major diagonal conflicts for a queen placed in row[0], column[1] on a 4x4 board: For row[0], the major diagonal conflicts can be represented by “0100” (since this is where the queen is). Moving down one row, the space threatened by the same type of attack by the same queen shifts to the right- “0010”. On the next row, it shifts again to “0001”. Finally, on row[3], there are no spaces that would be vulnerable to a major-diagonal attack by that queen. Likewise, the spaces threatened by a minor-diagonal attack shift to the left as you move down the rows.
With this in mind, after you place a queen in a given row, the “map” you pass to the recursive function call (which handles the next row) is the column bit, the major diagonal bit shifted one decimal place to the left, and the minor diagonal bit shifted one decimal place to the right. When the column bit it full, the board is complete and the solution count is incremented.