app/cses1624.hs

   1 import Data.List
   2 import qualified Data.Set as S
   3 import Control.Monad
   4
   5 data Queen = Queen Int Int -- row, column
   6   deriving (Show, Eq, Ord)
   7
   8 main :: IO ()
   9 main = do
  10   text <- getContents
  11   let grid = mkGrid text
  12   -- print grid
  13   let solutions = solve grid
  14   print $ length solutions
  15
  16 solve :: S.Set Queen -> [S.Set Queen]
  17 solve forbiddens =
  18   do cols <- permutations [0..7]
  19      let queens = S.fromList [uncurry Queen p | p <- zip [0..7] cols]
  20      guard $ S.null $ S.intersection queens forbiddens
  21      let posDiagonals = S.map posDiagonalOf queens
  22      let negDiagonals = S.map negDiagonalOf queens
  23      guard $ S.size posDiagonals == 8
  24      guard $ S.size negDiagonals == 8
  25      return queens
  26
  27 posDiagonalOf, negDiagonalOf :: Queen -> Int
  28 posDiagonalOf (Queen r c) = c - r
  29 negDiagonalOf (Queen r c) = c + r
  30
  31 mkGrid :: String -> S.Set Queen
  32 mkGrid text = S.fromList forbiddens
  33   where rows = lines text
  34         r = length rows - 1
  35         c = (length $ head rows) - 1
  36         forbiddens = [Queen i j | i <- [0..r], j <- [0..c], rows !! i !! j == '*' ]
  37
  38