Back to Lauschke Consulting Home Back to JavaTools Home

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

nqueens_1.gif

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

nqueens_2.gif

with

nqueens_3.gif

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]:=

nqueens_4.gif

In[2]:=

nqueens_5.gif

In[9]:=

nqueens_6.gif

The corresponding F# code:

In[18]:=

nqueens_7.gif

In[5]:=

nqueens_8.gif

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]:=

nqueens_9.gif

In[8]:=

nqueens_10.gif

Here is an equivalent Scala solution:

In[9]:=

nqueens_11.gif

In[12]:=

nqueens_12.gif

In[15]:=

nqueens_13.gif

Out[15]=

nqueens_14.gif

In[16]:=

nqueens_15.gif

Out[16]=

nqueens_16.gif

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]:=

nqueens_17.gif

In[19]:=

nqueens_18.gif

In[22]:=

nqueens_19.gif

In[24]:=

nqueens_20.gif

In[25]:=

nqueens_21.gif

Out[25]=

nqueens_22.gif

In[26]:=

nqueens_23.gif

Out[26]=

nqueens_24.gif

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]:=

nqueens_25.gif

In[33]:=

nqueens_26.gif

In[34]:=

nqueens_27.gif

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]:=

nqueens_28.gif

In[37]:=

nqueens_29.gif

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]:=

nqueens_30.gif

In[43]:=

nqueens_31.gif

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

nqueens_32.gif

In[51]:=

nqueens_33.gif

In[88]:=

nqueens_34.gif

Out[88]=

nqueens_35.gif

In[54]:=

nqueens_36.gif

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

In[55]:=

nqueens_37.gif

Out[55]=

nqueens_38.gif

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

In[56]:=

nqueens_39.gif

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]:=

nqueens_40.gif

In[58]:=

nqueens_41.gif

We get the following results:

In[59]:=

nqueens_42.gif

Out[59]=

nqueens_43.gif

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

In[60]:=

nqueens_44.gif

In[61]:=

nqueens_45.gif

In[62]:=

nqueens_46.gif

In[65]:=

nqueens_47.gif

In[68]:=

nqueens_48.gif

In[69]:=

nqueens_49.gif

Out[69]=

nqueens_50.gif

In[70]:=

nqueens_51.gif

Out[70]=

nqueens_52.gif

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]:=

nqueens_53.gif

nqueens_54.gif

Out[96]=

nqueens_55.gif

In[97]:=

nqueens_56.gif

Out[97]=

nqueens_57.gif

In[98]:=

nqueens_58.gif

Out[98]=

nqueens_59.gif

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:

nqueens_60.gif

nqueens_61.gif

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]:=

nqueens_62.gif

nqueens_63.gif

nqueens_64.gif

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:

nqueens_65.gif

nqueens_66.gif

We note that the attempted compilation does not succeed:

In[72]:=

nqueens_67.gif

nqueens_68.gif

nqueens_69.gif

Here is the uncompiled equivalent:

nqueens_70.gif

nqueens_71.gif

The uncompiled version is just as fast:

nqueens_72.gif

nqueens_73.gif

nqueens_74.gif

nqueens_75.gif

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]:=

nqueens_76.gif

Out[73]=

nqueens_77.gif

nqueens_78.gif

nqueens_79.gif

nqueens_80.gif

nqueens_81.gif

nqueens_82.gif

C code:

nqueens_83.gif

nqueens_84.gif

nqueens_85.gif

nqueens_86.gif

nqueens_87.gif

nqueens_88.gif

nqueens_89.gif

Java sees no problems:

In[74]:=

nqueens_90.gif

nqueens_91.gif

1
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
1073741824
2147483648
4294967296
8589934592
17179869184
34359738368
68719476736
137438953472
274877906944
549755813888
1099511627776
2199023255552
4398046511104
8796093022208
17592186044416
35184372088832
70368744177664
140737488355328
281474976710656
562949953421312
1125899906842624
2251799813685248
4503599627370496
9007199254740992
18014398509481984
36028797018963968
72057594037927936
144115188075855872
288230376151711744
576460752303423488
1152921504606846976
2305843009213693952
4611686018427387904
9223372036854775807

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

In[75]:=

nqueens_92.gif

Out[75]=

nqueens_93.gif

nqueens_94.gif

1
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
1073741824
2147483648
4294967296
8589934592
17179869184
34359738368
68719476736
137438953472
274877906944
549755813888
1099511627776
2199023255552
4398046511104
8796093022208
17592186044416
35184372088832
70368744177664
140737488355328
281474976710656
562949953421312
1125899906842624
2251799813685248
4503599627370496
9007199254740992
18014398509481984
36028797018963968
72057594037927936
144115188075855872
288230376151711744
576460752303423488
1152921504606846976
2305843009213693952
4611686018427387904

But Mathematica cannot compile it to C:

In[76]:=

nqueens_95.gif

Out[76]=

nqueens_96.gif

nqueens_97.gif

nqueens_98.gif

nqueens_99.gif

nqueens_100.gif

nqueens_101.gif

nqueens_102.gif

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]:=

nqueens_103.gif

nqueens_104.gif

nqueens_105.gif

nqueens_106.gif

nqueens_107.gif

nqueens_108.gif

1
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
1073741824
2147483648
4294967296
8589934592
17179869184
34359738368
68719476736
137438953472
274877906944
549755813888
1099511627776
2199023255552
4398046511104
8796093022208
17592186044416
35184372088832
70368744177664
140737488355328
281474976710656
562949953421312
1125899906842624
2251799813685248
4503599627370496
9007199254740992
18014398509481984
36028797018963968
72057594037927936
144115188075855872
288230376151711744
576460752303423488
1152921504606846976
2305843009213693952
4611686018427387904

Or bit shifts with C#:

In[78]:=

nqueens_109.gif

Out[78]=

nqueens_110.gif

nqueens_111.gif

1
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
1073741824
2147483648
4294967296
8589934592
17179869184
34359738368
68719476736
137438953472
274877906944
549755813888
1099511627776
2199023255552
4398046511104
8796093022208
17592186044416
35184372088832
70368744177664
140737488355328
281474976710656
562949953421312
1125899906842624
2251799813685248
4503599627370496
9007199254740992
18014398509481984
36028797018963968
72057594037927936
144115188075855872
288230376151711744
576460752303423488
1152921504606846976
2305843009213693952
4611686018427387904
Spikey Created with Wolfram Mathematica 8.0