Struct Solution 

pub struct Solution<'s, 'i: 's, I, C, S> { /* private fields */ }

An iterator over the options of a solution to an XCC problem.

Implementations

impl<'s, 'i, S, I, C> Solution<'s, 'i, I, C, S>

where S: Solver<'i, I, C>, I: Eq,

pub fn next(&mut self, result: &mut Vec<&'i I>) -> bool

Places the items in the next option of the solution into result.

Returns false and leaves the vector untouched if and only if all options have already been enumerated.

Examples found in repository

examples/langford_pairs.rs (line 61)

fn main() {
    let numbers = (1..=N).map(Item::Number);
    let slots = (1..=2 * N).map(Item::Slot);
    let items: Vec<_> = numbers.chain(slots).collect();

    let mut solver: DlSolver<Item, ()> = DlSolver::new(&items, &[]);
    for i in 1..=N {
        // Optimization: half of the Langford pairs for a given value of $n$
        // are the reverses of the others. Reduce the search space by placing
        // the first 1 in position $1\le s_j<n$.
        let first_slot_range = 1..if i == 1 { N } else { 2 * N - i };
        for j in first_slot_range {
            let k = i + j + 1;
            let items = [Item::Number(i), Item::Slot(j), Item::Slot(k)];
            solver.add_option(items, []);
        }
    }

    let mut options = Vec::new();
    solver.solve(|mut solution| {
        assert_eq!(solution.option_count(), N);
        // Convert the set of options into the corresponding placement.
        let mut placement = [0usize; 2 * N];
        while solution.next(&mut options) {
            // Sort the items in `options` so we can perform pattern matching.
            // Note that `Item` derives `Ord`, so item variants are ordered by
            // their discriminants: numbers come before slots.
            options.sort();
            if let &[&Item::Number(i), &Item::Slot(j), &Item::Slot(k)] = &options[..] {
                placement[j - 1] = i;
                placement[k - 1] = i;
            } else {
                unreachable!("ordered option should match (number, slot, slot) pattern");
            }
        }
        // Print the found Langford sequence, and its reverse.
        println!("{:?}", placement);
        placement.reverse();
        println!("{:?}", placement);
    });
}

examples/polycube_packing.rs (line 186)

fn main() {
    // Define the items of the exact cover problem, namely the $lmn$ cells of
    // the $l\times m\times n$ cuboid.
    let (l, m, n) = (5i8, 5i8, 5i8);
    let positions = (0..l)
        .flat_map(|x| iter::repeat(x).zip(0..m))
        .flat_map(|y| iter::repeat(y).zip(0..n))
        .map(|((x, y), z)| (x, y, z))
        .collect::<Vec<_>>();

    let mut solver: DlSolver<Position, ()> = DlSolver::new(&positions, &[]);
    // For each base placement $P$ of the Y pentacube, and for each offset
    // $(x_0,y_0,z_0)$ such that the piece $P'=P+(x_0,y_0,z_0)$ lies within the
    // $l\times m\times n$ cuboid cornered at the origin, define an option whose
    // primary items are the cells of $P'$. We break symmetry by constraining
    // a particular cubie of the first pentacube to be at $L_\infty$ distance
    // $\le2$ from the origin.
    let placements = Y.base_placements();
    let mut first = true;
    for placement in placements {
        for (x_0, y_0, z_0) in &positions {
            if first && (*x_0 > 2 || *y_0 > 2 || *z_0 > 2) {
                continue;
            }
            let shifted = placement.transform(|(x, y, z)| (x + x_0, y + y_0, z + z_0));
            if is_in_bounds(&shifted, l, m, n) {
                solver.add_option(&shifted.0, []);
            }
        }
        first = false;
    }

    let mut count = 0;
    let mut polycube = Vec::with_capacity(Y.cubie_count());
    solver.solve(|mut solution| {
        // Print the solution, which consists of a set of 25 pentacubes.
        print!("[");
        while solution.next(&mut polycube) {
            print!("[");
            if let Some((&last, elements)) = polycube.split_last() {
                for &cubie in elements {
                    print!("[{},{},{}],", cubie.0, cubie.1, cubie.2);
                }
                print!("[{},{},{}]", last.0, last.1, last.2);
            }
            print!("],");
        }
        println!("]");
        count += 1;
    });
    println!("found {count} packings");
}

pub fn option_count(&self) -> usize

Returns the number of options in the solution.

Examples found in repository

examples/langford_pairs.rs (line 58)

fn main() {
    let numbers = (1..=N).map(Item::Number);
    let slots = (1..=2 * N).map(Item::Slot);
    let items: Vec<_> = numbers.chain(slots).collect();

    let mut solver: DlSolver<Item, ()> = DlSolver::new(&items, &[]);
    for i in 1..=N {
        // Optimization: half of the Langford pairs for a given value of $n$
        // are the reverses of the others. Reduce the search space by placing
        // the first 1 in position $1\le s_j<n$.
        let first_slot_range = 1..if i == 1 { N } else { 2 * N - i };
        for j in first_slot_range {
            let k = i + j + 1;
            let items = [Item::Number(i), Item::Slot(j), Item::Slot(k)];
            solver.add_option(items, []);
        }
    }

    let mut options = Vec::new();
    solver.solve(|mut solution| {
        assert_eq!(solution.option_count(), N);
        // Convert the set of options into the corresponding placement.
        let mut placement = [0usize; 2 * N];
        while solution.next(&mut options) {
            // Sort the items in `options` so we can perform pattern matching.
            // Note that `Item` derives `Ord`, so item variants are ordered by
            // their discriminants: numbers come before slots.
            options.sort();
            if let &[&Item::Number(i), &Item::Slot(j), &Item::Slot(k)] = &options[..] {
                placement[j - 1] = i;
                placement[k - 1] = i;
            } else {
                unreachable!("ordered option should match (number, slot, slot) pattern");
            }
        }
        // Print the found Langford sequence, and its reverse.
        println!("{:?}", placement);
        placement.reverse();
        println!("{:?}", placement);
    });
}