import Control.Parallel.Strategies

maxDepth :: Int
maxDepth = 20

search :: (NFData solution, NFData partial) =>
           Int
        -> (partial -> Maybe solution)
        -> (partial -> [partial])
        -> partial
        -> [solution]
search depth finished extend current
    | Just sol <- finished current = [sol]
    | otherwise = cmap (search (depth+1) finished extend) (extend current)
    where cmap f = if depth > maxDepth then concatMap f
                   else concat . parMap rseq f

type Row = Int
type Col = Int

queens :: Int -> [[(Row, Col)]]
queens n = search 1 goal extend []
    where goal sol = if length sol >= n
                     then Just sol
                     else Nothing
          extend ps = let curRow = length ps
                      in [(curRow, pos):ps | pos<-[1..n], safe (curRow, pos) ps]
          safe (r, c) ps = not . or $ [c == cc || abs (r - rr) == abs (c - cc)
                                    | (rr, cc) <- ps ]

main :: IO ()
main = print $ length (queens 13)