Done several tasks

[cses-programming-tasks.git] / app / cses1624.hs

diff --git a/app/cses1624.hs b/app/cses1624.hs
new file mode 100644 (file)
index 0000000..d984ffe
--- /dev/null
+++ b/app/cses1624.hs
@@ -0,0 +1,38 @@
+import Data.List
+import qualified Data.Set as S
+import Control.Monad
+
+data Queen = Queen Int Int -- row, column
+  deriving (Show, Eq, Ord)
+
+main :: IO ()
+main = do
+  text <- getContents
+  let grid = mkGrid text
+  -- print grid
+  let solutions = solve grid
+  print $ length solutions
+
+solve :: S.Set Queen -> [S.Set Queen]
+solve forbiddens =
+  do cols <- permutations [0..7]
+     let queens = S.fromList [uncurry Queen p | p <- zip [0..7] cols]
+     guard $ S.null $ S.intersection queens forbiddens
+     let posDiagonals = S.map posDiagonalOf queens
+     let negDiagonals = S.map negDiagonalOf queens
+     guard $ S.size posDiagonals == 8
+     guard $ S.size negDiagonals == 8
+     return queens
+
+posDiagonalOf, negDiagonalOf :: Queen -> Int
+posDiagonalOf (Queen r c) = c - r
+negDiagonalOf (Queen r c) = c + r
+
+mkGrid :: String -> S.Set Queen
+mkGrid text = S.fromList forbiddens
+  where rows = lines text
+        r = length rows - 1
+        c = (length $ head rows) - 1
+        forbiddens = [Queen i j | i <- [0..r], j <- [0..c], rows !! i !! j == '*' ]
+
+