Skip to main content

logicaffeine_proof/
grid_solver.rs

1//! A fast, certified finite-domain (logic-grid) solver.
2//!
3//! Logic-grid puzzles ground to a quantifier-free clause/rule set; a 4×4 grid is a
4//! small SAT(+equality) problem that a determined-CSP solver closes in milliseconds.
5//! The wall the previous engine hit was speed: `engine::cert_saturate` re-saturates
6//! `O(facts²)` at every search node. This module is the incremental replacement —
7//! trail-based watched-literal unit propagation + DPLL — that finds the answer fast.
8//!
9//! Crucially, certification is DECOUPLED from search (see [`crate::verify`]): the
10//! solver finds the model/refutation however it likes, then a post-pass emits a
11//! [`DerivationTree`] from the recorded reasons, reusing the certified inference
12//! rules. [`crate::verify::check_derivation`] re-checks that tree in the kernel, so
13//! the solver sits OUTSIDE the trusted base — a wrong tree yields `verified == false`,
14//! never a false claim.
15//!
16//! Build order (see plan): Phase A de-risks the emitter (this file's tests prove the
17//! certified tree SHAPES the solver will produce actually certify), before any search
18//! machinery exists.
19
20#![allow(dead_code)]
21
22use crate::{DerivationTree, InferenceRule, ProofExpr};
23
24// ── Tree constructors (the exact certified shapes the emitter produces) ──────────
25
26fn leaf(e: ProofExpr) -> DerivationTree {
27    DerivationTree::leaf(e, InferenceRule::PremiseMatch)
28}
29
30fn neg(e: &ProofExpr) -> ProofExpr {
31    match e {
32        ProofExpr::Not(inner) => (**inner).clone(),
33        _ => ProofExpr::Not(Box::new(e.clone())),
34    }
35}
36
37fn falsum() -> ProofExpr {
38    ProofExpr::Atom("⊥".into())
39}
40
41/// ModusPonens: from `impl_tree : A → C` and `ante_tree : A`, conclude `C`.
42fn modus_ponens(
43    c: ProofExpr,
44    impl_tree: DerivationTree,
45    ante_tree: DerivationTree,
46) -> DerivationTree {
47    DerivationTree::new(c, InferenceRule::ModusPonens, vec![impl_tree, ante_tree])
48}
49
50/// Disjunctive syllogism: from `or_tree : A ∨ B` and `neg_tree : ¬A`, conclude `B`.
51fn disjunction_elim(
52    survivor: ProofExpr,
53    or_tree: DerivationTree,
54    neg_tree: DerivationTree,
55) -> DerivationTree {
56    DerivationTree::new(
57        survivor,
58        InferenceRule::DisjunctionElim,
59        vec![or_tree, neg_tree],
60    )
61}
62
63/// Conjunction introduction: from `l : A` and `r : B`, conclude `A ∧ B`.
64fn conj_intro(a: ProofExpr, b: ProofExpr, l: DerivationTree, r: DerivationTree) -> DerivationTree {
65    DerivationTree::new(
66        ProofExpr::And(Box::new(a), Box::new(b)),
67        InferenceRule::ConjunctionIntro,
68        vec![l, r],
69    )
70}
71
72/// Contradiction: from `P` and `¬P`, conclude `⊥` (the certifier finds the polarity).
73fn contradiction(p: DerivationTree, np: DerivationTree) -> DerivationTree {
74    DerivationTree::new(falsum(), InferenceRule::Contradiction, vec![p, np])
75}
76
77/// Reductio: assume `assumed`, derive `⊥` (`falsum_tree`), conclude `¬assumed`.
78fn reductio(assumed: ProofExpr, falsum_tree: DerivationTree) -> DerivationTree {
79    let concl = ProofExpr::Not(Box::new(assumed.clone()));
80    DerivationTree::new(
81        concl,
82        InferenceRule::ReductioAdAbsurdum,
83        vec![leaf(assumed), falsum_tree],
84    )
85}
86
87/// Equality symmetry: from `a = b`, conclude `b = a`.
88fn eq_sym(a: crate::ProofTerm, b: crate::ProofTerm, tree: DerivationTree) -> DerivationTree {
89    DerivationTree::new(
90        ProofExpr::Identity(b, a),
91        InferenceRule::EqualitySymmetry,
92        vec![tree],
93    )
94}
95
96/// Disjunction case analysis to a common conclusion: from `A ∨ B` and a proof of the
97/// conclusion in each branch (with the disjunct bound as a local hypothesis), conclude
98/// the common goal.
99fn disjunction_cases(
100    goal: ProofExpr,
101    or_tree: DerivationTree,
102    left: DerivationTree,
103    right: DerivationTree,
104) -> DerivationTree {
105    DerivationTree::new(
106        goal,
107        InferenceRule::DisjunctionCases,
108        vec![or_tree, left, right],
109    )
110}
111
112/// Conjunction elimination: from `A ∧ B`, project the named `conjunct`.
113fn conj_elim(conjunct: ProofExpr, and_tree: DerivationTree) -> DerivationTree {
114    DerivationTree::new(conjunct, InferenceRule::ConjunctionElim, vec![and_tree])
115}
116
117// ── Atoms & literals ─────────────────────────────────────────────────────────────
118
119use crate::ProofTerm;
120use std::collections::HashMap;
121
122type Var = usize;
123
124#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
125struct Lit {
126    var: Var,
127    pos: bool,
128}
129
130impl Lit {
131    fn negate(self) -> Lit {
132        Lit {
133            var: self.var,
134            pos: !self.pos,
135        }
136    }
137}
138
139fn term_key(t: &ProofTerm) -> String {
140    t.to_string()
141}
142
143/// Canonical key for a POSITIVE atom. `Identity` is normalized to an unordered pair so
144/// `a = b` and `b = a` intern to the SAME variable — they are the same proposition.
145fn atom_key(e: &ProofExpr) -> Option<String> {
146    match e {
147        ProofExpr::Predicate { name, args, .. } => {
148            let parts: Vec<String> = args.iter().map(term_key).collect();
149            Some(format!("P:{}({})", name, parts.join(",")))
150        }
151        ProofExpr::Identity(a, b) => {
152            let (ka, kb) = (term_key(a), term_key(b));
153            let (lo, hi) = if ka <= kb { (ka, kb) } else { (kb, ka) };
154            Some(format!("=:{}|{}", lo, hi))
155        }
156        ProofExpr::Atom(s) => Some(format!("A:{}", s)),
157        _ => None,
158    }
159}
160
161fn is_atomish(e: &ProofExpr) -> bool {
162    matches!(
163        e,
164        ProofExpr::Predicate { .. } | ProofExpr::Identity(..) | ProofExpr::Atom(_)
165    )
166}
167
168fn is_literal(e: &ProofExpr) -> bool {
169    match e {
170        ProofExpr::Not(inner) => is_atomish(inner),
171        _ => is_atomish(e),
172    }
173}
174
175/// A clause disjunct the solver can decide on: a literal, or a conjunction whose every
176/// leaf is a literal (an of-pair disjunct). A disjunct carrying an implication or
177/// quantifier (e.g. a grounded `∃`-existence clause) is rejected, so `compile` skips it.
178fn is_clause_disjunct(e: &ProofExpr) -> bool {
179    match e {
180        ProofExpr::And(l, r) | ProofExpr::Or(l, r) => {
181            is_clause_disjunct(l) && is_clause_disjunct(r)
182        }
183        _ => is_literal(e),
184    }
185}
186
187fn flatten_and(e: &ProofExpr, out: &mut Vec<ProofExpr>) {
188    match e {
189        ProofExpr::And(l, r) => {
190            flatten_and(l, out);
191            flatten_and(r, out);
192        }
193        _ => out.push(e.clone()),
194    }
195}
196
197fn flatten_or(e: &ProofExpr, out: &mut Vec<ProofExpr>) {
198    match e {
199        ProofExpr::Or(l, r) => {
200            flatten_or(l, out);
201            flatten_or(r, out);
202        }
203        _ => out.push(e.clone()),
204    }
205}
206
207/// Intern every atom occurring in `e` (so a decision clause's compound disjuncts get
208/// variables even though they never appear as standalone literals).
209fn intern_all(table: &mut AtomTable, e: &ProofExpr) {
210    match e {
211        ProofExpr::And(l, r)
212        | ProofExpr::Or(l, r)
213        | ProofExpr::Implies(l, r)
214        | ProofExpr::Iff(l, r) => {
215            intern_all(table, l);
216            intern_all(table, r);
217        }
218        ProofExpr::Not(inner) => intern_all(table, inner),
219        _ if is_atomish(e) => {
220            table.intern(e);
221        }
222        _ => {}
223    }
224}
225
226#[derive(Default)]
227struct AtomTable {
228    by_key: HashMap<String, Var>,
229    atoms: Vec<ProofExpr>,
230}
231
232impl AtomTable {
233    fn intern(&mut self, atom: &ProofExpr) -> Option<Var> {
234        let k = atom_key(atom)?;
235        if let Some(&v) = self.by_key.get(&k) {
236            return Some(v);
237        }
238        let v = self.atoms.len();
239        self.atoms.push(atom.clone());
240        self.by_key.insert(k, v);
241        Some(v)
242    }
243
244    fn lit(&mut self, e: &ProofExpr) -> Option<Lit> {
245        match e {
246            ProofExpr::Not(inner) => Some(Lit {
247                var: self.intern(inner)?,
248                pos: false,
249            }),
250            _ => Some(Lit {
251                var: self.intern(e)?,
252                pos: true,
253            }),
254        }
255    }
256}
257
258// ── Clauses & rules ──────────────────────────────────────────────────────────────
259
260enum ClauseSrc {
261    /// A bare disjunction premise; the exact `Or(...)` expression (for emit).
262    Bare(ProofExpr),
263    /// Materialized when the disjunctive-consequent rule `usize` fires.
264    FromRule(usize),
265    /// Added inside a decision branch as the assumed disjunct of an enclosing
266    /// case-split (resolves to the bound conjunct hypothesis at emit time).
267    Assumed(ProofExpr),
268}
269
270/// A disjunction. Its disjuncts may be literals (enabling unit propagation, `lits`
271/// `Some`) or compound conjunctions (decision clauses, `lits` `None`). `or_expr`
272/// preserves the exact `Or` nesting the emitter must follow.
273struct Clause {
274    or_expr: ProofExpr,
275    disjuncts: Vec<ProofExpr>,
276    lits: Option<Vec<Lit>>,
277    src: ClauseSrc,
278}
279
280enum RuleCons {
281    Lit(Lit),
282    Disj(Vec<Lit>),
283}
284
285/// Three-valued status of a disjunct (or a whole conjunction) under the trail.
286#[derive(Clone, Copy, PartialEq, Eq)]
287enum Tri {
288    True,
289    False,
290    Live,
291}
292
293struct Rule {
294    ante: Vec<Lit>,
295    cons: RuleCons,
296    /// The exact `Implies(...)` premise (cited by ModusPonens emit).
297    src: ProofExpr,
298}
299
300/// How a variable came to be assigned — enough for the emitter to rebuild the
301/// certified sub-proof.
302#[derive(Clone)]
303enum Reason {
304    /// A unit premise; the exact premise expression.
305    Premise(ProofExpr),
306    /// ModusPonens: rule `usize` fired (all antecedents true) yielding this literal.
307    Rule(usize),
308    /// Exclusion (ModusTollens shape): rule `usize`'s consequent is violated and all
309    /// antecedents but this one are true, so this antecedent is forced false.
310    Exclude(usize),
311    /// Unit propagation: this literal is the survivor of clause `usize`.
312    Clause(usize),
313    /// Disjunctive syllogism over a COMPOUND clause: clause `clause` has a single live
314    /// disjunct (index `disjunct`); every other disjunct is refuted by a false conjunct.
315    /// This literal is one of that surviving disjunct's conjuncts — proved by peeling the
316    /// refuted disjuncts (`DisjunctionElim`) then projecting the conjunct (`ConjunctionElim`).
317    /// This is what lets an of-pair clue contribute a LINEAR deduction instead of a search.
318    CompoundClause { clause: usize, disjunct: usize },
319    /// A search decision / assumption (justified by a bound hypothesis at emit time).
320    Assumption,
321}
322
323// ── The solver ───────────────────────────────────────────────────────────────────
324
325struct Solver {
326    table: AtomTable,
327    clauses: Vec<Clause>,
328    rules: Vec<Rule>,
329    assign: Vec<Option<bool>>,
330    reason: Vec<Option<Reason>>,
331    trail: Vec<Var>,
332    /// Per-variable assignment order (index into `trail`). Lets the emitter refute a
333    /// disjunct using the conjunct that became false EARLIEST, keeping the reconstructed
334    /// proof's recursion strictly backward in trail order (acyclic).
335    pos: Vec<usize>,
336    fired_disj: Vec<bool>,
337    /// Clauses currently mid-case-split (so the recursive search does not re-pick a
338    /// clause whose chosen disjunct still has a pending sub-disjunction).
339    deciding: std::collections::HashSet<usize>,
340    /// Whether propagation is running at decision level 0 (the root fixpoint, never
341    /// backtracked). Compound-clause unit propagation fires ONLY here: a root-forced
342    /// literal is permanent, so its reason chain is monotone in trail order and the
343    /// linear emit is acyclic. Under a backtrackable assumption (search branch), an
344    /// of-pair clause's XOR-coupled disjuncts can force each other circularly, so there
345    /// the clause is left to the case-split fallback instead.
346    at_root: bool,
347}
348
349enum Conflict {
350    /// Rule `usize`'s antecedents are all true but its consequent is violated.
351    Rule(usize),
352    /// Clause `usize` has every literal violated.
353    Clause(usize),
354}
355
356/// Classify each ground premise into the solver's clause/rule/unit forms. Returns
357/// `None` on anything it cannot classify (e.g. a surviving quantifier), so the caller
358/// can fall back to the general engine.
359fn compile(premises: &[ProofExpr]) -> Option<Solver> {
360    let mut table = AtomTable::default();
361    let mut clauses = Vec::new();
362    let mut rules = Vec::new();
363    let mut units: Vec<(Lit, ProofExpr)> = Vec::new();
364
365    // Grounding conjoins each universal's instances into one top-level `And`; split
366    // those back into independent facts (a conjunction asserts each conjunct).
367    let mut flat: Vec<ProofExpr> = Vec::new();
368    for p in premises {
369        flatten_and(p, &mut flat);
370    }
371
372    // Classify each fact; a premise that does not fit the clause/rule/unit grammar is
373    // SKIPPED, not fatal. Skipping is sound — `check_derivation` re-checks every emitted
374    // tree against the FULL premise set, so a dropped (e.g. redundant grounded `∃`
375    // existence) premise can only make the solver fail to prove, never prove falsely.
376    for p in &flat {
377        match p {
378            ProofExpr::Or(..) => {
379                let mut ds = Vec::new();
380                flatten_or(p, &mut ds);
381                if !ds.iter().all(is_clause_disjunct) {
382                    continue;
383                }
384                intern_all(&mut table, p);
385                let lits = if ds.iter().all(is_literal) {
386                    ds.iter()
387                        .map(|d| table.lit(d))
388                        .collect::<Option<Vec<Lit>>>()
389                } else {
390                    None
391                };
392                clauses.push(Clause {
393                    or_expr: p.clone(),
394                    disjuncts: ds,
395                    lits,
396                    src: ClauseSrc::Bare(p.clone()),
397                });
398            }
399            ProofExpr::Implies(ante, cons) => {
400                let mut as_ = Vec::new();
401                flatten_and(ante, &mut as_);
402                if !as_.iter().all(is_literal) {
403                    continue;
404                }
405                let cons_form = if is_literal(cons) {
406                    intern_all(&mut table, p);
407                    RuleCons::Lit(table.lit(cons).unwrap())
408                } else if matches!(cons.as_ref(), ProofExpr::Or(..)) {
409                    let mut ds = Vec::new();
410                    flatten_or(cons, &mut ds);
411                    if !ds.iter().all(is_literal) {
412                        continue;
413                    }
414                    intern_all(&mut table, p);
415                    RuleCons::Disj(ds.iter().map(|d| table.lit(d).unwrap()).collect())
416                } else {
417                    continue;
418                };
419                let ante_lits = as_.iter().map(|a| table.lit(a).unwrap()).collect();
420                rules.push(Rule {
421                    ante: ante_lits,
422                    cons: cons_form,
423                    src: p.clone(),
424                });
425            }
426            _ if is_literal(p) => {
427                intern_all(&mut table, p);
428                units.push((table.lit(p).unwrap(), p.clone()));
429            }
430            _ => continue,
431        }
432    }
433
434    let n = table.atoms.len();
435    let fired_disj = vec![false; rules.len()];
436    let mut solver = Solver {
437        table,
438        clauses,
439        rules,
440        assign: vec![None; n],
441        reason: vec![None; n],
442        trail: Vec::new(),
443        pos: vec![usize::MAX; n],
444        fired_disj,
445        deciding: std::collections::HashSet::new(),
446        at_root: false,
447    };
448    for (l, expr) in units {
449        let _ = solver.set(l, Reason::Premise(expr));
450    }
451    Some(solver)
452}
453
454impl Solver {
455    /// `Some(true)` if `l` holds, `Some(false)` if `l` is violated, `None` if unknown.
456    fn value(&self, l: Lit) -> Option<bool> {
457        self.assign[l.var].map(|b| b == l.pos)
458    }
459
460    fn var_of_atom(&self, atom: &ProofExpr) -> Option<Var> {
461        self.table.by_key.get(&atom_key(atom)?).copied()
462    }
463
464    fn lit_of(&self, e: &ProofExpr) -> Option<Lit> {
465        match e {
466            ProofExpr::Not(inner) => Some(Lit {
467                var: self.var_of_atom(inner)?,
468                pos: false,
469            }),
470            _ => Some(Lit {
471                var: self.var_of_atom(e)?,
472                pos: true,
473            }),
474        }
475    }
476
477    fn lit_expr(&self, l: Lit) -> ProofExpr {
478        let atom = self.table.atoms[l.var].clone();
479        if l.pos {
480            atom
481        } else {
482            ProofExpr::Not(Box::new(atom))
483        }
484    }
485
486    fn set(&mut self, l: Lit, r: Reason) -> Result<(), ()> {
487        match self.assign[l.var] {
488            Some(b) => {
489                if b == l.pos {
490                    Ok(())
491                } else {
492                    Err(())
493                }
494            }
495            None => {
496                self.assign[l.var] = Some(l.pos);
497                self.reason[l.var] = Some(r);
498                self.pos[l.var] = self.trail.len();
499                self.trail.push(l.var);
500                Ok(())
501            }
502        }
503    }
504
505    /// Trail-based fixpoint propagation: forward ModusPonens, backward exclusion
506    /// (ModusTollens), disjunctive-consequent materialization, and unit-clause
507    /// propagation. Returns the conflict if one is reached.
508    fn propagate(&mut self) -> Result<(), Conflict> {
509        loop {
510            let mut changed = false;
511
512            for ri in 0..self.rules.len() {
513                // Tally the antecedents.
514                let mut n_nonsat = 0usize;
515                let mut the_nonsat: Option<Lit> = None;
516                let mut any_false = false;
517                for i in 0..self.rules[ri].ante.len() {
518                    let a = self.rules[ri].ante[i];
519                    match self.value(a) {
520                        Some(true) => {}
521                        Some(false) => {
522                            any_false = true;
523                            n_nonsat += 1;
524                            the_nonsat = Some(a);
525                        }
526                        None => {
527                            n_nonsat += 1;
528                            the_nonsat = Some(a);
529                        }
530                    }
531                }
532
533                // A false antecedent makes the rule vacuously true.
534                if any_false {
535                    continue;
536                }
537
538                if n_nonsat == 0 {
539                    // All antecedents hold → fire forward.
540                    match &self.rules[ri].cons {
541                        RuleCons::Lit(l) => {
542                            let l = *l;
543                            match self.value(l) {
544                                Some(true) => {}
545                                Some(false) => return Err(Conflict::Rule(ri)),
546                                None => {
547                                    let _ = self.set(l, Reason::Rule(ri));
548                                    changed = true;
549                                }
550                            }
551                        }
552                        RuleCons::Disj(lits) => {
553                            if !self.fired_disj[ri] {
554                                let lits = lits.clone();
555                                self.fired_disj[ri] = true;
556                                let (_, cons_form) = Self::split_implies(&self.rules[ri].src);
557                                let mut ds = Vec::new();
558                                flatten_or(&cons_form, &mut ds);
559                                self.clauses.push(Clause {
560                                    or_expr: cons_form,
561                                    disjuncts: ds,
562                                    lits: Some(lits),
563                                    src: ClauseSrc::FromRule(ri),
564                                });
565                                changed = true;
566                            }
567                        }
568                    }
569                } else if n_nonsat == 1 {
570                    // Exactly one antecedent open. If the consequent is a literal that is
571                    // already violated, that antecedent must be false (ModusTollens).
572                    if let RuleCons::Lit(l) = &self.rules[ri].cons {
573                        if self.value(*l) == Some(false) {
574                            let open = the_nonsat.unwrap();
575                            if self.value(open).is_none() {
576                                let _ = self.set(open.negate(), Reason::Exclude(ri));
577                                changed = true;
578                            }
579                        }
580                    }
581                }
582            }
583
584            for ci in 0..self.clauses.len() {
585                let (has_true, live) = self.clause_status(ci);
586                if has_true {
587                    continue;
588                }
589                if live.is_empty() {
590                    return Err(Conflict::Clause(ci));
591                }
592                // Unit propagation on a literal clause: the lone live literal is forced.
593                if self.clauses[ci].lits.is_some() && live.len() == 1 {
594                    if let Some(l) = self.lit_of(&self.clauses[ci].disjuncts[live[0]]) {
595                        if self.set(l, Reason::Clause(ci)).is_ok() {
596                            changed = true;
597                        }
598                    }
599                }
600                // Compound (of-pair / either-or) clause collapsed to a SINGLE live
601                // disjunct: disjunctive syllogism forces that disjunct, so assert each of
602                // its literal conjuncts. This is the deduction that lets the whole grid
603                // be forced by propagation (no search) → linear proofs. Gated to the root
604                // fixpoint: under a backtrackable assumption the survivor's conjuncts can
605                // be the only thing refuting a sibling (shared anchor), making the reason
606                // chain cyclic — those clauses are left to the case-split fallback.
607                if self.at_root && self.clauses[ci].lits.is_none() && live.len() == 1 {
608                    let di = live[0];
609                    let mut conjs = Vec::new();
610                    flatten_and(&self.clauses[ci].disjuncts[di].clone(), &mut conjs);
611                    for conj in &conjs {
612                        // Inner disjunction conjuncts (a nested either-or) are left to the
613                        // search; only the literal conjuncts are forced here.
614                        if !is_literal(conj) {
615                            continue;
616                        }
617                        let Some(l) = self.lit_of(conj) else { continue };
618                        match self.value(l) {
619                            Some(true) => {}
620                            Some(false) => return Err(Conflict::Clause(ci)),
621                            None => {
622                                let _ = self.set(
623                                    l,
624                                    Reason::CompoundClause {
625                                        clause: ci,
626                                        disjunct: di,
627                                    },
628                                );
629                                changed = true;
630                            }
631                        }
632                    }
633                }
634            }
635
636            if !changed {
637                break;
638            }
639        }
640        Ok(())
641    }
642
643    // ── Emit: turn the trail into a certified DerivationTree ─────────────────────
644
645    /// Prove the literal assigned to variable `v` (in its assigned polarity).
646    fn prove_var(&self, v: Var) -> DerivationTree {
647        let val = self.assign[v].expect("prove_var on unassigned variable");
648        match self.reason[v]
649            .as_ref()
650            .expect("assigned variable lacks a reason")
651        {
652            Reason::Premise(expr) => leaf(expr.clone()),
653            Reason::Assumption => leaf(self.lit_expr(Lit { var: v, pos: val })),
654            Reason::Rule(ri) => self.emit_rule_forward(*ri),
655            Reason::Exclude(ri) => self.emit_rule_exclude(*ri, v),
656            Reason::Clause(ci) => self.emit_clause_survivor(*ci, Lit { var: v, pos: val }),
657            Reason::CompoundClause { clause, disjunct } => {
658                self.emit_compound_clause(*clause, *disjunct, Lit { var: v, pos: val })
659            }
660        }
661    }
662
663    /// Emit a literal forced as a conjunct of a compound clause's single surviving
664    /// disjunct: peel the refuted disjuncts (disjunctive syllogism) to prove the
665    /// surviving conjunction, then ∧-eliminate down to the wanted literal. The
666    /// disjunction's `Or`-type appears ONCE here, not multiplied by a search tree.
667    fn emit_compound_clause(&self, ci: usize, di: usize, want: Lit) -> DerivationTree {
668        let or_expr = self.clauses[ci].or_expr.clone();
669        let or_tree = self.materialize_clause(ci);
670        let survivor = self.clauses[ci].disjuncts[di].clone();
671        let before = self.pos[want.var];
672        let surv_tree = self.extract_survivor(&or_expr, or_tree, &survivor, before);
673        let proj = self.project_conjunct(&survivor, surv_tree, want);
674        align_to(proj, &self.lit_expr(want))
675    }
676
677    /// From a proof of a (possibly nested) conjunction, ∧-eliminate down to the conjunct
678    /// whose literal is `want`.
679    fn project_conjunct(
680        &self,
681        conj: &ProofExpr,
682        conj_tree: DerivationTree,
683        want: Lit,
684    ) -> DerivationTree {
685        match conj {
686            ProofExpr::And(l, r) => {
687                if self.conjunct_has(l, want) {
688                    let lt = conj_elim((**l).clone(), conj_tree);
689                    self.project_conjunct(l, lt, want)
690                } else {
691                    let rt = conj_elim((**r).clone(), conj_tree);
692                    self.project_conjunct(r, rt, want)
693                }
694            }
695            _ => conj_tree,
696        }
697    }
698
699    /// Does the conjunction `e` contain a literal conjunct equal to `want`?
700    fn conjunct_has(&self, e: &ProofExpr, want: Lit) -> bool {
701        match e {
702            ProofExpr::And(l, r) => self.conjunct_has(l, want) || self.conjunct_has(r, want),
703            _ => self.lit_of(e) == Some(want),
704        }
705    }
706
707    /// Prove a literal expression `want` exactly (aligning Identity orientation).
708    fn prove_lit_expr(&self, want: &ProofExpr) -> DerivationTree {
709        let lit = self
710            .lit_of(want)
711            .expect("prove_lit_expr on an un-interned atom");
712        let base = self.prove_var(lit.var);
713        align_to(base, want)
714    }
715
716    fn split_implies(src: &ProofExpr) -> (ProofExpr, ProofExpr) {
717        match src {
718            ProofExpr::Implies(a, c) => ((**a).clone(), (**c).clone()),
719            _ => unreachable!("rule src is always an implication"),
720        }
721    }
722
723    /// Prove a conjunction/literal antecedent form. `forced` (if any) is proved by a
724    /// bound hypothesis leaf instead of recursing (it is the reductio assumption).
725    fn prove_ante(&self, form: &ProofExpr, forced: Option<Var>) -> DerivationTree {
726        match form {
727            ProofExpr::And(l, r) => conj_intro(
728                (**l).clone(),
729                (**r).clone(),
730                self.prove_ante(l, forced),
731                self.prove_ante(r, forced),
732            ),
733            _ => {
734                if let (Some(fv), Some(lit)) = (forced, self.lit_of(form)) {
735                    if lit.var == fv {
736                        return leaf(form.clone());
737                    }
738                }
739                self.prove_lit_expr(form)
740            }
741        }
742    }
743
744    fn emit_rule_forward(&self, ri: usize) -> DerivationTree {
745        let src = self.rules[ri].src.clone();
746        let (ante_form, cons_form) = Self::split_implies(&src);
747        let ante_proof = self.prove_ante(&ante_form, None);
748        modus_ponens(cons_form, leaf(src), ante_proof)
749    }
750
751    fn emit_rule_exclude(&self, ri: usize, forced_v: Var) -> DerivationTree {
752        let src = self.rules[ri].src.clone();
753        let (ante_form, cons_form) = Self::split_implies(&src);
754        let assumed = self.table.atoms[forced_v].clone();
755        let ante_proof = self.prove_ante(&ante_form, Some(forced_v));
756        let cons_tree = modus_ponens(cons_form.clone(), leaf(src), ante_proof);
757        let cons_lit = self
758            .lit_of(&cons_form)
759            .expect("exclusion consequent must be a literal");
760        let neg_cons = self.prove_var(cons_lit.var);
761        // The consequent may be negative (a functionality rule `Li → ¬Lj`), so the
762        // contradiction's polarity order is not fixed — let `make_contradiction` sort it.
763        let bot = make_contradiction(cons_tree, neg_cons);
764        reductio(assumed, bot)
765    }
766
767    fn materialize_clause(&self, ci: usize) -> DerivationTree {
768        match &self.clauses[ci].src {
769            ClauseSrc::Bare(or_expr) | ClauseSrc::Assumed(or_expr) => leaf(or_expr.clone()),
770            ClauseSrc::FromRule(ri) => {
771                let src = self.rules[*ri].src.clone();
772                let (ante_form, cons_form) = Self::split_implies(&src);
773                let ante_proof = self.prove_ante(&ante_form, None);
774                modus_ponens(cons_form, leaf(src), ante_proof)
775            }
776        }
777    }
778
779    fn emit_clause_survivor(&self, ci: usize, survivor: Lit) -> DerivationTree {
780        let or_tree = self.materialize_clause(ci);
781        let or_expr = or_tree.conclusion.clone();
782        let survivor_expr = self.lit_expr(survivor);
783        let before = self.pos[survivor.var];
784        self.extract_survivor(&or_expr, or_tree, &survivor_expr, before)
785    }
786
787    /// Extract the surviving disjunct `target` from a (left-nested) disjunction whose
788    /// every other disjunct is violated, by iterated disjunctive syllogism. `before` caps
789    /// the trail position of the facts used to refute the other disjuncts (acyclicity).
790    fn extract_survivor(
791        &self,
792        or_expr: &ProofExpr,
793        or_tree: DerivationTree,
794        target: &ProofExpr,
795        before: usize,
796    ) -> DerivationTree {
797        match or_expr {
798            ProofExpr::Or(l, r) => {
799                if r.as_ref() == target {
800                    let lneg = self.prove_neg_disjunct(l, before);
801                    disjunction_elim(target.clone(), or_tree, lneg)
802                } else {
803                    let rneg = self.prove_neg_disjunct(r, before);
804                    let l_tree = disjunction_elim((**l).clone(), or_tree, rneg);
805                    self.extract_survivor(l, l_tree, target, before)
806                }
807            }
808            _ => or_tree,
809        }
810    }
811
812    /// Prove `¬e` where `e` is a violated disjunct: a single literal (directly) or a
813    /// sub-disjunction (by reductio whose branches close to ⊥). `before` caps the
814    /// refuting facts' trail positions.
815    fn prove_neg_disjunct(&self, e: &ProofExpr, before: usize) -> DerivationTree {
816        if is_literal(e) {
817            let lit = self.lit_of(e).expect("disjunct atom must be interned");
818            let proof = self.prove_var(lit.var);
819            align_to(proof, &neg_of(e))
820        } else {
821            let bot = self.falsum_from_disj(e, leaf(e.clone()), before);
822            reductio(e.clone(), bot)
823        }
824    }
825
826    /// Given `e_tree : e` (a disjunction, conjunction, or literal, all violated), derive ⊥,
827    /// refuting using only facts assigned strictly before `before` where possible.
828    fn falsum_from_disj(
829        &self,
830        e: &ProofExpr,
831        e_tree: DerivationTree,
832        before: usize,
833    ) -> DerivationTree {
834        match e {
835            ProofExpr::Or(l, r) => {
836                let lb = self.falsum_from_disj(l, leaf((**l).clone()), before);
837                let rb = self.falsum_from_disj(r, leaf((**r).clone()), before);
838                disjunction_cases(falsum(), e_tree, lb, rb)
839            }
840            ProofExpr::And(l, r) => {
841                // A false conjunction disjunct: project the conjunct that became false
842                // EARLIEST — preferring one false strictly BEFORE the survivor was forced
843                // (`before`), else the globally earliest. Picking by trail order (not
844                // structural order, and capped at `before`) keeps the emit's recursion
845                // strictly backward, so the reconstructed proof is acyclic even when a
846                // later exclusion would otherwise refer back through the forcing clause.
847                let key = |x: &ProofExpr| {
848                    self.false_at(x, before)
849                        .map(|p| (0u8, p))
850                        .or_else(|| self.false_at(x, usize::MAX).map(|p| (1u8, p)))
851                };
852                let pick_left = match (key(l), key(r)) {
853                    (Some(a), Some(b)) => a <= b,
854                    (Some(_), None) => true,
855                    (None, Some(_)) => false,
856                    (None, None) => true,
857                };
858                let (conjunct, proj) = if pick_left {
859                    ((**l).clone(), conj_elim((**l).clone(), e_tree))
860                } else {
861                    ((**r).clone(), conj_elim((**r).clone(), e_tree))
862                };
863                self.falsum_from_disj(&conjunct, proj, before)
864            }
865            _ => {
866                let lit = self.lit_of(e).expect("disjunct atom must be interned");
867                let neg = self.prove_var(lit.var);
868                contra_align(e_tree, neg)
869            }
870        }
871    }
872
873    // ── Decision search (DPLL) ───────────────────────────────────────────────────
874
875    /// The trail position by which `e` is FALSE using only assignments strictly BEFORE
876    /// `before` (or `None`). A conjunction is false as soon as ANY conjunct is (earliest),
877    /// a disjunction only once ALL disjuncts are (latest), a literal at its own position.
878    /// The `before` cap keeps the reconstructed proof's recursion strictly backward.
879    fn false_at(&self, e: &ProofExpr, before: usize) -> Option<usize> {
880        match e {
881            ProofExpr::And(l, r) => match (self.false_at(l, before), self.false_at(r, before)) {
882                (Some(a), Some(b)) => Some(a.min(b)),
883                (a, b) => a.or(b),
884            },
885            ProofExpr::Or(l, r) => match (self.false_at(l, before), self.false_at(r, before)) {
886                (Some(a), Some(b)) => Some(a.max(b)),
887                _ => None,
888            },
889            _ => match self.lit_of(e) {
890                Some(l) if self.value(l) == Some(false) && self.pos[l.var] < before => {
891                    Some(self.pos[l.var])
892                }
893                _ => None,
894            },
895        }
896    }
897
898    /// Three-valued evaluation of a disjunct (or any conjunction/disjunction/literal)
899    /// under the current trail.
900    fn eval_disjunct(&self, e: &ProofExpr) -> Tri {
901        match e {
902            ProofExpr::And(l, r) => match (self.eval_disjunct(l), self.eval_disjunct(r)) {
903                (Tri::False, _) | (_, Tri::False) => Tri::False,
904                (Tri::True, Tri::True) => Tri::True,
905                _ => Tri::Live,
906            },
907            ProofExpr::Or(l, r) => match (self.eval_disjunct(l), self.eval_disjunct(r)) {
908                (Tri::True, _) | (_, Tri::True) => Tri::True,
909                (Tri::False, Tri::False) => Tri::False,
910                _ => Tri::Live,
911            },
912            _ => match self.lit_of(e).and_then(|l| self.value(l)) {
913                Some(true) => Tri::True,
914                Some(false) => Tri::False,
915                None => Tri::Live,
916            },
917        }
918    }
919
920    /// `(has_true, indices of live disjuncts)` for clause `ci`.
921    fn clause_status(&self, ci: usize) -> (bool, Vec<usize>) {
922        let mut has_true = false;
923        let mut live = Vec::new();
924        for (i, d) in self.clauses[ci].disjuncts.iter().enumerate() {
925            match self.eval_disjunct(d) {
926                Tri::True => has_true = true,
927                Tri::Live => live.push(i),
928                Tri::False => {}
929            }
930        }
931        (has_true, live)
932    }
933
934    /// The first unsatisfied clause with a live disjunct that the search must split.
935    /// (After propagation, literal clauses with a single live disjunct are already
936    /// unit-propagated, so only genuine decisions remain.)
937    fn pick_split(&self) -> Option<usize> {
938        // Split the MOST-CONSTRAINED open clause — the one with the fewest live disjuncts
939        // (minimum-remaining-values). A 2-live of-pair branches two ways and each branch
940        // re-propagates to a near-forced state; a 12-live one fans out twelve deep. Picking
941        // the smallest branching first keeps the case-analysis — and therefore the certified
942        // proof — shallow, the search analogue of the min-live closure selection.
943        (0..self.clauses.len())
944            .filter(|&ci| {
945                if self.deciding.contains(&ci) {
946                    return false;
947                }
948                let (has_true, live) = self.clause_status(ci);
949                if has_true || live.is_empty() {
950                    return false;
951                }
952                // A literal clause with a single live disjunct is already unit-propagated.
953                !(self.clauses[ci].lits.is_some() && live.len() < 2)
954            })
955            .min_by_key(|&ci| self.clause_status(ci).1.len())
956    }
957
958    /// Derive ⊥ from the current assumptions: propagate, and on a stall, case-split an
959    /// unresolved clause and refute every branch. `None` if a branch is satisfiable.
960    fn derive_falsum(&mut self, depth: usize) -> Option<DerivationTree> {
961        if depth > MAX_DEPTH {
962            return None;
963        }
964        if let Err(c) = self.propagate() {
965            return Some(self.emit_conflict(c));
966        }
967        let ci = self.pick_split()?;
968        let or_expr = self.clauses[ci].or_expr.clone();
969        let or_tree = self.materialize_clause(ci);
970        self.deciding.insert(ci);
971        let result = self.split_to_falsum(&or_expr, or_tree, depth);
972        self.deciding.remove(&ci);
973        result
974    }
975
976    fn split_to_falsum(
977        &mut self,
978        or_expr: &ProofExpr,
979        or_tree: DerivationTree,
980        depth: usize,
981    ) -> Option<DerivationTree> {
982        match or_expr {
983            ProofExpr::Or(l, r) => {
984                let lb = self.branch(l, depth)?;
985                let rb = self.branch(r, depth)?;
986                Some(disjunction_cases(falsum(), or_tree, lb, rb))
987            }
988            single => self.branch(single, depth),
989        }
990    }
991
992    /// Assume `disjunct` (bound as a hypothesis by the enclosing case-split), refute it
993    /// to ⊥, then undo the assumption.
994    fn branch(&mut self, disjunct: &ProofExpr, depth: usize) -> Option<DerivationTree> {
995        let trail_snap = self.trail.len();
996        let clause_snap = self.clauses.len();
997        let fired_snap = self.fired_disj.clone();
998        let result = match self.assume_disjunct(disjunct) {
999            Some(info) => Some(self.emit_conflict_info(info)),
1000            None => self.derive_falsum(depth + 1),
1001        };
1002        self.backtrack(trail_snap, clause_snap, fired_snap);
1003        result
1004    }
1005
1006    /// Assert a disjunct: set its literal conjuncts as assumptions and add any
1007    /// disjunction conjuncts as branch-local clauses. Returns the first conflict, if any.
1008    fn assume_disjunct(&mut self, d: &ProofExpr) -> Option<ConflictInfo> {
1009        match d {
1010            ProofExpr::And(l, r) => self.assume_disjunct(l).or_else(|| self.assume_disjunct(r)),
1011            ProofExpr::Or(..) => {
1012                let mut ds = Vec::new();
1013                flatten_or(d, &mut ds);
1014                let lits = if ds.iter().all(is_literal) {
1015                    ds.iter()
1016                        .map(|x| self.lit_of(x))
1017                        .collect::<Option<Vec<Lit>>>()
1018                } else {
1019                    None
1020                };
1021                self.clauses.push(Clause {
1022                    or_expr: d.clone(),
1023                    disjuncts: ds,
1024                    lits,
1025                    src: ClauseSrc::Assumed(d.clone()),
1026                });
1027                None
1028            }
1029            _ => {
1030                let lit = self.lit_of(d).expect("assumed atom must be interned");
1031                if self.set(lit, Reason::Assumption).is_err() {
1032                    Some(ConflictInfo::Clash { assumed: d.clone() })
1033                } else {
1034                    None
1035                }
1036            }
1037        }
1038    }
1039
1040    fn backtrack(&mut self, trail_snap: usize, clause_snap: usize, fired_snap: Vec<bool>) {
1041        while self.trail.len() > trail_snap {
1042            let v = self.trail.pop().unwrap();
1043            self.assign[v] = None;
1044            self.reason[v] = None;
1045        }
1046        self.clauses.truncate(clause_snap);
1047        self.fired_disj = fired_snap;
1048    }
1049
1050    fn emit_conflict(&self, c: Conflict) -> DerivationTree {
1051        match c {
1052            Conflict::Rule(ri) => {
1053                let src = self.rules[ri].src.clone();
1054                let (ante_form, cons_form) = Self::split_implies(&src);
1055                let ante_proof = self.prove_ante(&ante_form, None);
1056                let cons_tree = modus_ponens(cons_form.clone(), leaf(src), ante_proof);
1057                let cons_lit = self
1058                    .lit_of(&cons_form)
1059                    .expect("rule consequent is a literal");
1060                let opp = self.prove_var(cons_lit.var);
1061                make_contradiction(cons_tree, opp)
1062            }
1063            Conflict::Clause(ci) => {
1064                let or_expr = self.clauses[ci].or_expr.clone();
1065                let or_tree = self.materialize_clause(ci);
1066                self.falsum_from_disj(&or_expr, or_tree, usize::MAX)
1067            }
1068        }
1069    }
1070
1071    fn emit_conflict_info(&self, info: ConflictInfo) -> DerivationTree {
1072        match info {
1073            ConflictInfo::Clash { assumed } => {
1074                let lit = self
1075                    .lit_of(&assumed)
1076                    .expect("clashing atom must be interned");
1077                let existing = self.prove_var(lit.var);
1078                make_contradiction(leaf(assumed), existing)
1079            }
1080            ConflictInfo::Rule(ri) => self.emit_conflict(Conflict::Rule(ri)),
1081            ConflictInfo::Clause(ci) => self.emit_conflict(Conflict::Clause(ci)),
1082        }
1083    }
1084
1085    // ── Positive-cell goal by closure elimination + search ───────────────────────
1086
1087    /// Prove a positive cell `goal` that propagation alone does not force: find the
1088    /// closure clause it sits in (the row's value disjunction), refute every OTHER
1089    /// value by DPLL search, then the goal survives by disjunctive syllogism.
1090    fn prove_positive_by_closure(&mut self, goal: &ProofExpr) -> Option<DerivationTree> {
1091        let goal_lit = self.lit_of(goal)?;
1092        // The cell can sit in more than one closure clause — its row (the values it may
1093        // take) AND, once column closures are added, its column (the rows that may take
1094        // its value). Both prove it by refuting their OTHER disjuncts. Try them
1095        // FEWEST-LIVE first (the rest already refuted on the trail ⇒ the search opens the
1096        // fewest branches and the proof stays small), but FALL THROUGH to the next on
1097        // failure: trying only one closure would lose completeness when that one's
1098        // refutations exceed the depth bound while another's would have closed.
1099        let mut candidates: Vec<usize> = (0..self.clauses.len())
1100            .filter(|&ci| {
1101                self.clauses[ci]
1102                    .lits
1103                    .as_ref()
1104                    .map_or(false, |ls| ls.contains(&goal_lit) && ls.len() >= 2)
1105            })
1106            .collect();
1107        candidates.sort_by_key(|&ci| self.clause_status(ci).1.len());
1108        for ci in candidates {
1109            let or_expr = self.clauses[ci].or_expr.clone();
1110            let or_tree = self.materialize_clause(ci);
1111            if let Some(tree) = self.extract_by_search(&or_expr, or_tree, goal) {
1112                return Some(tree);
1113            }
1114        }
1115        None
1116    }
1117
1118    /// Like `extract_survivor`, but the non-surviving disjuncts are refuted by SEARCH
1119    /// (assume + derive ⊥ + reductio) rather than read from the trail.
1120    fn extract_by_search(
1121        &mut self,
1122        or_expr: &ProofExpr,
1123        or_tree: DerivationTree,
1124        target: &ProofExpr,
1125    ) -> Option<DerivationTree> {
1126        debug_assert!(
1127            &or_tree.conclusion == or_expr,
1128            "extract_by_search mismatch:\n tree={:?}\n expr={:?}",
1129            or_tree.conclusion,
1130            or_expr
1131        );
1132        match or_expr {
1133            ProofExpr::Or(l, r) => {
1134                if r.as_ref() == target {
1135                    let lneg = self.prove_neg_by_search(l)?;
1136                    Some(disjunction_elim(target.clone(), or_tree, lneg))
1137                } else {
1138                    let rneg = self.prove_neg_by_search(r)?;
1139                    let l_tree = disjunction_elim((**l).clone(), or_tree, rneg);
1140                    self.extract_by_search(l, l_tree, target)
1141                }
1142            }
1143            _ => Some(or_tree),
1144        }
1145    }
1146
1147    /// Prove `¬e` where `e` is a single cell literal OR a sub-disjunction. A literal:
1148    /// directly if already false on the trail, else by assuming it and refuting it (DPLL),
1149    /// discharged by reductio. A disjunction `A ∨ B` (e.g. the whole `CT ∨ FL ∨ KY` to the
1150    /// LEFT of `Maine` when the goal cell is the closure's RIGHTMOST disjunct): assume it
1151    /// and case-split each disjunct to ⊥. Without the disjunction case, a cell that is the
1152    /// last value of its closure could never be proved positively (its left subtree is not
1153    /// a single literal).
1154    fn prove_neg_by_search(&mut self, e: &ProofExpr) -> Option<DerivationTree> {
1155        if let ProofExpr::Or(..) = e {
1156            let bot = self.disj_to_falsum(e)?;
1157            return Some(reductio(e.clone(), bot));
1158        }
1159        let lit = self.lit_of(e)?;
1160        match self.value(lit) {
1161            Some(false) => Some(align_to(self.prove_var(lit.var), &neg_of(e))),
1162            Some(true) => None,
1163            None => {
1164                let trail_snap = self.trail.len();
1165                let clause_snap = self.clauses.len();
1166                let fired_snap = self.fired_disj.clone();
1167                let _ = self.set(lit, Reason::Assumption);
1168                let bot = self.derive_falsum(0);
1169                let result = bot.map(|b| reductio(e.clone(), b));
1170                self.backtrack(trail_snap, clause_snap, fired_snap);
1171                result
1172            }
1173        }
1174    }
1175
1176    /// Derive ⊥ from `e` ASSUMED true (bound as a hypothesis by an enclosing case-split):
1177    /// a disjunction recurses (case-split each arm); a literal contradicts its own searched
1178    /// refutation. Mirrors `falsum_from_disj`, but the disjuncts are refuted by SEARCH
1179    /// rather than read off the trail.
1180    fn disj_to_falsum(&mut self, e: &ProofExpr) -> Option<DerivationTree> {
1181        if let ProofExpr::Or(l, r) = e {
1182            let lb = self.disj_to_falsum(l)?;
1183            let rb = self.disj_to_falsum(r)?;
1184            return Some(disjunction_cases(falsum(), leaf(e.clone()), lb, rb));
1185        }
1186        // `e` is a literal assumed true here; its searched negation closes the branch.
1187        let neg = self.prove_neg_by_search(e)?;
1188        Some(make_contradiction(leaf(e.clone()), neg))
1189    }
1190}
1191
1192const MAX_DEPTH: usize = 64;
1193
1194enum ConflictInfo {
1195    /// An assumed literal clashes with the existing assignment of its variable.
1196    Clash {
1197        assumed: ProofExpr,
1198    },
1199    Rule(usize),
1200    Clause(usize),
1201}
1202
1203/// `Contradiction` from two proofs of opposite polarity, in either order.
1204fn make_contradiction(a: DerivationTree, b: DerivationTree) -> DerivationTree {
1205    if matches!(a.conclusion, ProofExpr::Not(_)) {
1206        contra_align(b, a)
1207    } else {
1208        contra_align(a, b)
1209    }
1210}
1211
1212/// `¬e` (peeling a double negation).
1213fn neg_of(e: &ProofExpr) -> ProofExpr {
1214    match e {
1215        ProofExpr::Not(inner) => (**inner).clone(),
1216        _ => ProofExpr::Not(Box::new(e.clone())),
1217    }
1218}
1219
1220/// Re-orient `tree` (a literal proof) to conclude exactly `want`, inserting an equality
1221/// symmetry (or a symmetry-reductio under a negation) when only the Identity order
1222/// differs.
1223fn align_to(tree: DerivationTree, want: &ProofExpr) -> DerivationTree {
1224    if &tree.conclusion == want {
1225        return tree;
1226    }
1227    match (&tree.conclusion, want) {
1228        (ProofExpr::Identity(a, b), ProofExpr::Identity(c, d)) if a == d && b == c => {
1229            eq_sym(a.clone(), b.clone(), tree)
1230        }
1231        (ProofExpr::Not(ti), ProofExpr::Not(wi)) => match (ti.as_ref(), wi.as_ref()) {
1232            (ProofExpr::Identity(a, b), ProofExpr::Identity(c, d)) if a == d && b == c => {
1233                let assumed = ProofExpr::Identity(c.clone(), d.clone());
1234                let flipped = eq_sym(c.clone(), d.clone(), leaf(assumed.clone()));
1235                let bot = contradiction(flipped, tree);
1236                reductio(assumed, bot)
1237            }
1238            _ => tree,
1239        },
1240        _ => tree,
1241    }
1242}
1243
1244/// Build `Contradiction` from a positive proof and a negation proof, aligning the
1245/// positive side's Identity orientation to the negation's inner term.
1246fn contra_align(pos_tree: DerivationTree, neg_tree: DerivationTree) -> DerivationTree {
1247    let inner = match &neg_tree.conclusion {
1248        ProofExpr::Not(i) => (**i).clone(),
1249        other => other.clone(),
1250    };
1251    let aligned = align_to(pos_tree, &inner);
1252    contradiction(aligned, neg_tree)
1253}
1254
1255/// Solve a single grid cell by propagation and emit its certified derivation. The
1256/// premises must be ground (call `grounding::ground_problem` first). Returns `None`
1257/// when the cell is not forced by propagation alone (it needs search — Phase C) or the
1258/// premises do not classify as a grid.
1259pub fn grid_prove(premises: &[ProofExpr], goal: &ProofExpr) -> Option<DerivationTree> {
1260    let mut solver = compile(premises)?;
1261    // The root fixpoint runs at decision level 0: its assignments are permanent, so
1262    // compound-clause unit propagation is sound to emit linearly here. Every later
1263    // `propagate()` runs under a backtrackable assumption with `at_root` false.
1264    //
1265    solver.at_root = true;
1266    let root = solver.propagate();
1267    solver.at_root = false;
1268    if root.is_err() {
1269        return None;
1270    }
1271    // A goal already forced by propagation (the Phase-B positive-cell path).
1272    if let Some(lit) = solver.lit_of(goal) {
1273        if solver.value(lit) == Some(true) {
1274            return Some(align_to(solver.prove_var(lit.var), goal));
1275        }
1276    }
1277    // A positive cell not forced by propagation: prove it by closure elimination,
1278    // refuting the row's other values via DPLL search.
1279    if !matches!(goal, ProofExpr::Not(_)) && solver.lit_of(goal).is_some() {
1280        if let Some(tree) = solver.prove_positive_by_closure(goal) {
1281            return Some(align_to(tree, goal));
1282        }
1283    }
1284    // A negative goal: assume the atom and refute it by search (DPLL), then reductio.
1285    if let ProofExpr::Not(inner) = goal {
1286        let x_lit = solver.lit_of(inner)?;
1287        match solver.value(x_lit) {
1288            Some(false) => return Some(align_to(solver.prove_var(x_lit.var), goal)),
1289            Some(true) => return None,
1290            None => {
1291                let _ = solver.set(x_lit, Reason::Assumption);
1292                let bot = solver.derive_falsum(0)?;
1293                return Some(reductio((**inner).clone(), bot));
1294            }
1295        }
1296    }
1297    None
1298}
1299
1300#[cfg(test)]
1301#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/grid_solver/tests.rs"]
1302mod tests;