I love the Haskell version of this because non-deterministic computation via (depth-first) search is embodied by the list monad! The preliminaries are that we

I love the Haskell version of this because non-deterministic computation via (depth-first) search is embodied by the list monad! The preliminaries are that we represent a board position containing N queens on an NxN board by a list of row positions in each of N columns. newtype Board = Board [Int] deriving ( Eq, Show ) emptySolution = Board [] Then, given any particular NxN board with M queens in first M columns that is a solution to M-queens, we can generate the list of possible new boards with (M+1) queens. We try all possible row positions for the new column excepting the rows where queens already exist. attempts :: Int -> Board -> [Board] attempts n (Board queens) = map (\r -> Board (r : queens)) ([0 .. n - 1] \\ queens) And we prune out the ones where the new queen has a diagonal conflict. valid :: Board -> Bool valid (Board []) = True valid (Board (q:cols)) = and $ map (\(n, c) -> abs (q - c) /= n) (zip [1..] cols) -- this is a bit clever, as we walk back through -- the previous columns, if the absolute difference -- between the row position of the new queen and -- an old queen is ever the count of the column -- we're in, then it must be in a diagonal line -- from the new queen All of the above is pretty standard, but the fun part is using the list monad to structure a search. Each bind (<-) in do-notation can be thought of as non-deterministically setting a particular choice from the right side to the name on the left queens :: Int -> [Board] queens n = search n [emptySolution] where search 0 boards = boards -- no more queens to add search k boards = do board <- search (k - 1) boards -- find a smaller solution filter valid (attempts board) -- try all possible extensions, -- remove the bad ones >>> length (queens 8) 92 Finally, the pattern of `search` is really common, it's just iterating the generation of attempted solutions. We can write it with the built-in function `Control.Monad.foldM` or another common utility combinator, `iterateM` iterateM :: Monad m => (a -> m a) -> a -> [m a] iterateM f x = iterate (f =<<) (return x) queens n = iterateM (filter valid . attempts n) emptySolution !! n Finally, it's worth noting that there's nothing special about the list monad's implementation. It's easy to rewrite it without using the typeclass. -- this is the list monad definition instance Monad [] where return a = [a] xs >>= f = concat (map f xs) iterateList :: (a -> [a]) -> a -> [[a]] iterateList f x = iterate (concat . map f) [x]