N-Queens in Haskell

After reading the chapter on options, exceptions, and failure continuations from Programming in Standard ML I thought spending a few minutes on translating the code to Haskell might be fun.

I should start with a disclaimer, I’ve never coded in SML, never even read any article or book about the language or even looked at code written in it. Nevertheless I seem to have produced runnable, and presumably correct, code in a fairly short amount of time. I’ve tried to stay as close to the original code as possible, there are undoubtably better and more effective way of writing the same code in Haskell. Feel free to provide comments with improvements :-)

First the representation of the board:

data Board = Board Int Int Int [(Int, Int)]
    | NoBoard
    deriving (Show)

Then some functions to manipulate a board:

new n = Board n 1 0 []

size (Board n _ _ _) = n

complete (Board n _ k _) = k == n

positions (Board _ _ _ qs) = qs

place (Board n i k qs) j = Board n (i + 1) (k + 1) ( (i, j) : qs)

threatens (i, j) (i', j')
    | i == i' = True
    | j == j' = True
    | i + j == i' + j' = True
    | i - j == i' - j' = True
    | otherwise = False

conflicts q [] = False
conflicts q (q':qs) = threatens q q' || conflicts q qs

safe (Board _ i _ qs) j = not $ conflicts (i, j) qs

These are all straight-forward translations, within minimal “haskell-ifications”.

The first solution using Maybe and explicit checks for failure:

addqueenM bd =
    let try j = if j > size bd
            then Nothing
            else if safe bd j
                then case addqueenM (place bd j) of
                    Nothing -> try $ j + 1
                    Just bd' -> Just bd'
                else try $ j + 1
    in
        if complete bd
            then Just bd
            else try 1

queensM = addqueenM . new

The second uses exceptions to avoid the explicit check (note that I’ve imported Control.Exception as CE to avoid the clash with Prelude‘s catch; see the documentation of catch if you don’t know why that’s necessary):

addqueenE bd =
    let try j = if j > size bd
            then error "no more space on board"
            else if safe bd j
                then CE.catch (addqueenE (place bd j)) (\ e -> try $ j + 1)
                else try $ j + 1
    in
        if complete bd
            then return bd
            else try 1

queensE n = CE.catch (addqueenE $ new n) (\ e -> return NoBoard)

The last translated version uses an explicit failure continuation to avoid both checking results and dealing with exceptions:

addqueenC bd fc =
    let try j = if j > size bd
            then fc
            else if safe bd j
                then addqueenC (place bd j) (try $ j + 1)
                else try $ j + 1
    in
        if complete bd
            then Just bd
            else try 1

queensC n = addqueenC (new n) Nothing

So far so good, but since this is Haskell, what about monads? :-) Minor changes results in the following somewhat general version of addqueenX:

addqueenH bd =
    let try j = if j > size bd
            then mzero
            else if safe bd j
                then addqueenH (place bd j) `mplus` (try $ j + 1)
                else try $ j + 1
    in
        if complete bd
            then return bd
            else try 1

With that it’s possible to lean on the type system to get something that’s similar to queenM from above:

queensHM :: Int -> Maybe Board
queensHM = addqueenH . new

It’s also easy to write a version that calculates all solutions given the size of the board:

queensHL :: Int -> [Board]
queensHL = addqueenH . new
Share

4 Comments

  1. You can implement threatens just like it is in the SML or just like you would in C-style languages.

    threatens (i, j) (i', j') = i == i' || j == j' || i+j == i'+j' || i-j == i'-j'
    
  2. Pingback: Some Basic Stuff: The Writer Monad « Sententia cdsmithus

  3. try this: (147 bytes ^^) h l n x=if x==0 then[l]else do y<-[1..n];if null[0|(p,q)<-l,or[q==y,p+q==x+y,p-q==q-y]] then h((x,y):l)n$x-1 else[] main=putStr$show$head$h[]8 8

  4. Pingback: Haskell, Eight Queens puzzle « Komap’s Blog

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>