exact-cover- Efficient exact cover solver.

Safe HaskellNone




This module provides an efficient solver for exact set cover problems (http://en.wikipedia.org/wiki/Exact_cover) using Algorithm X as described in the paper Dancing Links, by Donald Knuth, in Millennial Perspectives in Computer Science, P159, 2000 (https://arxiv.org/abs/cs/0011047).

For a quick start, go straight to the solve function.


Mathematical definition

Given a collection \( \mathcal{S} \) of subsets of a set \( \mathcal{X} \), an exact cover is a subcollection \( \mathcal{S}^{*} \) of \( \mathcal{S} \) such that each element in \( \mathcal{X} \) is contained in exactly one subset in \( \mathcal{S}^{*} \) (from wikipedia).

Simple interface

solve :: (Enum a, Ord a) => Map (Set a) setlabel -> [setlabel] Source #

Given a collection of subsets \( \mathcal{S} \), represented by a Map between each subset (of type Set a) and its label, returns a list of labels that represents the exact cover \( \mathcal{S}^{*} \).

Example: To find the exact cover of the collection of subsets \( \left\{\left\{2,4,5\right\}, \left\{0,3,6\right\}, \left\{1,2,5\right\}, \left\{0,3\right\}, \left\{1,6\right\}, \left\{3,4,6\right\}\right\} \),

solve (Map.fromList [ (Set.fromList [2,4,5], 'A')
                    , (Set.fromList [0,3,6], 'B')
                    , (Set.fromList [1,2,5], 'C')
                    , (Set.fromList [0,3], 'D')
                    , (Set.fromList [1,6], 'E')
                    , (Set.fromList [3,4,6], 'F')
                    ] :: Map (Set Int) Char)
== "DAE"


data ExactCoverProblem setlabel a Source #

Basic type that represents the exact cover problem.


transform :: Enum a => Map (Set a) setlabel -> ExactCoverProblem setlabel a Source #

Constructs an ExactCoverProblem given a collection of subsets \( \mathcal{S} \) as represented by a Map between each subset and its label. The set \( \mathcal{X} \) over which the exact cover is to be found is assumed to be the union of the given collection of subsets \( \mathcal{S} \).


solveEC :: (Enum a, Ord a) => ExactCoverProblem setlabel a -> [setlabel] Source #

Solves the given ExactCoverProblem, returning the labels of the subsets that form the exact cover.