Struct DlxBuilder

pub struct DlxBuilder { /* private fields */ }

Builder for Dlx

Implementations

impl DlxBuilder

pub fn new(n_primary: usize, n_secondary: usize) -> Self

Creates an empty Dlx instance with the specified number of primary and secondary items but no options. Primary items are automatically numbered starting at 1 and secondary item numbers follow consecutively after primary items.

Panics

If too many items (n_primary + n_secondary) exceeds memory or usize limitations.

Examples found in repository

examples/sudoku.rs (line 24)

pub fn solve(puzzle: &str) -> Option<String> {
    if puzzle.len() != 81 {
        return None;
    }

    let mut builder = DlxBuilder::new(9 * 9 * 4, 0);
    let mut givens = IntSet::<{ (324 + 63) / 64 }>::new();

    // add puzzle givens
    for (i, ch) in puzzle.chars().enumerate() {
        let Some(digit) = ch.to_digit(10) else {
            continue;
        };
        if !(1..=9).contains(&digit) {
            continue;
        }
        let digit = (digit - 1) as usize;
        let option = sudoku_items(i, digit);
        builder.add_option(&option);
        for &item in &option {
            givens.insert(item);
        }
    }

    // add all options that do not conflict with givens
    for cell in 0..81 {
        for digit in 0..9 {
            let option = sudoku_items(cell, digit);
            if option.iter().any(|&i| givens.get(i)) {
                continue;
            }
            builder.add_option(&option);
        }
    }

    let mut ec = MrvExactCoverSearch::new(builder.build());
    ec.search();

    let solution = ec.current_solution()?;
    let mut result = vec![b' '; 81];
    const DIGIT_BYTES: &[u8] = b"123456789";
    for option in solution {
        let Ok(option): Result<[usize; 4], _> = option.try_into() else {
            unreachable!()
        };
        let [cell, digit] = sudoku_invert_items(&option);
        result[cell] = DIGIT_BYTES[digit];
    }
    Some(String::from_utf8(result).expect("valid utf8 that we constructed ourselves"))
}

pub fn add_option<'a, I: IntoIterator<Item = &'a usize>>( &mut self, option: I, ) -> &mut Self

Adds option represented as a sorted (ascending order) collection of unique item indices.

Item indices start at 1 (index 0 is reserved). Empty options are silently ignored.

Panics

• If an item index is encountered that is outside the bounds established by the new call (1..=n_primary + n_secondary).
• If option items are not listed in ascending order or include duplicate items

Examples found in repository

examples/sudoku.rs (line 37)

pub fn solve(puzzle: &str) -> Option<String> {
    if puzzle.len() != 81 {
        return None;
    }

    let mut builder = DlxBuilder::new(9 * 9 * 4, 0);
    let mut givens = IntSet::<{ (324 + 63) / 64 }>::new();

    // add puzzle givens
    for (i, ch) in puzzle.chars().enumerate() {
        let Some(digit) = ch.to_digit(10) else {
            continue;
        };
        if !(1..=9).contains(&digit) {
            continue;
        }
        let digit = (digit - 1) as usize;
        let option = sudoku_items(i, digit);
        builder.add_option(&option);
        for &item in &option {
            givens.insert(item);
        }
    }

    // add all options that do not conflict with givens
    for cell in 0..81 {
        for digit in 0..9 {
            let option = sudoku_items(cell, digit);
            if option.iter().any(|&i| givens.get(i)) {
                continue;
            }
            builder.add_option(&option);
        }
    }

    let mut ec = MrvExactCoverSearch::new(builder.build());
    ec.search();

    let solution = ec.current_solution()?;
    let mut result = vec![b' '; 81];
    const DIGIT_BYTES: &[u8] = b"123456789";
    for option in solution {
        let Ok(option): Result<[usize; 4], _> = option.try_into() else {
            unreachable!()
        };
        let [cell, digit] = sudoku_invert_items(&option);
        result[cell] = DIGIT_BYTES[digit];
    }
    Some(String::from_utf8(result).expect("valid utf8 that we constructed ourselves"))
}

pub fn build(self) -> Dlx

Consumes the builder and returns the completed Dlx

Examples found in repository

examples/sudoku.rs (line 54)

pub fn solve(puzzle: &str) -> Option<String> {
    if puzzle.len() != 81 {
        return None;
    }

    let mut builder = DlxBuilder::new(9 * 9 * 4, 0);
    let mut givens = IntSet::<{ (324 + 63) / 64 }>::new();

    // add puzzle givens
    for (i, ch) in puzzle.chars().enumerate() {
        let Some(digit) = ch.to_digit(10) else {
            continue;
        };
        if !(1..=9).contains(&digit) {
            continue;
        }
        let digit = (digit - 1) as usize;
        let option = sudoku_items(i, digit);
        builder.add_option(&option);
        for &item in &option {
            givens.insert(item);
        }
    }

    // add all options that do not conflict with givens
    for cell in 0..81 {
        for digit in 0..9 {
            let option = sudoku_items(cell, digit);
            if option.iter().any(|&i| givens.get(i)) {
                continue;
            }
            builder.add_option(&option);
        }
    }

    let mut ec = MrvExactCoverSearch::new(builder.build());
    ec.search();

    let solution = ec.current_solution()?;
    let mut result = vec![b' '; 81];
    const DIGIT_BYTES: &[u8] = b"123456789";
    for option in solution {
        let Ok(option): Result<[usize; 4], _> = option.try_into() else {
            unreachable!()
        };
        let [cell, digit] = sudoku_invert_items(&option);
        result[cell] = DIGIT_BYTES[digit];
    }
    Some(String::from_utf8(result).expect("valid utf8 that we constructed ourselves"))
}

Trait Implementations

impl AsRef<Dlx> for DlxBuilder

Provides a read-only view into the underlying Dlx

fn as_ref(&self) -> &Dlx

Converts this type into a shared reference of the (usually inferred) input type.

impl From<DlxBuilder> for Dlx

fn from(value: DlxBuilder) -> Self

Converts to this type from the input type.