On: N-queen puzzle in 4 lines of Scala

[user2994cb]

Well, here's a fairly compact Haskell function that should be reasonably efficient (no fancy stuff mind):

  queens n = q n n [[]] where
   q 0 m ss = ss
   q n m ss = q (n-1) m (concatMap (\s->(map (:s)(filter (f 1 s) [0..m-1]))) ss)
   f _ [] a = True
   f n (b:s) a = a /= b && a /= b+n && a /= b-n && f (n+1) s a
  main = print $ queens 8

[user2994cb → user2994cb]

Actually, this is better (and no less clear):

  import Data.List
  queens n = q [] [0..n-1] where
   q s [] = [[]]
   q s as = concatMap (\a -> q (a:s) (delete a as)) (filter (f 1 s) as)
   f _ [] a = True
   f n (b:s) a = a /= b+n && a /= b-n && f (n+1) s a
  main = print $ length (queens 8)

Undoubtedly functional, the question is whether it is improved eg. by using folds instead of explicit recursion, or replacing concatMap with monadic join.

[user2994cb → user2994cb]

That should be "q s [] = [s]", otherwise you get 92 copies of the empty list.