Skip to main content

moser_tardos_witness

Function moser_tardos_witness 

Source
pub fn moser_tardos_witness(
    num_vars: usize,
    clauses: &[Vec<Lit>],
    seed: u64,
    max_resamples: usize,
) -> Option<Vec<bool>>
Expand description

Constructively find a satisfying assignment by Moser–Tardos resampling: start from a random assignment and, while some clause is violated, resample the variables of one violated clause. Under the LLL condition this terminates in expected O(m) resamples; the max_resamples cap is a safety net (only reachable when the condition does not hold). Returns a model, or None if the cap is hit.