set-cover

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

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

LTS Haskell 22.39:0.1.1.1
Stackage Nightly 2024-10-29:0.1.1.1
Latest on Hackage:0.1.1.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.1.1.1@sha256:6cf5df48292e8f9a97ac8d57ee30ebe4a960b621c6dea45fab1d4c34be430e61,8263

Module documentation for 0.1.1.1

Used by 2 packages in nightly-2024-10-29(full list with versions):
battleship-combinatorics, set-cover

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.

Changes

Change log for the set-cover package

0.1

  • SetCover.Exact.decisionTree, SetCover.Exact.Priority.decisionTree: Allow the programmer to generate human-friendly solutions.

  • SetCover.Cuboid: dx, dy, dz -> rotX, rotY, rotZ

  • SetCover.Bit: method complement replaced by difference. This way, we do not need the cumbersome SetCover.IntSet module anymore.

  • SetCover.BitMap made private.

  • SetCover.BitPriorityQueue made public.

  • SetCover.Exact.State.usedSubsets: Only store labels, not assignments. This is consistent with SetCover.Exact.Priority.State.

  • SetCover.Exact.minimize: allow an empty list of available subsets SetCover.Exact.step, SetCover.Exact.Priority.step: They do not need to test for an empty availableSubset anymore.

  • SetCover.Exact.step: Require non-empty set of free elements. This is consistent with SetCover.Exact.Priority.step. Until now, step returned 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 step is called from search.

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