obdd 0.3.2 → 0.3.3

raw patch · 3 files changed

+143/−6 lines, 3 filesdep +obdddep ~basedep ~containersPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependencies added: obdd

Dependency ranges changed: base, containers

API changes (from Hackage documentation)

Files

• examples/Placement.hs +49/−0
• examples/Queens.hs +77/−0
• obdd.cabal +17/−6

@@ -0,0 +1,49 @@+{-+Auf wie viele Weisen kann man Spielsteine auf ein 3 x 10-Spielbrett setzen, +sodass keine zwei Steine horizontal, vertikal oder diagonal benachbart sind?++(Quelle: Preisaufgabe bei LSGM-Wochenendseminar 2011 in Bennewitz+http://www.lsgm.de/tiki-index.php?page=Seminare.2011-09)++BUILD:  ghc --make Placement+RUN  :  ./Placement 3 10+-}++import OBDD (OBDD)+import qualified OBDD++import Control.Monad ( guard, forM_ )+import System.Environment ( getArgs )+import qualified Data.Set ++type Position = (Int,Int)++positions :: Int -> Int -> [ Position ]+positions width height = do +    a <- [ 1 .. width  ]+    b <- [ 1 .. height ]+    return (a,b)++adjacent :: Position -> Position -> Bool+adjacent (a,b) (c,d) = +    abs (a-c) <= 1 && abs (b-d) <= 1+  +main = do+    args <- getArgs+    case map read args :: [Int] of+        [] -> mainf 3 10+        [ width, height ] -> mainf width height++mainf width height = do+    let ps = positions width height+    print $ OBDD.number_of_models ( Data.Set.fromList ps )+          $ OBDD.and $ do+           p <- ps+           q <- ps+           guard $ p < q +           guard $ adjacent p q+           return $ OBDD.or [ OBDD.unit p False, OBDD.unit q False ]++++

@@ -0,0 +1,77 @@+{-+the N Queens problem. The propositional variables+correspond to the positions on the board.+It shows how to construct an OBDD+and how to check some of its properties.+It also shows that the implementation is not terribly efficient.+It computes the number of solutions for board size 8+(the answer is: 92) in approx. 1.6 seconds on my machine.++BUILD:  ghc -O2 Queens+RUN  :  ./Queens 8+-}++import OBDD (OBDD)+import qualified OBDD+import qualified OBDD.Data (toDot)++import Control.Monad ( guard )+import System.Environment ( getArgs )+import qualified Data.Set ++type Position = (Int,Int)++positions :: Int -> [ Position ]+positions n = do +    a <- [ 1 .. n ]+    b <- [ 1 .. n ]+    return (a,b)++threatens :: Position -> Position -> Bool+threatens (a,b) (c,d) = +       a == c     -- same column+    || b == d     -- same row+    || a+b == c+d -- same diagonal+    || a-b == c-d -- same antidiagonal++board :: Int -> OBDD Position+board n = OBDD.and +    [ each_column_is_occupied n+    , no_threats n+    ]++each_column_is_occupied n = OBDD.and $ do+    a <- [ 1 .. n ]+    return $ OBDD.or $ do+        b <- [ 1 .. n ]+        return $ OBDD.unit (a,b) True++no_threats n = OBDD.and $ do+    p <- positions n+    return $ OBDD.and $ do+        q <- positions n+        guard $ p < q+        guard $ threatens p q+        return $ OBDD.or [ OBDD.unit p False, OBDD.unit q False ]++main = do+    args <- getArgs+    case map read args :: [Int] of+        [] -> mainf 8+        [arg] -> mainf arg++mainf n = do+    let d :: OBDD Position+        d = board n++    print $ OBDD.size d+    print $ OBDD.satisfiable d++    print $ OBDD.number_of_models +          ( Data.Set.fromList $ positions n )+          d++    m <- OBDD.some_model d+    print m++    -- writeFile "Queens.dot" $ OBDD.Data.toDot d

@@ -1,6 +1,6 @@ Name:                obdd-Version:             0.3.2-Cabal-Version:       >= 1.6+Version:             0.3.3+Cabal-Version:       >= 1.8 Build-type: Simple Synopsis:            Ordered Reduced Binary Decision Diagrams Description:         Construct, combine and query OBDDs;@@ -12,16 +12,27 @@ Maintainer:          Johannes Waldmann Homepage:	     https://github.com/jwaldmann/haskell-obdd -library+Source-Repository head+    Type: git+    Location: git://github.com/jwaldmann/haskell-obdd.git++Library     Build-Depends:       base==4.*, random, mtl, containers>=0.5, array     Hs-Source-Dirs:	     src     Exposed-Modules:     OBDD OBDD.Data OBDD.Make OBDD.Operation OBDD.Property     Other-Modules:	     OBDD.IntIntMap, OBDD.VarIntIntMap     ghc-options: -funbox-strict-fields +test-suite obdd-placement+    Hs-Source-Dirs : examples+    Type: exitcode-stdio-1.0+    Main-Is: Placement.hs+    Build-Depends: base, containers, obdd -Source-Repository head-    Type: git-    Location: git://github.com/jwaldmann/haskell-obdd.git+test-suite obdd-queens+    Hs-Source-Dirs : examples+    Type: exitcode-stdio-1.0+    Main-Is: Queens.hs+    Build-Depends: base, containers, obdd