Bitwise N-Queens

The N-Queens Problem

Eight Queens is a well-known algorithmic problem. How many ways can you place eight queens on an 8x8 chessboard so that none of the queens threaten each other. Following the rules of chess, one queen threatens another when it is in the same row, column, or diagonal. N-Queens in the more general problem of solving this for any n queens on an n x n chessboard.

The Non-Bitwise Solution

I first solved this problem using an instance of an abstract Board class on which I recorded the positions of the queens as I placed them. The Board is basically a matrix populated with 0s and 1s where 1s represent the placed queens and 0s represent the empty spaces. The Board class also contained methods called

1

togglePiece()

1

hasAnyQueenConflicts()

1

countNQueensSolutions

window.countNQueensSolutions = function(n){
  var solutionCount = 0; 
  var board = new Board({n:n});

  var countQueenSolutions = function(queenBoard, rowIndex, numCols) {
    if (rowIndex === numCols) {
      solutionCount++;
      return;
    }
    for (var i = 0; i < numCols; i++){
      board.togglePiece(rowIndex, i);
      if (!queenBoard.hasAnyQueensConflicts()){
        var result = countQueenSolutions(queenBoard, rowIndex+1, numCols);
        if (result) { return solution = result; }
      }
      board.togglePiece(rowIndex, i);
    }
  };

  countQueenSolutions(board, 0, n);
  console.log('Number of solutions for ' + n + ' queens:', solutionCount);
  return solutionCount;
};

The Bitwise Solution

My goal was to implement a solution using bitshifting. While a bitshifting implementation would definitely increase the performance of the code above, I wanted to do this merely to better understand how I could use bitwise operators in an algorithm like this one. Also, it was good preparation before attending a panel this week with three engineers out of Hack Reactor talking about their attempt to use a supercomputer to solve N-Queens where N=27. There was a Wired article about this.

No Board, no

1	togglePiece()

In the bitwise implementation, we won’t be using the Board class. Instead of using the Board matrix, we’ll use binary numbers to represent the queen’s position in a row. For instance, in a 4x4 chessboard, the queen’s position will be a binary number with the queen represented by 1 and the empty places represented by 0s:

Instead of using Board’s

1

togglePiece()

No Board, no

1	hasAnyQueensConflicts()

We need a new way - a bitshifting way - of finding the threats to a queen in a particular position. Since we’re working with one position per row, we don’t need to account for row conflicts, but we still need to worry about column conflicts, minor diagonal (left) conflicts, and major diagonal (right) conflicts.

Imagine that the queen is in the third position in the row. The binary representations of the conflicts are shown in the table below - 1s are in positions for the conflicts.

In order to check for all the conflicts, we need to bitwise OR these 3 conflicts to find all the positions that would cause a conflict in the next row. So

Now we can see that despite all these conflicts, there still is a position where a queen could fit in the next row without causing additional conflicts (represented by 1000).

We can find that perfect position by iterating through all possible positions of the queen and performing bitwise AND with this position and the conflicts. When the result of this operation is 0, we know that there is a place for the queen.

Compare the above table with the one below where there would be a conflict with queen’s position.

It’s only when the result of the bitwise AND equals 0 that we know the queen will be able to be in that position without conflict.

Finding the next row’s conflicts

In the example above, we had the following conflicts and position of the queen

We can build on this information in order to find the conflicts in the next row. The next column conflict is found by bitwise ORing the current column conflict with the queen’s position. Similarly, the next minor diagonal and major diagonal conflicts are found by bitwise ORing the current conflicts with the queen’s position and then bitshifting the diagonals in the proper direction (to the left for the minor diagonals and to the right for major diagonals.) This gives us the following next conflicts.

Column Conflicts

Minor Diagonal Conflicts

Major Diagonal Conflicts

Putting it Together

Now we can implement the bitwise queens logic into the original

1

countNQueensSolutions

window.countNQueensSolutionsBitwise = function(n) {
  var solutionCount = 0;

  // uses minDiagConflict, majDiagConflict, colConflict for conflicts in the 
  // minor diagonal, major diagonal, and column
  // only placing one queen per row so not testing row conflicts
  var countQueenSolutions = function(currentRow, minDiagConflict, majDiagConflict, colConflict) {

    // if we've hit n (the index past the last row), then we've found a solution
    if (currentRow === n) {
      solutionCount++;
      return;
    }

    // we have a conflict if we have any type of conflict  
    // so we want to use bitwise OR  
    var conflicts = minDiagConflict | majDiagConflict | colConflict;

    // iterates from 1 up through increments of 2 (binary numbers)
    // until it bitshifts over the size of the board 
    // ex: if n = 4 , (1 << 4) = 10000 = 16, so the last iteration will be 
    // when queenPosition = 8 = 1000 [1 = 0001, 2 = 0010, 4 = 0100, 8 = 1000]
    // queenPosition represents the position of the queen in the row
    for (var queenPosition = 1; queenPosition < 1<<n; queenPosition*=2) {

      // we want conflicts & queenPosition to equal 0
      if (!(conflicts & queenPosition)) {

        // put the next values of the conflicts into the recursive solution
        // (stored in variables here for readability in the blog post)
        var nextMinDiagConflict = (minDiagConflict | queenPosition) << 1;
        var nextMajDiagConflict = (majDiagConflict | queenPosition) >> 1;
        var nextColConflict = colConflict | queenPosition;
        result = countQueenSolutions(currentRow+1, nextMinDiagConflict, nextMajDiagConflict, nextColConflict);
        if (result) return solutionCount = result;
      }
    }
  };

  countQueenSolutions(0,0,0,0);
  return solutionCount;
};