## 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
``````

1. Derek Elkins says:

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. [...] Basic Stuff: The Writer Monad Filed under: Uncategorized — cdsmith @ 11:47 am In this post, Magnus Therning gives a number of solutions to the n-queens problem in Haskell.  The problem [...]

3. dtldarek says:

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. [...] magnus blog – N-Queens solution, relatively long, code translated from Standard ML, uses exceptions. There is another solution (in comments), 147bytes long [...]