Solver for exact set cover problems.
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
and fast but cumbersome bitvectors.
For getting familiar with the package
I propose to study the Queen8 example along with
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
Do not rely on that interface in released packages.
Change log for the
SetCover.Exact.Priority.decisionTree: Allow the programmer to generate human-friendly solutions.
difference. This way, we do not need the cumbersome
SetCover.Exact.State.usedSubsets: Only store labels, not assignments. This is consistent with
SetCover.Exact.minimize: allow an empty list of available subsets
SetCover.Exact.Priority.step: They do not need to test for an empty
SetCover.Exact.step: Require non-empty set of free elements. This is consistent with
SetCover.Exact.Priority.step. Until now,
stepreturned an empty list if the were no free elements. This is not very helpful since it will throw away already completed solutions. The test is also redundant when
stepis called from
SetCover.Exact.Priorityimplements the Algorithm X using a priority queue that registers the sets each element is contained in. This allows for drastic speedup of the
ESC.bitVectorFromSetAssignsallows to turn sets into bit vectors without manual bit position gymnastics.
Use it in
example/Nonogram: explore different encodings of the problem