Guest User

parallelized n-queens

a guest
Jun 22nd, 2014
222
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import Control.Parallel.Strategies
  2.  
  3. maxDepth :: Int
  4. maxDepth = 20
  5.  
  6. search :: (NFData solution, NFData partial) =>
  7.            Int
  8.         -> (partial -> Maybe solution)
  9.         -> (partial -> [partial])
  10.         -> partial
  11.         -> [solution]
  12. search depth finished extend current
  13.     | Just sol <- finished current = [sol]
  14.     | otherwise = cmap (search (depth+1) finished extend) (extend current)
  15.     where cmap f = if depth > maxDepth then concatMap f
  16.                    else concat . parMap rseq f
  17.  
  18. type Row = Int
  19. type Col = Int
  20.  
  21. queens :: Int -> [[(Row, Col)]]
  22. queens n = search 1 goal extend []
  23.     where goal sol = if length sol >= n
  24.                      then Just sol
  25.                      else Nothing
  26.           extend ps = let curRow = length ps
  27.                       in [(curRow, pos):ps | pos<-[1..n], safe (curRow, pos) ps]
  28.           safe (r, c) ps = not . or $ [c == cc || abs (r - rr) == abs (c - cc)
  29.                                       | (rr, cc) <- ps ]
  30.  
  31. main :: IO ()
  32. main = print $ length (queens 13)
RAW Paste Data