backtrack-rs 🦀

backtrack 允许您简单且通用地解决回溯问题。

问题通过其 范围 和对可能解的 检查 来定义。

范围 确定了解的长度和允许的值。默认域为 usize，但如果 Scope 的生命周期允许，任何 T 都可以工作，包括引用。

检查 或 CheckInc 特性确定特定值的组合是否满足条件。

用法

要求解决方案长度小于整个范围，即部分解决方案必须满足，如果完整解决方案也应该满足。

求解器 在搜索中借用问题以获取 候选解决方案。

检查

我们定义了一个使用有限数字集进行倒数的问题，并通过迭代来解决。

use backtrack::problem::{Check, Scope};
use backtrack::solvers::IterSolveNaive;
// helper trait to filter solutions of interest
use backtrack::solve::IterSolveExt;

/// Obtain permutations of some 3 descending numbers
struct CountDown {}

impl Scope<'_> for CountDown {
    fn size(&self) -> usize { 3 }
    fn value(&self, index: usize) -> usize { index }
    fn len(&self) -> usize { 4 }
}

impl Check for CountDown{
    fn extends_sat(&self, solution: &[usize], x: &usize) -> bool {
        solution.last().map_or(true, |last| *last > *x)
    }
}

let solver = IterSolveNaive::new(&CountDown{});
let mut sats = solver.sat_iter();

assert_eq!(sats.next(), Some(vec![2, 1, 0]));
assert_eq!(sats.next(), Some(vec![3, 1, 0]));
assert_eq!(sats.next(), Some(vec![3, 2, 0]));
assert_eq!(sats.next(), Some(vec![3, 2, 1]));
assert_eq!(sats.next(), None);

增量检查

如果您的检查可以针对简化的解决方案制定，请实现 CheckInc。

通过首先为任何给定的 sat 检查计算中间值，可以获得与上述相同的结果。如果应该重用先前候选值之间的工作，则此方法是有意义的。

use backtrack::problem::{CheckInc, Scope};
use backtrack::solvers::{IterSolveCached};
// ...
impl CheckInc for CountDown{
    type Accumulator = (usize, bool);

    fn fold_acc(&self, accu: Option<Self::Accumulator>, x: &usize, _position: usize) -> Self::Accumulator {
        // remember last value and if it was larger than current one
        accu.map_or_else(||(*x, true), |last| (*x, last.0 > *x))
    }

    fn accu_sat(&self, accu: &Self::Accumulator, _x: &usize, _position: usize) -> bool {
        accu.1
    }
}
// since `CheckInc` works from accumulated state, a solver that caches them should be used
let mut sats = IterSolveCached::new(&CountDown{}).sat_iter();
// ... gives the same results as above

示例

请查看 examples 文件夹中的示例问题。

# 4-queens solution
cargo run --example n_queens 4 | grep Sat
## n_queens.rs: NQueens { n: 4 }
## Sat([1, 3, 0, 2])
## Sat([2, 0, 3, 1])

# sequence of numbers which sum up to a minimum value but not more
cargo run --example total_sum | grep Sat

基准测试

backtrack-rs 使用 criterion 进行基准测试。

cargo bench

待办事项

• 规划 / 有序解决方案
• 并行化搜索