[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 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.
|
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.
