n-Queens Pt 2: 5,000 times the speed

In which I explicate my accurate, albeit click-bait, title.

You may (or may not — let’s assume not) have read my previous blog post on efficiently counting the number of n Queens solutions: that is, the number of ways in which n Queens can be placed on an n × n chessboard without any of them being able to attack each other:

The main thrust of it was to be careful about when time complexity is too blunt a tool. In big calculations that take a while, constants matter and orders matter.

Some problems are still exponential, but if you can reduce the number of operations you’re doing and increase the rate at which those operations are performed then that could have a real impact. Reducing a constant in an exponential problem from thirty to one (or speeding up its operations by that sort of rate), could change the amount of time it takes to compute from a month to a day; that’s the kind of change that could save lives by making certain calculations possible in applications such as protein folding.


Why are you so obsessed with n-queens?

n-queens is a really fun example of the above: it’s an exponential problem to brute force — not the fastest solution but the most pedagogically interesting — which can be performed at a dramatically faster rate with a few simple tweaks. These simple tweaks do not change it from an exponential problem: it is still O(n^n), but with decreased constants.

Below, I compare several brute-force solutions of the same time complexity:

As you can see, these simple shortcuts can have a real impact on the length of time it takes to compute an answer. You can speed up a solution by:

  1. Decreasing the number of operations;
  2. Doing faster operations;
  3. Doing more operations at the same time.

I looked at one and two in my previous post, but this time I get to look at number three: parallelisation. This is yet another reason I love n-queens: it’s really easy to parallelise. We need to find the number of total solutions, which we can easily do by finding the number of solutions for certain segments of the board separately and summing them.


n Queens running in parallel

Using Web Workers

What’s a Web Worker?

I don’t want to spend too much time on what exactly Web Workers are, but if you’re interested one of the best sources of information is, of course, MDN. They have a good reference and a great page on just getting them going.

The TL;DR of Web Workers is that they’re objects which when instantiated begin execution of a separate, named JS file in their own pristine global context on a new thread. If, like me, you find the possibility of parallelism within JS hugely exciting then you deffo need to find some better hobbies or, like, get in a fight or something. I don’t know — you do you.

There are two important methods that Worker objects have: onmessage and postMessage (with analogues created for the Workers in their own global scopes). The former is an event handler that receives communication from its Worker, and the latter sends communication to it.

Using Web Workers to calculate columns in separate threads

How are they useful for counting n-queens solutions? Well, there are multiple ways of slicing up the work of finding a whole solution. Just as we can take the number of solutions for half the board and double it, we can also take the number of solutions starting at distinct columns on the top row and add them together to find the total. E.g. for an n of four, we can separately calculate the number of possible solutions with a Queen in the first column of the top row and the number of possible solutions with a Queen in the second column of the top row, double them and sum the results to get the total number of solutions for the whole board.

With only a little bit of refactoring, Web Workers can, therefore, separately (and in parallel) calculate the number of individual results for given columns on the top row and return the result for us to sum together to get the total. The important concern here is how fast they are, and I assure you they’re fast. How fast? Like, shit me, I barely got my socks off fast.

How fast exactly?

Above, our initial solution (simply recursing through every possible solution) took 1,400 seconds (around 23 and a half minutes) to calculate the number of solutions for n=12. Our best solution so far took over ten seconds. My Web Workers take on average 285ms. That’s about 5,000 times faster than our slowest solution.

Some other average times they return:

  • n=13: 1,300ms
  • n=14: 6,650ms
  • n=13: 45,900ms

Compare that to our previous fastest solution which took around 10,000ms for n=12 and 56,350ms for n=13, this is a really strong gain on an already good solution.

How are they so fast?

Web Workers have a lot of advantages. In particular, they’re not worrying about the DOM and have a completely fresh execution context. One web worker on its own will calculate n-queens for n=12 in less than a second on my laptop. This is substantially faster than our previous fastest solution with which it shares almost all of its code. Of course, the biggest gain is that you can run one for each column.

Obviously just looking at times is an apples-and-oranges game with different implementations, different computers etc. I’ve been as methodical as I can, ensuring all the tests are run in as similar an environment as possible on the same computer, in the same browser at the same version. The Mocha framework I used to write tests to compare the times of the above would be a difficult tool to time my Web Workers as they run asynchronously in a different context. Instead, the solution times itself, taking the time before it initialises its first variable and subtracting that from the time straight after it logs an answer.


Getting the most out of my Web Workers

Keep them working all the time

The most important thing was that my Web Workers didn’t idle — that would defeat the point — so I pretty quickly rejected the idea distributing columns as workers were created; what if one of them finished its workload long before the other? The number of viable solutions is pretty unevenly distributed across the board, so simple solutions like giving one worker even columns and one odd would very likely lead to that scenario.

Communication with Workers is handled with the onmessage and postMessge methods I explained above. The API is very simple: all you can do is send and receive data to and from your Workers (and, in special cases transfer ownership of data), but getting the most out of them can be complicated for exactly that reason.

Their loss of global context, in particular, makes it important to ensure that your Worker has all the information and data they need but also gives one a chance to ensure that they have no more than they need. Passing objects between contexts is not easy, as everything sent to your Worker is, in fact, copied as a structured clone. Functions don’t survive the transition, so a lot of objects become useless, and classes are obviously right out. As a rule of thumb, your worker can get what you could usefully JSON.stringify.

The token system

This leaves a conundrum: how to coordinate Web Workers effectively without distributing their work as they’re created: I used ‘tokens’. I imagined this like taking a number when you’re queuing for something. Every time someone takes one, it leaves the next number for the next person regardless of the wait. I wrote a solver, responsible for creating the requested number of Workers (defaulting to three) and distributing the workload across them. Every time a Worker reports back from one calculation, it’s given a new token saying which column of the top row to count the solutions for next.

Thanks for reading :)

Thanks pals. The gist below shows how the Workers were coordinated; the full code can be found at this repo should you wish to run it for yourself (and maybe improve it?). Let me know any thoughts, comments or corrections!

PWM’s Computery Bollocks

Computery bollocks that I find diverting — 99% just faffing about

Peter Warner-Medley

Written by

PWM’s Computery Bollocks

Computery bollocks that I find diverting — 99% just faffing about

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade