1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104

//! `backtrack` lets you solve [backtracking](https://en.wikipedia.org/wiki/Backtracking) problems
//! simply and generically.
//!
//! Problems are defined by their *scope* and *checks* against possible solutions.
//!
//! A [Scope](crate::problem::Scope) determines length and allowed values of a solution.
//! The domain defaults to `usize`, but any `T` works if it lives as long as its `Scope`, including references.
//!
//! The [Check](crate::problem::Check) or [CheckInc](crate::problem::CheckInc) trait determines whether
//! a particular combination of values is satisfying.
//!
//!
//! ## Usage
//!
//! It is required that solutions shorter than the entire scope, i.e. partial
//! solutions must satisfy if the completed solutions should as well.
//!
//! [Solvers](crate::solvers) borrow a problem in search for
//! [candidate solutions](crate::solve::CandidateSolution).
//!
//! ### Checks
//! We define the problem of counting down with a limited set of numbers and solve iteratively.
//! ```rust
//! 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);
//! ```
//! ### Incremental Checks
//! If your checks can be formulated against a reduced solution,
//! implement [CheckInc](crate::problem::CheckInc) instead.
//!
//! The same result as above can be obtained by first "computing"
//! the last item at each step. Such an approach makes more sense if
//! work on more than one prior value needs to be peformed
//! for any given sat check.
//!
//! ```rust
//! use backtrack::problem::{CheckInc, Scope};
//! // ...
//! # use backtrack::solvers::IterSolveNaive;
//! # use backtrack::solve::IterSolveExt;
//! #  
//! # struct CountDown {}
//! #
//! # impl Scope<'_> for CountDown {
//! #     fn size(&self) -> usize { 3 }
//! #     fn value(&self, index: usize) -> usize { index }
//! #     fn len(&self) -> usize { 4 }
//! # }
//! #
//! impl CheckInc for CountDown{
//!     type Accumulator = usize;
//!
//!     fn fold_acc(&self, accu: Option<&Self::Accumulator>, x: &usize) -> Self::Accumulator {
//!         // only last value is of interest for checking
//!         *x
//!     }
//!
//!     fn accu_sat(&self, accu: Option<&Self::Accumulator>, x: &usize, index: usize) -> bool {
//!        accu.map_or(true, |last| last > x)
//!     }
//! }
//! // since `CheckInc` impls `Check`, the same solver as before can be used
//! // todo: specialize solver to actually realize performance advantage
//! // ...
//! #
//! # 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);
//! ```
pub mod problem;
pub mod problems;
pub mod solve;
pub mod solvers;