# [Programming] N-queens problem using Haskell

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 puzzleis 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 generalof placingnqueens problemnnon-attacking queens on ann×nchessboard, for which solutions exist for all natural numbersnwith the exception ofn=2 andn=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.

1 2 |
queens :: Int -> [[Int]] queens n = filter (good . zip [1..]) $ permutations [1..n] |

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:

1 2 3 4 |
good :: [(Int, Int)] -> Bool good [] = True good (x:xs) = all (good' x) xs && good xs where good' (x1,y1) (x2,y2) = x1+y1 /= x2+y2 && x1-y1 /= x2-y2 |

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.

1 2 3 4 5 6 |
import Data.List (nub, permutations) check f = length . nub . zipWith f [0..] generate n = filter (\x -> check (+) x == n && check (-) x == n) $ permutations [0..n-1] main = print $ generate 8 |

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.