To solve an exact cover problem with this implementation, instantiate a Problem using [Problem::new()], add constraints to describe the problem, and call [solve()] to produce one or more solutions.

An example, based on Wikipedia's Algorithm X article:

// This is the example problem from
// <https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X>; it
// makes for a nice test case, since the article explains
// every step of the execution.

let mut problem = excov::Problem::new(excov::DenseOptMapper{});

problem.add_constraint([0, 1]);
problem.add_constraint([4, 5]);
problem.add_constraint([3, 4]);
problem.add_constraint([0, 1, 2]);
problem.add_constraint([2, 3]);
problem.add_constraint([2, 3]);
problem.add_constraint([3, 4]);
problem.add_constraint([0, 2, 4, 5]);

// And then, actually solve the problem.
let mut solution_count = 0;
for soln in excov::solve(problem) {
    solution_count += 1;
    assert_eq!(
        vec![1usize, 3, 5],
        soln,
        "solution: expected(left) != actual(right)"
    )
};

assert_eq!(1, solution_count);

For more expressiveness in option identifiers, it may be useful to use HashOptMapper, which lets you use any option identifier that can be stored as a key in a std::collections::HashMap.

Excov

This package is an implementation of Knuth's Algorithm X using DLX.

This is just my little starter project to explore Rust. That said, the implementation is meant to be relatively simple and efficient, and I'd deeply appreciate any comments on how to make the code better.

Knuth's Algorithm X solves exact cover problems -- see the wikipedia article for details. But basically: if you have a set X, and a set S of subsets of X (so, each element of S contains some number of elements of X), can you find a subset of S s.t. each element of X is contained in exactly one subset? Essentially, this partitions X, with no elements in X left over.

This is useful for things like solving Sudoku puzzles or the N Queens puzzle.