Bitwise Optimization of N-Queens (2024)

The N-Queens problem is a classic problem in algorithm design. It involves finding a way (or multiple ways) to place n queens on an n by n chessboard such that no queen can attack another along any row, column, or diagonal. There are numerous possible approaches to this problem, ranging from extremely inefficient exhaustive generation and evaluation to modern solutions using neural networks or genetic algorithms. In this post I will explore an optimized recursive backtracking algorithm, implemented in JavaScript, which makes use of bit strings to efficiently prune the queen placement tree as early as possible. My approach, which will discover all possible solutions for a given value of n, is based on an algorithm by Martin Richards found in this academic paper.

At the core of the algorithm is a simple recursive function which adds a queen to a single row of the chessboard, and then calls itself to add a queen to the row above. Let’s get a feel for the basic idea with some pseudocode:

function placeQueen(board, row) { //if row is greater than board size //BASE CASE: we’ve placed queens on every row, //return what we’ve found //for each space in row //if a queen can safely go here //place queen on board //call placeQueen with (board, row + 1) to place the next queen //remove queen from board for next iteration}

The above function will build a complete tree of possible solutions, but skip searching branches as soon as a conflict is created. If our intent is an exhaustive search (rather than, for example, using heuristics to find a single solution), this is already a pretty solid approach. But let's explore further optimization by delving into how we check for conflicts with already-placed queens.

There are a few possibilities for checking whether a queen can be placed on a given square. Initially, we might opt to scan each column and the major and minor diagonal of the potential square for other queens which could pose a threat, resulting in linear time complexity for every check. We can do better. By implementing caching of occupied columns and diagonals, we can get to constant time lookup. (Imagine passing along with the board an array of true or false values which represent whether a queen already resides in their column/diagonal. Then we can merely check this array, avoiding the need to scan every square in the column or diagonal). This is a step in the right direction. But we can go even further with the magic of bitwise operators, both by taking advantage of their great speed and by eliminating the need to test each possibility, skipping straight to each workable queen placement in constant time. Let’s take a look at how this is possible. (I assume a basic familiarity with bitwise operations. If you need a quick refresher on bit shifts and bitwise AND, OR, XOR, and NOT, Wikipedia is a good place to start). Complete JavaScript code for findNQueensSolutions is found near the bottom of this post - it may be helpful to refer to it while reading.

First, we need to add some parameters to our recursive function – bit strings in which a set bit will represent the presence of a queen. Let’s call them colBits, majDiagBits, and minDiagBits. (If you’re stingy about parameters for some reason, you could also of course store all the information in a single parameter!) We’ll look at how these parameters are generated and updated in a moment; for now understand that (for example) bit 2 being set in colBits represents an existing vertical queen conflict in column two and bit 2 being set in majDiagBits represents a major diagonal queen conflict in column two for the current row. Thus, evaluating colBits | majDiagBits | minDiagBits gives us a bit string in which all columns which result in any type of conflict on this row are marked with set bits. Then we simply perform a NOT operation on the resulting bit string to obtain a bit string in which all possible, non-conflicting queen locations for this row are set.

Since we will shortly be adding a queen at each set bit without wasting time on range checking, we need to perform a corrective action here. If our bit strings are stored in a number of greater than n bits (and they will be; I doubt any computers would be willing to accommodate our desire for a 5-bit number with which to solve the 5-queens problem!), there will be a number of unused zeros at the front of our bit string. And our previous NOT operation has just changed them all to ones, indicating that we should go ahead and put a queen on these non-existent spaces! To zero out everything but the last n bits, we simply mask (AND) our bit string with (1 << n) – 1. The following example should clarify why this works:

00000001 Start with the binary representation of 1 00010000 Left shift by n (in this case, 4) 00001111 Subtract 1 (regular integer subtraction) We can now AND this bit string with any number to zero out all but the last 4 bits. 

Okay, so we have a bit string where each set bit represents a possible queen placement, and we’ve found it using only extremely efficient bitwise operations. At this point we could pat ourselves on the back for some nice optimizations and loop over the bit string (via shifting), plopping down queens wherever we see a one. But we can actually improve our time even more by only looping over the bits where we know we will actually place a queen. Assuming we stored our result from the last operation in a variable called possibilities, it looks like this:

while (bit = (possibilities & -possibilities)) { 

What’s going on there? The first thing to notice on this line is that we’re mixing an assignment and a conditional; generally a slightly obfuscating practice but reasonably clear in this instance. On each iteration, we set a variable bit to the result of ANDing possibilities and negative possibilities. This results in bit being set to all zeros with the exception of the least significant set bit in possibilities, where we will place our queen. Explaining why this works would require an in-depth discussion of how computers generally store signed numbers, which is beyond the scope of this blog post; interested readers should research two’s complement.

Within the body of the loop, we first set possibilities ^= bit. This unsets the current (least significant) set bit in possibilities so the next time through the loop we will examine the next possibility (the new least significant set bit). We make our recursive call, updating our bit strings for the next row (recall that bit contains a bit string with a single 1 representing the queen's new location. Thus, ORing it with our passed-in conflict information adds it as a potential conflict for the recursive call):

placeQueen(colBits | bit, (majDiagBits | bit) << 1, (minDiagBits | bit) >> 1) 

If it’s not apparent why shifting the diagonal bit strings by one is the correct way to update them, think about it this way: if a queen threatens a space in column i along its major diagonal, it threatens space (i – 1) in the row immediately above. Thus, shifting each set bit by one in the appropriate direction results in the correct conflict information for the next row.

Up to this point, I've followed the Martin Richards algorithm closely, which was my primary intent in creating this solution. But I'd now like to suggest a slightly modified version of the algorithm, which offers somewhat increased speed but perhaps requires us to think about bitwise operators in a less intuitive way. By inverting the meaning of a set bit outside our while loop, we are able to use a different set of bitwise operations (eliminating a NOT, replacing some ORs with XORs, etc.). In a certain sense, this approach creates a more consistent interpretation of our bit strings, but it also requires us to abandon our instinct that an empty board should be filled with zeros. It is not immediately clear that this should run any faster; however, profiling reveals that this configuration is in fact slightly more efficient, particularly as n becomes large. I won't provide a blow-by-blow walkthrough of this version of the algorithm; curious readers hopefully now have the tools to work through the code on their own.

And that's it! With these optimizations, the algorithm runs around two orders of magnitude faster than our original recursive backtracking idea. Running in Google Chrome on my mid-range laptop, it finds the 92 solutions (counting symmetrical solutions) to the 8-queens problem in under a millisecond, and all (over 14 million) solutions to the 16-queens problem in less than twenty seconds. The following table shows average execution time for various versions of the algorithm and different values of n:

Both complete bitwise implementations in JavaScript follow:

function findNQueensSolutions(n) { var mask = (1 << n) - 1; (function placeQueen(colBits, majDiagBits, minDiagBits) { if (colBits === mask) { return; //Base case: do something with our solution. //We would probably accept a callback parameter. } var bit, possibilities = ~(colBits | majDiagBits | minDiagBits) & mask; while (bit = possibilities & -possibilities) { possibilities ^= bit; placeQueen(colBits | bit, (majDiagBits | bit) << 1, (minDiagBits | bit) >> 1); } }(0, 0, 0));}

function findNQueensSolutionsFlipped(n) { var shiftCorrect = 1 << (n - 1); (function placeQueen(colBits, majDiagBits, minDiagBits) { if (colBits === 0) { return; //solution found } var bit, possibilities = colBits & majDiagBits & minDiagBits; while (bit = possibilities & -possibilities) { possibilities ^= bit; placeQueen(colBits ^ bit, (majDiagBits ^ bit) << 1 | 1, (minDiagBits ^ bit) >> 1 | shiftCorrect); } }((1 << n) - 1, (1 << n) - 1, (1 << n) - 1));}

These are tricky algorithms; it may take a while to grasp what's going on. Readers who wish to test their understanding may want to try answering the following questions:

• In findNQueensSolutions, why do we test for the base case with colBits === mask?
• How does findNQueensSolutionsFlipped work? Specifically:
• What does a set bit represent in each stage of the algorithm and how is it different from the non-flipped version? (Hint: examine the difference in the base case test)
• Why do we make our first call with (1 << n) - 1 as each parameter?
• Why have we switched from OR to XOR in our recursive call, and what is the purpose of shiftCorrect?

I hope you've enjoyed this foray into the increasingly (and lamentably) unfrequented territory of bitwise operations, and maybe learned something along the way!