4 ms·
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
by user2994cb 10y ago
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 10y agoActually, 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 10y agoThat should be "q s [] = [s]", otherwise you get 92 copies of the empty list.