The N-Queens Problem Haskell

This is a real toughy! I have to tell you I’ve cheated a bit to get the solution of this one! (It were my first 2 hours of real Haskell programming, so be nice! :))

The problem

A queen in this problem can go infinite steps forwards, backwards and diagonally. We need to place N queens on a NxN board so that no queen can attack another queen. You know how they can get…

This is a problem that is very well suited to be solved with streams. Streams are available in a number of programming languages like Scheme or Haskell. As this was an excericse for my Haskell course I’m obviously going for Haskell here.

The Solution

First step: Data representation

We can represent a list of all possible positions as [[(Int, Int)]] where the first value would be the row and the second one the column. But there is a small trick possible here. We know that the array is indexed from 1 to N. Every column on our board will have exactly one queen (if not there are 2 or more queens on one row and they will fight). This means we can have the column for each queen defined in an implicit manner, namely the array position. So we will represent our queens this way: [[Int]].

Second step: What to filter..?

We will need to generate a list of all possible rowpositions for each column. For a 2×2 board this would be:

[[1,1],[1,2],[2,1],[2,2]]

But we can immediatly see that [2,2] and [1,1] are no valid solutions because queens can attack eachother. This means that every value in the list must be unique between 1 and N. How do we generate these permutations for the list [1..N] ?

generateSolutions' :: Int -> [[Int]]
generateSolutions' 0 = [[]]
generateSolutions' n = permutations [1..n]

Third step: How to filter?

We’ve already taken only the permutations, this means that we never haveĀ  a queen on the same row/column. So we only need to filter out the lists that contain queens that are on the same diagonal.

When are two queens on a diagonal?

This happens when the distance between two columns and two rows is the same. You can draw this on a paper if you like. In the image below you can see that the distance between the rows of A and B is 1. The distance between the columns of A and B is 3.

To determine wether these queens are on a diagonal or not we can do just that:

sameDiagonal (a,b) (x,y) = abs (a - x) == abs (b - y)

But this means we we need to pass couples into the function, which we don’t have. We only have rowindices. So what we can do here is pass the first queen as a paramter and zip the rest of the list with [1..]. This gives us the column distance right away! So conceptually speaking we would get a list [(columnDistance, rowIndex)] for all queens except the head.

duplicateDiagonals q qs = any
                          (\(columnDistance, row) -> abs (row - q) == columnDistance)
                          $ zip [1..] qs

This will first of all zip with the infinite list, and then we will apply the predicate function to each element of that list. It just check wether the row distance between both queens is equal to the columndistance. This is pretty neat, isn’t it?
queens

Putting it all together

Now we have all the pieces we need to filter our list.

generateSolutions' :: Int -> [[Int]]
generateSolutions' 0 = [[]]
generateSolutions' n = permutations [1..n]

duplicateDiagonals :: Int -> [Int] -> Bool
duplicateDiagonals q qs = any (\(columnDistance, row) -> abs (row - q) == columnDistance) $ zip [1..] qs

test :: [Int] -> Bool
test [] = True
test (q:qs) = not (duplicateDiagonals q qs) &&test qs

Thanks for reading, Christophe

Advertisements