SHOW:
|
|
- or go back to the newest paste.
| 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 ] |
| 29 | + | | (rr, cc) <- ps ] |
| 30 | ||
| 31 | main :: IO () | |
| 32 | main = print $ length (queens 13) |
