While the topics and technologies are coming fast and furious at Hack Reactor, one assignment has held my attention more than any other in the last couple of weeks. Once through the eleven-hour day, I find myself spending my copious free time revising my strategies for the ‘N Queens’ problem (in which some number (n) of queens must be placed on an n by n chessboard so that they do not threaten each other).
It has been a very long time since I wrote much recursive code, so my first pass at the problem was pretty naive, very expensive and just focused on remembering how to structure a base case and recursive call. I realized I could represent the board as an array of n elements (in which positions on the board were represented by using the index of each element to represent a piece’s column, and the value of the element to represent the row), rather than a matrix:
var sampleSolution = [1,3,5,0,2,4];
Therefore, a brute-force approach to generating solutions simply required all permutations of the sequence 1 to ‘n’. However, my approach was to generate all possible board permutations in which each column held one queen, and to then iterate over each permutation in the array, convert it to a two-dimensional array that represented the board, and then test that for queens conflicts. So, yeah. Slow.
My first rewrite was almost top-to-bottom. I started by rewriting my validity checking functions to run on the one-dimensional representation of the board, removing the step of converting each permutation to a matrix board when I checked it. This way, I could check boards as they were generated, and only push valid boards into the solutions array. That made a huge difference.
Next, I started looking at ways that I could prune possible board spaces. Since a board permutation is generated column by column, I could run a validity check on the board every time a new element was added to the sequence. If a partial sequence had queens conflicts, then it was safe to ignore any permutations that began with this partial sequence. This change dramatically increased the performance for large boards.
What next?
The immediately obvious improvement lay in the way I was testing partial sequences. For each board fragment (e.g. [1], [1,3], [1,3,5], etc.), I would test each element (column) for queens conflicts. In order to reduce the number of checks, I implemented a breadcrumb hash to to track conflicts. I gave each diagonal on the board a number, and hashed a to a simple array for every diagonal on the board that was occupied. This way, every new element added to the candidate board could be checked against the hash, rather than re-checking conflicts for every element in the array so far.
Oddly, this didn’t give me the speed improvement I was expecting. I suspect that’s a factor of my implementation, which is what I’m analyzing right now.
If I can nail that down, I’m going to investigate two more possible optimizations:
- I think I can check for diagonal conflicts using bitwise operations, which should be faster than my current checking method. I know that using buffers in Node.js might provide even faster bitwise operations, but I’m trying to keep things in the browser for now, so we’ll see how that goes…
- Concurrency: I’m also wondering if I can divide the space of potential boards to be generated so that they can be worked on by separate workers. Not too sure about that yet…