The queens must be placed on the board in such a way that no two queens threaten each other in the backend testing process. Thus, a solution requires that no two queens share the same column, row, or diagonal. For the implementations below the generalized n-queens problem has been used.
Implementations using functional programming
I present the implementations of the n-queens puzzle in the order I have created them.
Common Lisp
The Lisp solution is the first I present here since I started learning functional programming languages with Lisp. I did some research on algorithms to solve the 8-queens puzzle before I cam up with this attempt to implement one. For the algorithm, it is clear that per column only one queen can be placed. Once understanding the symmetric properties of the chessboard it became clear that the search space can be easily split in half using only the first half of the first column. Then only 46 of the 8-queens puzzle solutions are found. The remaining 46 solutions are found by just mirroring the board.
As you all know in functional programming a different way to decompose the problem is being used. In the beginning, it was hard for me to wrap my head around that. As always in similar situations I started drawing diagrams and once I understood that map, filter, and folder are the basic building blocks I figured it out.
Haskell
My first contact with Haskell was really an eye-opener. When it comes to type systems I experience people to get very opinionated. Either you belong to the one (right) fraction or you will be considered an idiot! While learning Haskell I experienced the first time that this topic has shades of grey. In Haskell the types used in your function help you to argue (think) about your program. The nice side is that the type system does not get into your way. Haskell has type detection so you do not need to write all that type related boilerplate code you have in other strongly typed programming languages. And Haskell provides type classes so you do not need Generics. It is said that one of the most important goals in designing Haskell was to make statements very compact. For example, Haskell uses the space character ” ” to notate application. This leads to very compact programs. My personal summary is that I am looking forward to seeing a lot more of Haskell in the future.
Erlang
Having deep roots in Prolog Erlang has no static typing. The current hype concerning Erlang is about its strong support for parallel computing. I did not use this feature in the following solution. As you can see the Erlang and Haskell solutions are very similar and it is easy to transform one into the other.
Python
Python has elegant support for List Comprehensions as well. Consequently, there is not a huge difference between the Haskell and Erlang solutions besides that the Python solution is a little bit more verbose.
Javascript
Javascript implementations that follow the Ecma 262 Standard do not support List Comprehensions. For example, the V8 Javascript engine follows this 1999 standard very closely. But there is considerable hope that with the Harmony Project and the 6th edition of the standard the goodness implemented in Javascript 1.7 like List Comprehensions will be taken up.
Haskell has strong support for mathematical reasoning about programs. So a side-effect of learning Haskell was that I also learned how to transform one expression into another. For example, a list comprehension can be expressed as a composition of map and filter.
[ x * x | x \leftarrow [1..5], odd \: x] \equiv (map \: square \: \circ \: filter \: odd)[1..5]
Above an example for an equivalence transform of a list comprehension into a composition of map and filter. The function composed of map and filter is much less readable than the nested list comprehension.
The list comprehension is constructed in one pass whereas the application of the map and filter function takes two passes. However if one does the composition in the wrong order he is in deep trouble since he gets a program that still computes the correct solution but this tiny little difference has a huge impact on performance. In the 8-queens solution, the queens_intern function is called nine times. If the order is wrong it is called 20 million times which results in a factor 1000x impact on execution time. I think these are strong arguments in favor of using list comprehensions.
The underscore.js library provides the basic building blocks like map, filter, reduce which I needed. I downloaded the V8 Javascript engine and compiled it with the “sample=shell” option. Now I can run it on my machine “time shell underscore.js queens_map_filter.js”.
Finally, execution times
The solutions for the n-queens puzzle discussed above have not been optimized for performance. The focus of the solutions is on readability and experimentation with functional programming concepts. I currently work as a performance engineer and therefore I need to get some insights on execution time considerations, too.
