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
![[Digg]](http://therning.org/magnus/wp-content/plugins/bookmarkify/digg.png)
![[Reddit]](http://therning.org/magnus/wp-content/plugins/bookmarkify/reddit.png)
You can implement threatens just like it is in the SML or just like you would in C-style languages.
[...] 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 [...]
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
[...] magnus blog – N-Queens solution, relatively long, code translated from Standard ML, uses exceptions. There is another solution (in comments), 147bytes long [...]