pub struct Cnf<'b> {
pub nvars: usize,
pub clauses: Vec<&'b [i32]>,
bump: &'b bumpalo::Bump,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum SatResult {
Sat(Vec<bool>),
Unsat,
Unknown,
}
impl<'b> Cnf<'b> {
#[must_use]
pub fn new(bump: &'b bumpalo::Bump) -> Self {
Self {
nvars: 0,
clauses: Vec::new(),
bump,
}
}
pub fn new_var(&mut self) -> i32 {
self.nvars += 1;
self.nvars as i32 }
pub fn add_clause(&mut self, lits: &[i32]) {
self.clauses.push(self.bump.alloc_slice_copy(lits));
}
#[must_use]
pub fn solve_within(&self, budget: u64, deadline: Option<std::time::Instant>) -> SatResult {
let n = self.nvars;
let mut assign: Vec<Option<bool>> = vec![None; n];
let mut trail: Vec<usize> = Vec::new(); let mut is_decision = vec![false; n];
let mut flipped = vec![false; n];
let mut decisions = 0u64;
loop {
if deadline.is_some_and(|d| std::time::Instant::now() >= d) {
return SatResult::Unknown;
}
if self.propagate(&mut assign, &mut trail, &mut is_decision) {
loop {
let Some(&v) = trail.last() else {
return SatResult::Unsat; };
if is_decision[v] && !flipped[v] {
let tried = assign[v].unwrap_or(false);
assign[v] = Some(!tried);
flipped[v] = true;
break; }
trail.pop();
assign[v] = None;
is_decision[v] = false;
flipped[v] = false;
}
} else {
match assign.iter().position(Option::is_none) {
None => {
return SatResult::Sat(assign.iter().map(|a| a.unwrap_or(false)).collect());
}
Some(v) => {
decisions += 1;
if decisions > budget {
return SatResult::Unknown;
}
assign[v] = Some(true);
is_decision[v] = true;
flipped[v] = false;
trail.push(v);
}
}
}
}
}
fn propagate(
&self,
assign: &mut [Option<bool>],
trail: &mut Vec<usize>,
is_decision: &mut [bool],
) -> bool {
loop {
let mut changed = false;
for clause in &self.clauses {
let mut unit: Option<i32> = None;
let mut unassigned = 0;
let mut satisfied = false;
for &lit in clause.iter() {
let v = (lit.unsigned_abs() - 1) as usize;
let want = lit > 0;
match assign[v] {
Some(b) => {
if b == want {
satisfied = true;
break;
}
}
None => {
unassigned += 1;
unit = Some(lit);
}
}
}
if satisfied {
continue;
}
if unassigned == 0 {
return true; }
if unassigned == 1 {
let lit = unit.unwrap_or(0);
let v = (lit.unsigned_abs() - 1) as usize;
assign[v] = Some(lit > 0);
is_decision[v] = false;
trail.push(v);
changed = true;
}
}
if !changed {
return false;
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_sat_unit_chain() {
let bump = bumpalo::Bump::new();
let mut cnf = Cnf::new(&bump);
let (a, b, c) = (cnf.new_var(), cnf.new_var(), cnf.new_var());
cnf.add_clause(&[a]);
cnf.add_clause(&[-a, b]);
cnf.add_clause(&[-b, c]);
match cnf.solve_within(10_000, None) {
SatResult::Sat(m) => assert!(m[0] && m[1] && m[2]),
other => panic!("expected SAT, got {other:?}"),
}
}
#[test]
fn test_sat_contradiction_is_unsat() {
let bump = bumpalo::Bump::new();
let mut cnf = Cnf::new(&bump);
let a = cnf.new_var();
cnf.add_clause(&[a]);
cnf.add_clause(&[-a]);
assert_eq!(cnf.solve_within(10_000, None), SatResult::Unsat);
}
#[test]
fn test_sat_needs_a_decision() {
let bump = bumpalo::Bump::new();
let mut cnf = Cnf::new(&bump);
let (a, b) = (cnf.new_var(), cnf.new_var());
cnf.add_clause(&[a, b]);
match cnf.solve_within(10_000, None) {
SatResult::Sat(m) => assert!(m[0] || m[1]),
other => panic!("expected SAT, got {other:?}"),
}
}
}