Crate excov 

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.

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.

Structs

DenseOptMapper

An implemention of OptMapper, where the option identifiers are already dense usize values; this implementation simply uses the opaque option identifier as the dense integer value.

HashOptMapper

An implemention of OptMapper, using a std::collections::HashMap to manage the option mapping.

Problem

Represention of an exact cover problem to be solved by solve().

SolutionIterator

An iterator yielding solutions to an exact cover problem. This is typically created by solve().

Traits

OptMapper

A trait for types that map between opaque solution-specific option identifiers and the dense option identifier space the problem solver requires for representing options.

Functions

solve

Computes solutions to the exact cover problem described by the supplied Problem.