The queens must be placed on the board so 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 researched algorithms to solve the 8-queens puzzle before I came up with this attempt to implement one.
For the algorithm, it is clear that per column, only one queen can be placed. Furthermore, 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. Finally, the remaining 46 solutions are found by just mirroring the board.
As you all know, a different way to decompose the problem is being used in functional programming. 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 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 in 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.
One of the most important goals in designing Haskell was to make statements very compact. Thus, for example, Haskell uses the space character ” ” to notate the application.
This leads to very compact programs. My personal summary is that I am looking forward to seeing 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 to 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. So, for example, 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 is an example for an equivalence transform of a list comprehension into a composition of map and filter. Unfortunately, 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 map and filter function application takes two passes. However, if one does the composition incorrectly, 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, resulting in a 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. So I downloaded the V8 Javascript engine and compiled it with the “sample=shell” option. So 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. Instead, the focus of the solutions is on readability and experimentation with functional programming concepts. However, I currently work as a performance engineer, and therefore I need to get some insights on execution time considerations.
Add Comment