Name: set-cover Version: 0.1 License: BSD3 License-File: LICENSE Author: Henning Thielemann, Helmut Podhaisky Maintainer: Henning Thielemann Homepage: http://hub.darcs.net/thielema/set-cover/ Category: Math, Algorithms Synopsis: Solve exact set cover problems like Sudoku, 8 Queens, Soma Cube, Tetris Cube Description: Solver for exact set cover problems. Included examples: Sudoku, Nonogram, 8 Queens, Domino tiling, Mastermind, Alphametics, Soma Cube, Tetris Cube, Cube of L's, Logika's Baumeister puzzle, Lonpos pyramid, Conway's puzzle. The generic algorithm allows to choose between slow but flexible @Set@ from @containers@ package and fast but cumbersome bitvectors. . For getting familiar with the package I propose to study the Queen8 example along with "Math.SetCover.Exact". . The Sudoku and Nonogram examples also demonstrate how to interpret the set-cover solution in a human-friendly way. . Build examples with @cabal install -fbuildExamples@. . The package needs only Haskell 98. There is also an experimental implementation using LLVM and @knead@. Do not rely on that interface in released packages. Tested-With: GHC==7.4.2, GHC==7.6.3, GHC==7.8.2 Cabal-Version: >=1.8 Build-Type: Simple Extra-Source-Files: Changes.md Makefile Flag buildExamples Description: Build example executables Default: False Flag llvm Description: Enable efficient signal processing using LLVM Manual: True Default: False Source-Repository this Tag: 0.1 Type: darcs Location: http://hub.darcs.net/thielema/set-cover/ Source-Repository head Type: darcs Location: http://hub.darcs.net/thielema/set-cover/ Library Build-Depends: psqueues >=0.2 && <0.3, enummapset >=0.1 && <0.7, transformers >=0.2 && <0.6, array >=0.4 && <0.6, containers >=0.4 && <0.7, non-empty >=0.2 && <0.4, semigroups >=0.1 && <1.0, utility-ht >=0.0.12 && <0.1, prelude-compat ==0.*, base >=4 && <5 GHC-Options: -Wall Hs-Source-Dirs: src Exposed-Modules: Math.SetCover.Bit Math.SetCover.BitSet Math.SetCover.BitPosition Math.SetCover.BitPriorityQueue Math.SetCover.Queue Math.SetCover.Exact Math.SetCover.Exact.Priority Math.SetCover.Exact.UArray Math.SetCover.Cuboid Other-Modules: Math.SetCover.BitMap Math.SetCover.EnumMap Math.SetCover.Queue.Set Math.SetCover.Queue.Map Math.SetCover.Queue.Bit Math.SetCover.Queue.BitPriorityQueue Math.SetCover.Exact.Block If flag(llvm) Build-Depends: knead >=0.4 && <0.5, llvm-extra >=0.8 && <0.9, llvm-tf >=3.1.1 && <3.2, tfp >=1.0 && <1.1, comfort-array >=0.3 && <0.5, storable-endian >=0.2.6 && <0.3, bool8 >=0.0 && <0.1, lazyio >=0.1 && <0.2 Exposed-Modules: Math.SetCover.Exact.Knead Math.SetCover.Exact.Knead.Vector Math.SetCover.Exact.Knead.Saturated Other-Modules: Math.SetCover.Exact.Knead.Symbolic Test-Suite set-cover-test Type: exitcode-stdio-1.0 Build-Depends: set-cover, transformers >=0.2 && <0.6, enummapset, containers, array >=0.1 && <0.6, utility-ht, QuickCheck >=2.5 && <3.0, base Main-Is: Test.hs Hs-Source-Dirs: test, example If flag(llvm) Hs-Source-Dirs: test/knead Else Hs-Source-Dirs: test/plain GHC-Options: -Wall Other-Modules: Mastermind.Test Mastermind.Guess Mastermind.Utility Test.Knead Test.Utility Executable tetris-cube If flag(buildExamples) Build-Depends: haha >=0.3.1 && <0.4, pooled-io >=0.0 && <0.1, set-cover, containers, utility-ht, base Else Buildable: False GHC-Options: -Wall -rtsopts -threaded Hs-Source-Dirs: example Main-Is: TetrisCube.hs Other-Modules: Utility Executable soma-cube If flag(buildExamples) Build-Depends: set-cover, containers, utility-ht, base Else Buildable: False GHC-Options: -Wall -rtsopts -threaded Hs-Source-Dirs: example Main-Is: Soma.hs Executable queen8 If flag(buildExamples) Build-Depends: set-cover, containers, array >=0.1 && <0.6, utility-ht, base Else Buildable: False GHC-Options: -Wall -rtsopts -threaded Hs-Source-Dirs: example Main-Is: Queen8.hs Executable sudoku-setcover If flag(buildExamples) Build-Depends: set-cover, haha >=0.3.1 && <0.4, random >=1.0 && <1.2, transformers >=0.2 && <0.6, containers, array >=0.1 && <0.6, utility-ht, base Else Buildable: False GHC-Options: -Wall -rtsopts -threaded Hs-Source-Dirs: example Main-Is: Sudoku.hs Other-Modules: Random, Mastermind.Utility Executable lcube If flag(buildExamples) Build-Depends: set-cover, pooled-io >=0.0 && <0.1, containers, utility-ht, base Else Buildable: False GHC-Options: -Wall -rtsopts -threaded Hs-Source-Dirs: example Main-Is: LCube.hs Other-Modules: Utility Executable baumeister If flag(buildExamples) Build-Depends: set-cover, containers, utility-ht, base Else Buildable: False GHC-Options: -Wall -rtsopts -threaded Hs-Source-Dirs: example Main-Is: Baumeister.hs Other-Modules: Utility Executable lonpos-pyramid If flag(buildExamples) Build-Depends: set-cover, containers, utility-ht, base Else Buildable: False GHC-Options: -Wall -rtsopts -threaded Hs-Source-Dirs: example Main-Is: LonposPyramid.hs Other-Modules: Utility Executable alphametics If flag(buildExamples) Build-Depends: set-cover, non-empty >=0.2 && <0.4, transformers >=0.2 && <0.6, containers, utility-ht, base Else Buildable: False GHC-Options: -Wall -rtsopts -threaded Hs-Source-Dirs: example Main-Is: Alphametics.hs Executable domino If flag(buildExamples) Build-Depends: set-cover, unicode >=0.0 && <0.1, containers, semigroups, utility-ht, base Else Buildable: False GHC-Options: -Wall -rtsopts -threaded Hs-Source-Dirs: example Main-Is: Domino.hs Executable nonogram If flag(buildExamples) Build-Depends: set-cover, non-empty >=0.2 && <0.4, psqueues, enummapset, containers, utility-ht, base Else Buildable: False GHC-Options: -Wall Hs-Source-Dirs: example Main-Is: Nonogram.hs Other-Modules: Nonogram.Example Nonogram.Encoding.Combinatoric Nonogram.Encoding.BlackWhite Nonogram.Encoding.Plug Nonogram.Encoding.Naive Nonogram.Base Executable mastermind-setcover If flag(buildExamples) Build-Depends: set-cover, random >=1.0 && <1.2, transformers >=0.2 && <0.6, enummapset, containers, array >=0.1 && <0.6, utility-ht, base Else Buildable: False GHC-Options: -Wall Hs-Source-Dirs: example Main-Is: Mastermind.hs Other-Modules: Mastermind.Utility Mastermind.Guess Mastermind.Distinguish Mastermind.Example Random Executable mastermind-knead If flag(buildExamples) && flag(llvm) GHC-Prof-Options: -rtsopts -auto-all Build-Depends: set-cover, haha >=0.3.1 && <0.4, random >=1.0 && <1.2, lazyio, transformers >=0.2 && <0.6, enummapset, containers, array >=0.1 && <0.6, utility-ht, base Else Buildable: False Extra-Libraries: stdc++ GHC-Options: -Wall Hs-Source-Dirs: example Main-Is: MastermindKnead.hs Other-Modules: Mastermind.Utility Mastermind.Guess Mastermind.Distinguish Mastermind.Example Random Benchmark mastermind-benchmark Type: exitcode-stdio-1.0 Build-Depends: set-cover, timeit, QuickCheck >=2.5 && <3.0, random >=1.0 && <1.2, transformers >=0.2 && <0.6, enummapset, containers, array >=0.1 && <0.6, utility-ht, base GHC-Options: -Wall Hs-Source-Dirs: example Main-Is: Mastermind/Benchmark.hs Other-Modules: Mastermind.Test Mastermind.Guess Mastermind.Utility Executable pangram If flag(buildExamples) Build-Depends: set-cover, containers, base Else Buildable: False GHC-Options: -Wall Hs-Source-Dirs: example Main-Is: Pangram.hs Executable conway-puzzle If flag(buildExamples) Build-Depends: set-cover, pooled-io >=0.0 && <0.1, transformers, containers, base Else Buildable: False GHC-Options: -Wall -rtsopts -threaded Hs-Source-Dirs: example Main-Is: ConwayPuzzle.hs Other-Modules: Utility