N-Queens Problem Solutions by Lauschke Consulting using JavaTools

N-Queens Problem: Comparing Mathematica(Mathematica) vs. Java (JVM) vs. Scala (JVM) vs. C# (.Net) vs. F# (.Net) with JavaTools

    Technical Note: Scala can also be compiled to .Net, and C# and F# can also be compiled to mono.

On this page we discuss several ways of computing the exact number of solutions of the n-queens problem for various n. The purpose of this discussion is to exemplify several advantages and shortcomings of these programming languages and their underlying execution platforms, in particular as to how they relate to functional programming and recursion. The Mathematica, Java, Scala, C#, and F# languages all have their relative advantages and shortcomings, and so do the Mathematica, JVM, and .Net execution platforms.

The objective of the n-queens problems is to place n queens on an n x n chessboard so that no two queens can attack each other. An exact formula for the number of solutions is still unknown today, despite over 160 years of research. The problem was originally posed by German chess player Max Bezzel, http://www.schachclub-ansbach.de/chronik_bezzel.htm, in 1848. He was never able to solve the problem completely in his lifetime -- until he passed away in 1871 due to cancer. Even Carl Friedrich Gauß tried to solve this problem. Dr. Nauck proved already in 1850 that there are 92 solutions for the 8 x 8 board (which is trivial for us today). By 1890 it was proven (through tedious manual experiments) that the 11 x 11 board had 2680 solutions (which also is trivial for us today). Subsequently, the n-queens problem has become one of the most celebrated problems for combinatorial algorithm benchmarks until today. In 1998 the two French mathematicians Sylvain Pion and Joel Fourré proved with 300 computers and 2 months' computation time that the solution to the 23 x 23 chessboard had 24 233 937 684 440 solutions (24.2 trillion), which is the world record, until today. Researchers have long switched over to the toroidal chessboard, to reduce computation time.

The asymptotic form of D(n) is unknown. Rivin et al. (The American Mathematical Monthly, vol. 101, 1994) conjecture that

Based on the known values of the sequence it is further conjectured that

with

which means that the logarithmic asymptotic form is slightly super-linear.

We picked the n-queens problem for various reasons.
◆ The n-queens problem has no known solution: no explicit or recursive function is known, and no generating function is known. The problem is genuinely intractable.
◆ It is best solved with backtracking recursion, to reduce the combinatorial explosion of possibilities. All other approaches to solve the n-queens problem are absolutely inferior.
◆ In performance comparisons recursion is oftentimes used because some platforms provide currying and tail-recursion which can speed up recursion enormously. Tail-recursion works by overwriting parameters during the recursion, which means no new stack space is needed. Hence, tail-recursive functions are iterative processes, which means they operate in linear time. Scala, for example, supports currying and tail-recursion in its term-rewriting.
◆ F# and Scala are functional programming languages (and so is Mathematica, and C# at least supports closures through Linq since .Net 3). Java is not a functional programming language, but, of course, it supports recursion.
◆ Recursion makes programs very succinct, code-efficient, and easy to understand. We generally prefer solutions with shorter code, although this is not a strict rule. If the solution with better performance is longer and most likely more elaborate, then we still prefer that solution with the longer code.

Solutions based on Backtracking and Recursion

In the first example we compare a top-level recursive Mathematica version with its corresponding F# version. The code is taken from http://stackoverflow.com/questions/6097071/tree-data-structure-in-mathematica.

The Mathematica code:

In[1]:=

In[2]:=

In[9]:=

The corresponding F# code:

In[18]:=

In[5]:=

The F# code above was specifically written to correspond to the previous Mathematica code. In the following we use functional operations on lists and the pipeline operator |> in F# to see if we get substantially different behavior. We have an intuition that lists are implemented *extremely* efficient in .Net and in the JVM, and combined with a functional paradigm should be the best candidates for the fastest solution:

In[20]:=

In[8]:=

Here is an equivalent Scala solution:

In[9]:=

In[12]:=

In[15]:=

Out[15]=

In[16]:=

Out[16]=

The Mathematica version is significantly slower because it is top-level code and not compiled. Note that the timing results for the F# and Scala solutions, using AbsoluteTiming[], include the link time, i. e. the time needed to call into .Net (and the JVM respectively) and to receive the results. In addition, the Scala solution returns a full list of the queen placements, not just the number of queen placements. This further slows down the Scala version, because all the queen placements are data and must be stored/managed in memory, yet it remains the clear winner (further evidenced by larger examples below).

We drop the Mathematica solution at this point so we can increase n further and compare the F# and Scala solutions:

In[17]:=

In[19]:=

In[22]:=

In[24]:=

In[25]:=

Out[25]=

In[26]:=

Out[26]=

At this point we abandon the recursive-only approach and make use of methods that exploit recursion, functional programming, and list-based programming. The list-based programming style oftentimes also allows for very easy addition of parallelization. In F# we would use an asynchronous workflow, and in Scala we would use a concurrent collection, to where the mere addition of the parallel method .par is all we’d need to do to have execution in parallel threads over all available cores. We do not do this here, but the page www.lauschkeconsulting.com/jcc.html shows a few examples of this.

Solutions based on Bit-Shifting

The use of bit-shifting helps us further to speed things up. Generally speaking, algorithms using binary arithmetic can be extremely fast, because binary arithmetic operates at the bit level, which is about the fastest speed possibly attainable, due to the binary number representations on computers. We can use it in Java, C#, F#, and Scala to get amazing speed results. Unfortunately, in Mathematica binary arithmetic is NOT performed at the bit level, this is true for compiled as well as uncompiled code (see discussion with examples further down).

The following Mathematica solution, due to Leonid Shifrin, makes heavy use of very advanced Mathematica programming paradigms. This Mathematica solution is a true expert solution that required a lot of thinking and theoretical development. It is much faster than the Mathematica solution presented above, but still slower than anything else (see below). This emphasizes once again the value of being able to copy/paste an existing solution found on the web or elsewhere, or interactively exploring solutions in other programming languages, instead of spending a lot of time on a dedicated effort to solve a problem within the self-imposed limitations of the Mathematica system. The objective of JavaTools is to make things not only *faster* during the execution, but also *easier* for the programmer during the development phase. Only very few people are able to program in Mathematica on that expert level. Yet, all Mathematica solutions presented here lose out completely against their Java, Scala, C#, and F# counterparts, as we shall see in the following.

In[27]:=

In[33]:=

In[34]:=

We throw the following Java solution into the race. This is a modification of the Java code from http://rosettacode.org/wiki/N-queens_problem#Java

In[35]:=

In[37]:=

The following Java solution is due to Bob Rimmer. It is based on the paper “Backtracking Algorithms in MCPL using Bit Patterns and Recursion” by Martin Richards. The reader is referred to this paper to understand more about using bit patterns for the n-queens problem (and related matters and other examples of the usefulness of bit patterns).

We use long in the Java and C# and Long in the Scala solutions because that is the type which matches the processor word size, without requiring any type conversion. Using int (Int) in the following was about 1/6 slower in the Java and Scala solutions. In the C# solution there was no discernible difference by using long instead of int, but for reasons of consistency we have kept it with long.

In[40]:=

In[43]:=

We have a feeling this algorithmic approch may be very superior, so we convert the algorithm to Scala and C# as well:

In[51]:=

In[88]:=

Out[88]=

In[54]:=

Also due to Bob Rimmer is the following Mathematica implementation, using bit patterns and recursion, and we attempt C compilation and parallelization:

In[55]:=

Out[55]=

It seems C compilation fails, see more about this in the next section.

In[56]:=

Also due to Bob Rimmer is the following Mathematica implementation, using bit patterns and recursion. It is an improvement over the previous version that attempts to compile to C code.

In[57]:=

In[58]:=

We get the following results:

In[59]:=

Out[59]=

At this point we drop all three Mathematica solutions and compare only the Java and Scala and F# solutions:

In[60]:=

In[61]:=

In[62]:=

In[65]:=

In[68]:=

In[69]:=

Out[69]=

In[70]:=

Out[70]=

We have clear winners. In less than 5 seconds we computed that the 15 x 15 chessboard has 2.3 million placements, using bit-shift operations in Java and Scala. However, the C# versions is not bad either. The relevant point is that we have substantially increased the speed by using bit-shift operations.

Let’s try 16, but just for the three solutions based on bit-shifting, to see if we can differentiate between the three:

In[79]:=

Out[96]=

In[97]:=

Out[97]=

In[98]:=

Out[98]=

With Java and Scala it’s pretty much a toss-up, but C#/.Net clearly starts lagging behind.

We can compute D(18), over 666 million, in less than half an hour:

Other Languages: Perl

In the spirit of showing a variety of languages to provide solutions from the same Mathematica session, here is a very efficient perl solution, it’s very fast and code-efficient. To our knowledge, it is due to Nick Holloway, 1993. Although JavaTools does not support perl directly at this time, it is very easy to harness the power of perl for our comparison. A perl program is JIT-compiled to C code upon invocation.

In[71]:=

6.5 seconds for an 11 x 11 chessboard, that is faster than all Mathematica solutions, “between” the two  F# solutions, and slower than Java and Scala (see above). Note that actual computation time is even slightly less, because the function nqueensperl[] also has to Export[] the perl string to the local file system and read and interpret the result after the computation has finished.

Shortcomings of Mathematica’s C Compilation

C compilation in Mathematica can sometimes be very disappointing. Although it’s clear, and to be expected, that not all parts of a Mathematica expression can be compiled (we know this from bytecode compilation in Mathematica), it appears that some attempts to compile to C code don’t compile anything at all. In the following we compare a version for which we (unsuccessfully) try Mathematica’s C compilation with an uncompiled version:

We note that the attempted compilation does not succeed:

In[72]:=

Here is the uncompiled equivalent:

The uncompiled version is just as fast:

Mathematica’s compilation is disappointing in other regards as well. We find that C compilation is limited to 32 bit computations, while Java has no problems with 64 bit:

Byte code:

In[73]:=

Out[73]=

C code:

Java sees no problems:

In[74]:=

Also C#/.Net have no problem with 64 bit technology:

In[75]:=

Out[75]=

But Mathematica cannot compile it to C:

In[76]:=

Out[76]=

We also found that the bitwise operations in Mathematica cannot be compiled and don’t operate on a bit level. These operations are many times slower than Mod[] or Quotient[] or just plain arithmetic. This means that the Mathematica versions presented above could be made many times faster by using other plain arithmetic operators like Mod[#,2] etc. instead of BitShift[]. This came quite surprising and is quite disappointing, the author of JavaTools didn’t know this until he actually dealt with this matter.

We have checked, the 64 bit technology *IS* in the runtime libraries of Windows/.Net/Linux/Java. We can write several bit shift functions with Java. Mathematica’s Compile[] doesn’t support ANY of these types of C compilations.

In[77]:=

Or bit shifts with C#:

In[78]:=

Out[78]=

Created with Wolfram Mathematica 8.0