If you’re reading this blog, you’re most likely familiar with the famous N-queens problem.
If not, here it is!

The eight queens puzzle is the problem of placing eight chessqueens on an 8×8 chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens problem of placing n non-attacking queens on an n×n chessboard, for which solutions exist for all natural numbers n with the exception of n=2 and n=3

This problem isn’t too difficult if you have knowledge in constraint programming.
However, solving this in a functional programming language could be more interesting. I chose Haskell as the language of choice because it seemed suitable to solve this problem.

The algorithm is the same – we just take the permutations of 1..n as the column for the n-consecutive rows and remove all the illegal ones.

In Haskell, we can utilize filter. As I was writing the code, it made me realize how easy it was to translate pseudo-code into actual code in Haskell.

This algorithm only guarantees that two queens won’t be on the same row or column though. How do we check diagonals?
It’s quite trivial:

This is not the best solution as it is quite inefficient with a runtime efficiecny of O(n^2). I know in OCaml, I could utilize mapi and fold with arrays. These functions were not legal in Haskell so I couldn’t use them.

Anyway, my lack of knowledge in Haskell was the main reason why I gave up and did some research online.

I found some elegant solutions written by Haskell experts:
The idea of using Date.List’s permutation and breadth of the search tree is extremely elegant (but the code is very difficult to understand).

Disclaimer: I did not write the code below. I just had to share it because of its sheer brilliance.

This solution uses permutations that generate some unique horizontal/vertical position for every queen. This means we only need to check the diagonals!
[0..] places each queen on her own row and then it filters out all the results where 2+ queens are on the same diagnoal. And of course [0..n-1] places each queen on her own column.

It’s less efficient (because of some prefix-filtering issue) but look how short and easy to understand the code is!

Lesson learned:
Functional programming is cool.