set-cover

Solve exact set cover problems like Sudoku, 8 Queens, Soma Cube, Tetris Cube

http://hub.darcs.net/thielema/set-cover/

Version on this page:0.0.9
LTS Haskell 23.19:0.1.1.1@rev:1
Stackage Nightly 2025-04-30:0.1.1.1@rev:1
Latest on Hackage:0.1.1.1@rev:1

See all snapshots set-cover appears in

BSD-3-Clause licensed by Henning Thielemann, Helmut Podhaisky
Maintained by Henning Thielemann
This version can be pinned in stack with:set-cover-0.0.9@sha256:6cb458704e5a3c60612f22922e0876a841732283a05ce89d23221044b99b3370,5742

Module documentation for 0.0.9

Solver for exact set cover problems. Included examples: Sudoku, Nonogram, 8 Queens, Domino tiling, Mastermind, Soma Cube, Tetris Cube, Cube of L's, Logika's Baumeister 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.

Build examples with cabal install -fbuildExamples.

The package needs only Haskell 98.

Changes

Change log for the set-cover package

0.0.8

  • SetCover.Exact.Priority implements the Algorithm X using a priority queue that registers the sets each element is contained in. This allows for drastic speedup of the Nonogram example.

0.0.7

  • ESC.bitVectorFromSetAssigns allows to turn sets into bit vectors without manual bit position gymnastics.

  • Use it in Sudoku and Nonogram examples.

0.0.6

  • Add SetCover.Exact.Set instances for Map, Integer, IntSet.

0.0.5.1

  • example/Nonogram: explore different encodings of the problem