Summary: recently I was asked to solve the classic N-Queens problem in an interview setting and came up with a slightly unorthodox solution. After a couple of iterations, I believe my solution is close to optimal. See if you agree.
Let’s recap — the N Queens problem is to enumerate all the possible arrangements of Queens on a NxN such that no Queen attacks another.
If your Chess is rusty, a Queen combines the moves of a Rook and a Bishop.
A Rook attacks all the squares along its rank and file, i.e. vertically and horizontally (N, S, W, E). A Bishop attacks all the square diagonally(NW, SE, NE, SW). So a Queen attacks along eight directions of the compass effectively (N, S, W, E, NW, SE, NE, SW).
Here’s the classic backtracking solution that’s quoted in most textbooks:
One handy rubyism is to use a generator so we can reuse the same code for counting solutions as well as listing them. Sweet!
Ok, so how do we code unsafe?. Basically we want to check that our candidates square in’t on a rank or diagonal of an existing Queen.
First attempt: count the attacks for every square
So every time we want to check a new Queen is safe, we have to compute the diagonals of all the previous Queens and compare them with our new Queen. That seems a bit inefficient. So in the interview, I proposed precomputing all the squares attacked from a given square and maintaining a count of how often every square is attacked. Here’s a straightforward implementation:
Compared to the previous solution, the unsafe? test is now extremely cheap — we just check if the candidate square has a positive count and we’re done. So how does it stack up against the naive solution?
$ time ruby n_queens.rb 12
14200real 0m14.801s
user 0m14.694s
sys 0m0.044s$ time ruby n_queens_counts.rb 12
14200real 0m10.422s
user 0m10.369s
sys 0m0.035s
It’s a 30% improvement. Not bad. Unfortunately, keeping the @counts array up-to-date isn’t cheap, despite precomputing and caching the results of attacks_all. As interviewers like to say… can we do better?
Second attempt: cache diagonals not squares.
The answer was staring us in the face in the original naive solution. Rather than recompute the diagonals of every square in the current solution, keep them in an efficient representation. What would that look like? Well how many NorthWest diagonals are there in an NxN board? 2*N-1. That’s not bad. Let’s keep them in a simple bitmask. First let’s code up our bit twiddling methods:
With those under our belt, we just need to reimplement unsafe?, move! and unmove!
Okey dokey. Time for another benchmark…
$ time ruby n_queens_bitmask.rb 12
14200real 0m4.210s
user 0m4.178s
sys 0m0.024s
Almost a 4x speedup over the naive solution. Woohoo!
Of course at this point there’s always some smart ass who points out that if your goal is speed, then you shouldn’t be coding in ruby. Grrr.
Crystal power!
I am seriously surprised how few rubyists know about crystal. It’s syntax is heavily based on the ruby syntax except it is statically typed and compiled. Yes, you read that right — you get a sweet little executable for your hard earned labours. No more looking enviously at your colleagues hacking Go or rust! So how hard is it to port a ruby to crystal? Not very. The crystal compiler insists that you disambiguate your types by adding type signatures to your methods and some instance variables. But you were going to document them anyway, right? Right??? So here’s the key parts of the crystal port of the bitmask implementation.
Fairly easy on the eyes. Only took me a few minutes once I got the hang of the crystal toolchain — you need to compile *and* run separately.
But what about the benchmarks? Drum roll please…
$ time ./n_queens_bitmask_run 12
14200real 0m0.385s
user 0m0.369s
sys 0m0.009s
Bam! Roughly 40x faster than our original naive ruby implementation. And for those of you who think I should use a *real* language — the C version was only 40% faster. Not too shabby for using an elegant statically typed OO language…
Appendix
If you’d like to peruse the code, the repo is: