N-Queens

The N-Queens puzzle is a classic computer science problem. In fact, it’s much older than discipline of computer science. It is usually used as a problem to introduce students to backtracking algorithms in computer science. I was first introduced to the problem in Niklaus Wirth’s Algorithms + Data Structures = Programs back in the ’70s.

I thought it might be interesting to write an updated version in my continuing effort to become proficient in Clojure. My intent was to write a simple working version, then use the concurrency features of the language to write a parallel version and see what kind of performance gain was possible.

Instead, I came across some interesting existing examples in the language. In researching the problem, I first came across the version at Rosetta Code. The code seems concise and straightforward. I also came across a version at the Mired in Code blog. Again, the code seems clean.

Imagine my surprise when I benchmarked the two versions and found that the implementation at Mired in Code was 40 (serial version) to 100 (parallel version) times faster than the solution presented at Rosetta Code. I’m not expert enough at Clojure to discover the reason for the difference just by inspecting the code. And I’m not expert enough with profiling Clojure to have discovered the difference by analysis yet.

But I thought I would post a repository containing a simple benchmarking project illustrating the differences here for anyone interested.

One more interesting thing. Professor Wirth once wrote that his solution took about one second to run back in the 70’s on a rather powerful mainframe of the time. It’s pretty gratifying to see that the slow version of the solutions runs that fast on a desktop today. It is even more gratifying to see that a faster version is up to 100x quicker.