Try this Queens.hs module Main where main = print $ queens 10 boardSize = 10 queens 0 = [[]] queens n = [ x : y | y <- queens (n-1), x <- [1..boardSize], safe x y 1] where safe x [] n = True safe x (c:y) n = and [ x /= c , x /= c + n , x /= c - n , safe x y (n+1)] Copied from somebody else. -----Original Message----- From: haskell-cafe-bounces@haskell.org [mailto:haskell-cafe-bounces@haskell.org]On Behalf Of David Sankel Sent: Thursday, March 04, 2004 12:19 PM To: haskell-cafe@haskell.org Subject: [Haskell-cafe] Fun with Haskell, runST, MArray, and a few queens. Hello Enthusiasts, My fiancee was assigned the n-queens problem in her Data Structures class. It was a study in backtracking. For those unfamiliar with the problem: one is given a grid of n x n. Return a grid with n queens on it where no queen can be attacked by another. Anyway, I decided to try an implementation in Haskell (as I often do with her assignments). Instead of the imperative approach (adding a queen and then getting rid of it), I opted for a functional one (the grid is passed to recursive calls, etc.). The interesting thing about this assignment is the runtimes: (n=10) ghc 58.749s ghc -O 12.580s javac 1.088s The Haskell version takes significantly longer (and it gets worse for larger inputs). So it seems that imperative algorithms are much better for certain problems. Since Haskell is supposed to have the ability to run imperative algorithms, I was wondering if any of you could explain how runST and MArray could be used to solve this problem (or is there a better way?). I am also interested in the run times you get with these two implementations of the n-queens problem. David