精确覆盖

此包提供Knuth的算法X的实现，用于解决精确覆盖问题。

本模块中的算法和数据结构，以及“选项”和“项目”的术语，来自Donald Knuth的计算机程序设计艺术，第7.2.2节，https://www-cs-faculty.stanford.edu/~knuth/fasc5c.ps.gz。

• 无依赖
• 100%安全Rust
• 选择是否找到单个解决方案或所有可能的解决方案
• 设计灵活（见下文）

从高层次来看，算法X只是一个回溯穷举搜索算法。在低层次上，算法X巧妙地使用“动态链接”技术操纵链表，使回溯更有效。此包将回溯搜索实现为提供的特质方法ExactCoverProblem::search，而动态链接数据结构和操作由[Dlx]结构实现。自定义实现ExactCoverProblem特质可以利用Dlx提供的动态链接结构，控制选择覆盖项的顺序，并针对纯精确覆盖问题之外的问题应用额外的过滤器。

提供了一个使用最小剩余值启发式方法选择项的现成实现（即选择由最少的可用选项覆盖的项），与MrvExactCoverSearch一起提供。其代码可以作为自定义实现的起点。

示例

以下纯精确覆盖问题常用于Knuth的文本示例中，由7个项目和6个选项组成。对于更实际的应用，请参阅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());