exact-covers

此包提供了 D. E. Knuth 和 C. Solnon 的算法实现，用于解决带有颜色控制的精确覆盖问题。

假设我们有一个选项集合 $\mathcal{O}$，每个选项都是一个项目集；精确覆盖问题是要找到一个子集合 $\mathcal{O}^\star\subseteq\mathcal{O}$，使得每个项目恰好出现在 $\mathcal{O}^\star$ 的一个选项中。Knuth 在其论文 "Dancing Links" 中提出了一个方法，该论文实现了这个目标，arXiv:cs/0011047 cs.DS (2000)，标题指的是一种巧妙而简单的删除和恢复双链表节点的方法。他的回溯方案，称为 Algorithm X，利用这种“华尔兹”链接以递归、深度优先的方式访问所有具有选项 $\mathcal{O}$ 的精确覆盖。[有关更多信息，请参阅 The Art of Computer Programming 4B (2022) 的第 7.2.2.1 节，Part 2，第 65-70 页。]

对 Algorithm X 的微小修改解决了更普遍的问题，其中项目分为两类：主要 和 次要。现在任务是找到一个选项子集合 $\mathcal{O}^\star\subseteq\mathcal{O}$，使得每个主要项目恰好被覆盖一次，而每个次要项目最多被覆盖一次。如果进一步为每个选项的次要项目分配一个 颜色，则出现 带有颜色的精确覆盖 (XCC) 问题。如果两个选项的次要项目具有匹配的颜色，则称这两个选项是 兼容的，我们定义一个解决方案为互为兼容的选项集合 $\mathcal{O}^\star\subseteq\mathcal{O}$，它恰好覆盖每个主要项目一次。（与无色情况不同，如果它们的颜色兼容，则次要项目可以出现在 $\mathcal{O}^\star$ 的多个选项中。）

幸运的是，舞蹈链技术也非常适合XCC问题。当Knuth在《TAOCP》第7.2.2.1节中引入算法C时，他就证明了这一点。[参见TAOCP 4B部分2，第87-91页](https://www-cs-faculty.stanford.edu/~knuth/taocp.html#vol4)，他的新方法将算法X扩展到了颜色。2020年，C. Solnon建议使用P. Briggs和L. Torczon的稀疏集合数据结构[参见ACM Letters on Programming Languages and Systems 2 (1993)，第59-69页](https://dl.acm.org/doi/pdf/10.1145/176454.176484)来存储当前活动选项的数据库和需要覆盖的项目列表。Knuth准备了这个方法的实现，称为“舞蹈细胞”方法，使用了算法C的约定。这两个XCC求解器的基准测试结果出现在《TAOCP》第7.2.2.3节中[参见TAOCP 4C (2024年6月25日)预印本7A，第64-65页](https://cs.stanford.edu/~knuth/fasc7a.ps.gz)。总结这些实验的结果：没有明显的赢家，我们还没有确定哪种方法最适合XCC的一个特定实例。

这个crate是Rust编程语言的子例程库，用于对$N_1\ge0$个主要项目和$N_2\ge0$个次要项目进行颜色控制覆盖。以下结构是其最重要的部分

• DlSolver找到XCC问题的所有解。它实现了Knuth的算法7.2.2.1C的略微修改版本。
• DcSolver遵循与先前结构相同的输入和输出约定，但它使用舞蹈细胞技术。

两种实现都支持通过移除阻塞和强制来简化选项。[关于这些预处理操作的讨论，请参见TAOCP 4B (2022)第2部分，第108-111页](https://www-cs-faculty.stanford.edu/~knuth/taocp.html#vol4)。

此外，examples目录包含一系列程序，展示了如何将这些算法应用于各种问题。

• langford_pairs.rs找到所有$2n$个数字的Langford配对。
• polycube_packing.rs计算25个Y五立方体在$5\times5\times5$立方体中排列的方法数量。
• domino_chessboard.rs找到将32个多米诺骨牌放入棋盘的所有方法。

许可

MIT © Hugo Sanz González