N-Queens

Eric Schmidt and I were asked to write an algorithm to solve the N-Queens problem: how many different ways can n queens fit on an n x n chessboard, such that none of the queens could knock out another in a single move?

For Example

• 1x1 board with 1 queen: 1 way
• 2x2 board with 2 queens: no ways
• 3x3 board with 3 queens: no ways
• 4x4 board with 4 queens: 2 ways

And so on.

For context, the world record for counting solutions to this problem is n = 26, which uses world-class supercomputers.

This is a hard problem because it involves recursive backtracking through possibilities, and the time-complexity is n! difficult.

But Hack Reactor offered a good amount of guidance about how to approach the challenge, and our first algorithm was able to solve up to n = 15 in about 300 milliseconds.

Then we were able to plug our solution-finding algorithm into a chessboard visualizer, so all of the different possibilities can be examined for any given n.

We also implemented the famous bitwise algorithm from Martin’s 1973 paper.

And then we were able to make this work multi-threaded using Web Workers. That was new for us, and not very straightforward – there’s not much good documentation about how to use these new techniques – but eventually we got it working. It managed to cut down the computation time for n = 16 from 800ms to 400ms, a 50% improvement.

We successfully got that to run for n = 19, which took 50 minutes. If it continued to follow a factorial run-time, we’d expect n = 20 to take almost 17 hours.