3 unstable releases
0.3.1  Dec 5, 2023 

0.3.0  Dec 5, 2023 
0.2.2  Nov 8, 2023 
0.2.1 

0.2.0 

#1152 in Algorithms
37KB
559 lines
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://wwwcsfaculty.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 readytouse 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
.
# use xcov::*;
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());