Trait Solver 

pub trait Solver<'i, I, C>: Solver<'i, I, C> {
    // Required methods
    fn new(primary: &'i [I], secondary: &'i [I]) -> Self;
    fn add_option<P, S>(&mut self, primary: P, secondary: S)
       where P: AsRef<[I]>,
             S: AsRef<[(I, Option<C>)]>;
    fn solve<F>(self, visit: F)
       where F: FnMut(Solution<'_, 'i, I, C, Self>) -> ControlFlow<()>;
}

Visits all solutions to an XCC problem with $N_1\ge0$ primary items and $N_2\ge0$ secondary items.

See the crate-level documentation for details.

Notes

The solver does not visit any solution containing a purely secondary option (that is, an option that uses no primary items). However, the set of items covered by the options in any visited solution intersects every purely secondary option. This strategy is a generalized version of the “second death” method from exercise 7.2.2.1–19 of TAOCP to the XCC problem.

This trait is sealed, meaning that it cannot be implemented outside of the exact-covers crate.

Examples

Suppose we want to cover the primary items $a,b,c,d,e,f,g$ using some of the following options: \[ `c\;e’;\quad`a\;d\;g’;\quad`b\;c\;f’;\quad`a\;d\;f’;\quad`b\;g’;\quad`d\;e\;g’. \] (D. E. Knuth posed this toy problem at the beginning of Section 7.2.2.1 in The Art of Computer Programming 4B (2022), Part 2, page 66.) The following program uses an XC solver based on the dancing links method to find the unique solution $`a\;d\;f’;\;`b\;g’;\;`c\;e’$:

use std::ops::ControlFlow;
use exact_covers::{DlSolver, Solver};

let items = ['a', 'b', 'c', 'd', 'e', 'f', 'g'];
let mut solver: DlSolver<char, ()> = DlSolver::new(&items, &[]);
solver.add_option([          'c',      'e'         ], []);
solver.add_option(['a',           'd',          'g'], []);
solver.add_option([     'b', 'c',           'f'    ], []);
solver.add_option(['a',           'd',      'f'    ], []);
solver.add_option([     'b',                    'g'], []);
solver.add_option([               'd', 'e',     'g'], []);

// We use an auxiliary table to store the items of an option. The chief
// purpose of this reserved storage is to reduce heap allocations when
// constructing the solutions to an XCC problem.
let mut option = Vec::new();
solver.solve(|mut solution| {
    assert_eq!(solution.option_count(), 3);

    // An option is represented as a list of `(item, color)` pairs.
    // In this example we are not doing color-controlled covering,
    // so all color assignments are `None`.
    assert!(solution.next(&mut option));
    assert_eq!(option, [(&'a', None), (&'d', None), (&'f', None)]);
    assert!(solution.next(&mut option));
    assert_eq!(option, [(&'b', None), (&'g', None)]);
    assert!(solution.next(&mut option));
    assert_eq!(option, [(&'c', None), (&'e', None)]);
    ControlFlow::Continue(())
});

Here’s a slightly more interesting challenge: Given primary items $a,b,c$ and secondary items $p,q$, find all subsets of options \[ `a\;c\;p\;q{:}0’;\quad`b\;c\;q{:}2’;\quad`a\;p’;\quad`b\;p{:}1’;\quad`q{:}2’ \] that (i) cover every primary item exactly once, and (ii) assign at most one color to every secondary item. (The notation $i{:}x$ means that color $x$ is assigned to item $i$; when a secondary item is not followed by a colon, it is implicitly assigned a unique color which is incompatible with any other.) The program below uses an XCC solver to obtain the solution $`a\;p’;\;`b\;c\;q{:}2’$. Observe that the solver discards the only other solution $`a\;p’;\;`b\;c\;q{:}2’;\;`q{:}2’$, because it contains a purely secondary option.

use std::ops::ControlFlow;
use exact_covers::{DlSolver, Solver};

let primary = ['a', 'b', 'c'];
let secondary = ['p', 'q'];
let mut solver: DlSolver<char, u8> = DlSolver::new(&primary, &secondary);
solver.add_option(['a',      'c'], [('p', None),    ('q', Some(0))]);
solver.add_option([     'b', 'c'], [                ('q', Some(2))]);
solver.add_option(['a'          ], [('p', None)                   ]);
solver.add_option([     'b',    ], [('p', Some(1))                ]);
solver.add_option([             ], [                ('q', Some(2))]);

let mut option = Vec::new();
let mut num_sols = 0;
solver.solve(|mut solution| {
    // Notice that `color = None` if and only if `item` is primary
    // or was not explicitly assigned a color by `option`.
    assert!(solution.next(&mut option));
    assert_eq!(option, [(&'a', None), (&'p', None)]);
    assert!(solution.next(&mut option));
    assert_eq!(option, [(&'b', None), (&'c', None), (&'q', Some(2))]);
    assert!(!solution.next(&mut option));
    num_sols += 1;
    ControlFlow::Continue(())
});
assert_eq!(num_sols, 1);

Required Methods

fn new(primary: &'i [I], secondary: &'i [I]) -> Self

Creates a solver for an XCC problem on the given primary and secondary items.

To specify the options to cover these items, use Self::add_option.

fn add_option<P, S>(&mut self, primary: P, secondary: S)

where P: AsRef<[I]>, S: AsRef<[(I, Option<C>)]>,

Appends an option to the XCC problem.

The meaning of a pair $(i,c)$ in the list of secondary items depends on the value of $c$: If $c$ is Some(c') for some c', then the secondary item $i$ is assigned color c'; otherwise $i$ is implicitly assigned a unique color that doesn’t match the color of the item in any other option.

Once all options have been specified, use Self::solve to visit all solutions to the problem.

fn solve<F>(self, visit: F)

where F: FnMut(Solution<'_, 'i, I, C, Self>) -> ControlFlow<()>,

Calls a closure on each solution to the XCC problem.

The solution process continues until the closure returns ControlFlow::Break or all solutions have been visited, whichever occurs first.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<'i, I: Eq, C: Eq + Copy> Solver<'i, I, C> for exact_covers::DcSolver

impl<'i, I: Eq, C: Eq + Copy> Solver<'i, I, C> for exact_covers::DlSolver<'i, I, C>