## Expand description

## Exact Cover

This crate provides an implementation of Knuth’s Algorithm X for solving exact cover problems.

The algorithms and data structures in this module, as well as the terminology of “options” and “items”, come from Donald Knuth’s The Art of Computer Programming, section 7.2.2, https://www-cs-faculty.stanford.edu/~knuth/fasc5c.ps.gz.

- No dependencies
- 100% safe Rust
- Choose whether to find a single solution or all possible solutions
- Designed for flexibility (see below)

From a high level, Algorithm X is simply a backtracking exhaustive search
algorithm. At a lower level, Algorithm X cleverly manipulates linked lists using
the “dancing links” technique to make the backtracking more efficient. This
crate implements the backtracking search as a provided trait method
`ExactCoverProblem::search`

, while the dancing links data structure
and operations are implemented by the `Dlx`

struct. A custom implementation of
the `ExactCoverProblem`

trait can make use of the dancing links structure
provided by `Dlx`

, control the order items are selected for covering, and apply
additional filters to options for problems beyond pure exact cover.

A ready-to-use implementation using the *minimum remaining values* heuristic to
select items (i.e. select the item covered by the fewest number of available
options) is provided with `MrvExactCoverSearch`

. Its code can be helpful as a
starting point for custom implementations.

### Examples

The following pure exact cover problem is often used as an example in texts by
Knuth, and consists of 7 items and 6 options. For a more practical application,
see `examples/sudoku.rs`

.

```
let mut builder = DlxBuilder::new(7, 0);
builder.add_option(&[ 3, 5 ]);
builder.add_option(&[1, 4, 7]);
builder.add_option(&[ 2, 3, 6 ]);
builder.add_option(&[1, 4, 6 ]);
builder.add_option(&[ 2, 7]);
builder.add_option(&[ 4, 5, 7]);
let mut problem = MrvExactCoverSearch::new(builder.build());
problem.search();
let solution = problem
.current_solution()
.expect("this example problem has a solution")
.into_iter()
.collect::<Vec<_>>();
assert_eq!(
solution,
[
&[1, 4, 6][..],
&[2, 7],
&[3, 5],
]
);
// can look for additional solutions but this problem has none
assert!(!problem.search());
assert!(problem.current_solution().is_none());
```

## Structs

- Lower level “dancing links” data structure described by Knuth for solving exact cover problems.
- Builder for
`Dlx`

- Opaque handle used by
`Dlx`

to refer to an option. - An
`ExactCoverProblem`

implementation using the*minimum-remaining-values*(MRV) heuristic, i.e. items with the fewest available options are selected first.

## Traits

- A generalized exact cover problem. See module documentation for additional details.