use std::collections::HashSet;
use std::time::Instant;
pub struct Cnf<'b> {
pub nvars: usize,
pub clauses: Vec<&'b [i32]>,
pub cap: Option<usize>,
pub full: bool,
bump: &'b bumpalo::Bump,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum SatResult {
Sat(Vec<bool>),
Unsat,
Unknown,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Propagated {
Fixpoint,
Conflict(usize),
Deadline,
}
struct Watches {
lists: Vec<Vec<usize>>,
watch: Vec<[usize; 2]>,
}
fn lit_index(lit: i32) -> usize {
(lit.unsigned_abs() - 1) as usize * 2 + usize::from(lit < 0)
}
fn build_watches(clauses: &[&[i32]], nvars: usize) -> Watches {
let mut lists = vec![Vec::new(); 2 * nvars];
let mut watch = Vec::with_capacity(clauses.len());
for (ci, clause) in clauses.iter().enumerate() {
let pair = if clause.len() >= 2 {
[0usize, 1]
} else {
[0usize, 0]
};
lists[lit_index(clause[pair[0]])].push(ci);
if clause.len() >= 2 {
lists[lit_index(clause[pair[1]])].push(ci);
}
watch.push(pair);
}
Watches { lists, watch }
}
impl<'b> Cnf<'b> {
#[must_use]
pub fn new(bump: &'b bumpalo::Bump) -> Self {
Self {
nvars: 0,
clauses: Vec::new(),
cap: None,
full: false,
bump,
}
}
pub fn new_var(&mut self) -> i32 {
self.nvars += 1;
self.nvars as i32 }
pub fn add_clause(&mut self, lits: &[i32]) {
if self.full {
return;
}
if self.cap.is_some_and(|c| self.clauses.len() >= c) {
self.full = true;
return;
}
self.clauses.push(self.bump.alloc_slice_copy(lits));
}
#[must_use]
pub fn solve_within(&self, budget: u64, deadline: Option<Instant>) -> SatResult {
if self.full {
return SatResult::Unknown;
}
solve(&self.clauses, self.nvars, budget, deadline)
}
}
fn preprocess(
clauses: &[&[i32]],
nvars: usize,
deadline: Option<Instant>,
) -> Option<Vec<Vec<i32>>> {
let mut forced = vec![None; nvars];
for clause in clauses {
if deadline.is_some_and(|d| Instant::now() >= d) {
return None;
}
if clause.len() == 1 {
let lit = clause[0];
forced[(lit.unsigned_abs() - 1) as usize] = Some(lit > 0);
}
}
let mut out: Vec<Vec<i32>> = Vec::with_capacity(clauses.len());
let mut seen: HashSet<Vec<i32>> = HashSet::new();
for clause in clauses {
if deadline.is_some_and(|d| Instant::now() >= d) {
return None;
}
let mut kept: Vec<i32> = Vec::with_capacity(clause.len());
let mut satisfied = false;
let mut tautology = false;
for &lit in clause.iter() {
let v = (lit.unsigned_abs() - 1) as usize;
match forced[v] {
Some(want) if want == (lit > 0) => {
if clause.len() == 1 {
kept.push(lit); } else {
satisfied = true; break;
}
}
Some(_) => {} None => {
if kept.contains(&-lit) {
tautology = true; }
kept.push(lit);
}
}
}
if satisfied || tautology {
continue;
}
if kept.is_empty() {
return None; }
let mut key = kept.clone();
key.sort_unstable();
if seen.insert(key) {
out.push(kept);
}
}
Some(out)
}
#[must_use]
pub fn solve(
clauses: &[&[i32]],
nvars: usize,
budget: u64,
deadline: Option<Instant>,
) -> SatResult {
if deadline.is_some_and(|d| Instant::now() >= d) {
return SatResult::Unknown;
}
if clauses.iter().any(|c| c.is_empty()) {
return SatResult::Unsat;
}
let cleaned = preprocess(clauses, nvars, deadline);
if deadline.is_some_and(|d| Instant::now() >= d) {
return SatResult::Unknown;
}
let Some(cleaned) = cleaned else {
return SatResult::Unsat;
};
let cleaned: Vec<&[i32]> = cleaned.iter().map(Vec::as_slice).collect();
let clauses = cleaned.as_slice();
let n = 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;
let mut activity = vec![0u64; n];
let mut phase = vec![false; n];
let mut active = vec![false; n];
for clause in clauses {
for &lit in clause.iter() {
active[(lit.unsigned_abs() - 1) as usize] = true;
}
}
let mut watches = build_watches(clauses, n);
for clause in clauses {
if clause.len() == 1 {
let lit = clause[0];
let v = (lit.unsigned_abs() - 1) as usize;
match assign[v] {
Some(b) if b != (lit > 0) => return SatResult::Unsat, Some(_) => {}
None => {
assign[v] = Some(lit > 0);
trail.push(v);
}
}
}
}
let mut prop_head = 0usize;
loop {
match propagate(
clauses,
&mut watches,
&mut assign,
&mut trail,
&mut is_decision,
&mut prop_head,
deadline,
) {
Propagated::Deadline => return SatResult::Unknown,
Propagated::Conflict(ci) => {
for &lit in clauses[ci].iter() {
activity[(lit.unsigned_abs() - 1) as usize] += 1;
}
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();
phase[v] = assign[v].unwrap_or(false);
assign[v] = None;
is_decision[v] = false;
flipped[v] = false;
}
}
Propagated::Fixpoint => {
let best = (0..n)
.filter(|&v| active[v] && assign[v].is_none())
.min_by_key(|&v| (std::cmp::Reverse(activity[v]), v));
match best {
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(phase[v]);
is_decision[v] = true;
flipped[v] = false;
trail.push(v);
}
}
}
}
prop_head = trail.len().saturating_sub(1);
}
}
fn propagate(
clauses: &[&[i32]],
watches: &mut Watches,
assign: &mut [Option<bool>],
trail: &mut Vec<usize>,
is_decision: &mut [bool],
prop_head: &mut usize,
deadline: Option<Instant>,
) -> Propagated {
while *prop_head < trail.len() {
if deadline.is_some_and(|d| Instant::now() >= d) {
return Propagated::Deadline;
}
let v = trail[*prop_head];
*prop_head += 1;
let value = assign[v].unwrap_or(false);
let false_lit = if value { -(v as i32 + 1) } else { v as i32 + 1 };
let pending = std::mem::take(&mut watches.lists[lit_index(false_lit)]);
let mut keep = Vec::with_capacity(pending.len());
let mut conflict = None;
for (i, &ci) in pending.iter().enumerate() {
let clause = clauses[ci];
let w = watches.watch[ci];
let slot = if clause[w[0]] == false_lit { 0 } else { 1 };
let other_slot = slot ^ 1;
let other = clause[w[other_slot]];
let other_v = (other.unsigned_abs() - 1) as usize;
if assign[other_v] == Some(other > 0) {
keep.push(ci);
continue;
}
let mut moved = false;
for (k, &l) in clause.iter().enumerate() {
if k == w[0] || k == w[1] {
continue;
}
let lv = (l.unsigned_abs() - 1) as usize;
let want = l > 0;
if assign[lv] != Some(!want) {
let mut nw = w;
nw[slot] = k;
watches.watch[ci] = nw;
watches.lists[lit_index(l)].push(ci);
moved = true;
break;
}
}
if moved {
continue;
}
match assign[other_v] {
None => {
assign[other_v] = Some(other > 0);
is_decision[other_v] = false;
trail.push(other_v);
keep.push(ci);
}
Some(_) => {
keep.push(ci);
conflict = Some(ci);
keep.extend_from_slice(&pending[i + 1..]);
break;
}
}
}
watches.lists[lit_index(false_lit)] = keep;
if let Some(ci) = conflict {
return Propagated::Conflict(ci);
}
}
Propagated::Fixpoint
}
#[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:?}"),
}
}
fn elapsed() -> std::time::Instant {
let now = std::time::Instant::now();
now.checked_sub(std::time::Duration::from_secs(1))
.unwrap_or(now)
}
#[test]
fn test_elapsed_deadline_is_unknown_not_a_verdict() {
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, Some(elapsed())),
SatResult::Unknown
);
}
#[test]
fn test_future_deadline_does_not_block_a_verdict() {
let bump = bumpalo::Bump::new();
let mut cnf = Cnf::new(&bump);
let a = cnf.new_var();
cnf.add_clause(&[a]);
cnf.add_clause(&[-a]);
let far = std::time::Instant::now() + std::time::Duration::from_secs(3600);
assert_eq!(cnf.solve_within(10_000, Some(far)), SatResult::Unsat);
}
#[test]
fn test_sat_needs_several_decisions() {
let bump = bumpalo::Bump::new();
let mut cnf = Cnf::new(&bump);
let v: Vec<i32> = (0..6).map(|_| cnf.new_var()).collect();
cnf.add_clause(&[v[0], v[1]]);
cnf.add_clause(&[v[2], v[3]]);
cnf.add_clause(&[v[4], v[5]]);
match cnf.solve_within(10_000, None) {
SatResult::Sat(m) => {
assert!((m[0] || m[1]) && (m[2] || m[3]) && (m[4] || m[5]));
}
other => panic!("expected SAT, got {other:?}"),
}
}
#[test]
fn test_backtracking_flips_a_decision_and_recovers() {
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]);
cnf.add_clause(&[-a, b]);
cnf.add_clause(&[-a, -b]);
match cnf.solve_within(10_000, None) {
SatResult::Sat(m) => assert!(!m[0] && m[1], "expected a=false, b=true; got {m:?}"),
other => panic!("expected SAT, got {other:?}"),
}
}
#[test]
fn test_pigeonhole_three_pigeons_two_holes_is_unsat() {
let bump = bumpalo::Bump::new();
let mut cnf = Cnf::new(&bump);
let mut x = [[0i32; 2]; 3];
for pigeon in &mut x {
for slot in pigeon.iter_mut() {
*slot = cnf.new_var();
}
}
for pigeon in &x {
cnf.add_clause(&[pigeon[0], pigeon[1]]); }
let mut holes: [Vec<i32>; 2] = [Vec::new(), Vec::new()];
for pigeon in &x {
for (hole, &lit) in pigeon.iter().enumerate() {
holes[hole].push(lit);
}
}
for column in &holes {
for (i, &p) in column.iter().enumerate() {
for &q in &column[i + 1..] {
cnf.add_clause(&[-p, -q]); }
}
}
assert_eq!(cnf.solve_within(1_000_000, None), SatResult::Unsat);
}
#[test]
fn test_pigeonhole_nine_pigeons_eight_holes_is_unsat() {
let bump = bumpalo::Bump::new();
let mut cnf = Cnf::new(&bump);
let mut x = [[0i32; 8]; 9];
for pigeon in &mut x {
for slot in pigeon.iter_mut() {
*slot = cnf.new_var();
}
}
for pigeon in &x {
cnf.add_clause(pigeon); }
let mut holes: [Vec<i32>; 8] = [
Vec::new(),
Vec::new(),
Vec::new(),
Vec::new(),
Vec::new(),
Vec::new(),
Vec::new(),
Vec::new(),
];
for pigeon in &x {
for (hole, &lit) in pigeon.iter().enumerate() {
holes[hole].push(lit);
}
}
for column in &holes {
for (i, &p) in column.iter().enumerate() {
for &q in &column[i + 1..] {
cnf.add_clause(&[-p, -q]); }
}
}
assert_eq!(cnf.solve_within(1_000_000, None), SatResult::Unsat);
}
#[test]
fn test_zero_budget_refutes_by_propagation_but_cannot_branch() {
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(0, None), SatResult::Unsat);
let bump = bumpalo::Bump::new();
let mut cnf = Cnf::new(&bump);
let b = cnf.new_var();
let c = cnf.new_var();
cnf.add_clause(&[b, c]);
assert_eq!(cnf.solve_within(0, None), SatResult::Unknown);
}
}