Lib.rs

异步 精确覆盖 求解库，使用 Knuth 的 舞蹈链 (DLX) 算法。

⚠️ 该库正在开发中，API 很可能发生变化。

概念

许多类似谜题的问题，例如拼图、数独、N 皇后问题等，可以建模为精确覆盖问题。该库提供了一个高效的求解器，用于通用精确覆盖问题及其推广，因此您可以将自己的问题建模为精确覆盖问题，并通过代码求解和分析解决方案。

基本示例

use exact_cover::{Problem, Solver, SolverEvent};

fn main() {
    let mut prob = Problem::default();
    prob.add_constraints(1..=3);
    prob.add_subset("A", vec![1, 2, 3]);
    prob.add_subset("B", vec![1]);
    prob.add_subset("C", vec![2]);
    prob.add_subset("D", vec![3]);
    prob.add_subset("E", vec![1, 2]);
    prob.add_subset("F", vec![2, 3]);

    let mut solver = Solver::new(prob);
    let mut solutions = vec![];
    solver.run();

    for event in solver {
        if let SolverEvent::SolutionFound(sol) = event {
            solutions.push(sol);
        }
    }

    println!("{:?}", solutions); // [["A"], ["B", "C", "D"], ["B", "F"], ["E", "D"]]
}

异步 API

⚠️ 该功能尚不可用，但它是本项目的首要目标之一。

解决复杂的精确覆盖问题需要很长时间。用户不希望在没有了解进度或剩余时间的情况下等待求解过程结束。该库提供了异步 API 和各种功能来帮助解决这个问题。

• 得益于异步 API，您的程序无需等待求解器找到下一个解决方案。
• 您可以在任何时候获取求解过程的估计进度。
• 当搜索空间太大，求解过程可能不会在数百年内结束时，您可以中断求解器。
• 您可以将求解过程暂停并将求解器状态保存下来，稍后再恢复。