import Data.Time.Clock (diffUTCTime, getCurrentTime)
import Control.Parallel
-- import Strategies
import Control.DeepSeq
import Control.Parallel.Strategies
import System.Environment
-- originally by Simon Marlow 03/2010.

main = do
  [n] <- fmap (fmap read) getArgs
  start <- getCurrentTime
  print (nqueens n)
  end <- getCurrentTime
  putStrLn (show (end `diffUTCTime` start) ++ " elapsed." )                   

nqueens :: Int -> Int
nqueens nq = length (pargen 0 [])
 where
    safe :: Int -> Int -> [Int] -> Bool
    safe x d []    = True
    safe x d (q:l) = x /= q && x /= q+d && x /= q-d && safe x (d+1) l

    gen :: [[Int]] -> [[Int]]
    gen bs = [ (q:b) | b <- bs, q <- [1..nq], safe q 1 b ]

    pargen :: Int -> [Int] -> [[Int]]
    pargen n b
       | n >= threshold = iterate gen [b] !! (nq - n)
       | otherwise      = concat bs 
       where bs = (map (pargen (n+1)) (gen [b])) 
                  `using` parList rdeepseq 
--                  `using` parList rnf

    threshold = 3