Skip to main content

logicaffeine_proof/
solve.rs

1//! Structure-detecting solve front-end — the auto-dispatcher that puts our whole arsenal behind a
2//! single entry point.
3//!
4//! An opaque CNF is offered, in cost order, to a battery of CHEAP (O(clauses)) structure
5//! recognizers — each *polynomial* on structure that costs plain CDCL/resolution exponentially, and
6//! each FAIL-CLOSED: it claims a verdict only with a re-checked certificate (a Hall witness, a
7//! cutting-plane derivation, a GF(2) refutation, a covering-measure collapse, or — the complete
8//! deciders — a 2-SAT/Horn model). Anything no recognizer fires on is decided by the authoritative
9//! CDCL core. Every recognizer is cheap to apply AND to reject, so the dispatcher is never slower
10//! than the plain solver — only faster when structure is present.
11//!
12//! Routes, in order:
13//! 1. **2-SAT** (`twosat`) — every clause ≤ 2 literals: linear, decides SAT (with model) or UNSAT.
14//! 2. **Horn** (`hornsat`) — every clause ≤ 1 positive literal: linear least-model / refutation.
15//! 3. **LLL** (`lll`) — *satisfiability from sparsity*: when every clause shares variables with few
16//!    others (`e·2^{-w}·(d+1) ≤ 1`), a model is guaranteed and constructed by Moser–Tardos. The
17//!    SAT-side specialist, dual to the UNSAT recognizers below.
18//! 4. **Pigeonhole / Hall** (`pigeonhole::decide_pigeonhole_unsat`) — bipartite-matching infeasibility:
19//!    crushes pigeonhole (PHP) instances of any size in microseconds.
20//! 5. **Cutting planes** (`pseudo_boolean::refute_clausal`) — cardinality refutation.
21//! 6. **Parity / GF(2)** (`xorsat::refute_via_parity`) — XOR/Tseitin linear systems.
22//! 7. **Covering collapse** (`lyapunov::auto_collapse`) — auto-discovers the covering symmetry
23//!    (pigeonhole, clique-colouring, …) or parity collapse with a Lyapunov-certified artifact.
24//! 8. **CDCL** — the authoritative fallback (model on SAT, RUP proof on UNSAT).
25
26use std::collections::HashMap;
27use std::collections::HashSet;
28
29use crate::cdcl::{BudgetedResult, Lit, SolveResult, Solver};
30use crate::lyapunov::{auto_collapse, extract_xor, AutoCollapse};
31use crate::proof::ProofStep;
32use crate::xor_engine::IncXor;
33use crate::xorsat::XorOutcome;
34use crate::ProofExpr;
35
36// NOTE: generic graph-automorphism detection (`symmetry_detect::find_generators`) and its SEL search
37// are deliberately NOT on this hot path — `find_generators` does not scale (measured ~57s on a
38// 1359-variable circuit instance CDCL solves in 4ms), and SEL spins on easy SAT instances. They are
39// *discovery* tools, not competition moves: run offline to learn a family's symmetry, then distill
40// it into a cheap O(clauses) fingerprint here. Everything below is O(clauses) to apply and reject,
41// so the dispatcher is never slower than the plain CDCL solver.
42
43/// Which engine decided the instance.
44#[derive(Clone, Copy, Debug, PartialEq, Eq)]
45pub enum Route {
46    TwoSat,
47    Horn,
48    Lll,
49    Pigeonhole,
50    CuttingPlanes,
51    Parity,
52    /// Exactly-one groups harvested from the raw clauses (all-positive clause + full pairwise
53    /// at-most-one) yield `Σ_{v∈g} x_v = 1` over every modulus; Gaussian elimination over small
54    /// fields finds the counting obstruction — the parity sum, the signed bipartite combination —
55    /// with the refutation re-checked fail-closed. The covering-encoded counting crusher.
56    ExactCover,
57    ModP,
58    ModM,
59    Collapse,
60    HybridXor,
61    Sos,
62    Nullstellensatz,
63    SymmetryBreak,
64    NestedSymmetry,
65    Sel,
66    LocalSymmetry,
67    OrbitalBranch,
68    SymmetricProbe,
69    SymmetricBinary,
70    OrbitWeightQuotient,
71    SymmetryPropagate,
72    SymmetricComponent,
73    SymmetrySimplify,
74    SemanticSymmetry,
75    AlmostSymmetry,
76    DeclaredSymmetry,
77    RecursiveBreak,
78    /// The formula is certified to carry no linear/parity symmetry shortcut and is provably rigid, so
79    /// the symmetry arsenal is useless — decided by CDCL with that honest "no shortcut" verdict on record.
80    Incompressible,
81    /// The formula split into independent components with no symmetry relating them; each was solved apart
82    /// through the full arsenal and the verdicts combined (the plain-decomposition analogue of separability).
83    Component,
84    /// Certified bounded variable elimination (Davis–Putnam, non-growing) reduced the formula to `⊥`.
85    /// The missing preprocessing crusher: it refutes bounded-treewidth cores the symmetry/algebra chain
86    /// declared `Incompressible`. Its RUP resolvents + clause deletions are the independently checkable proof.
87    BoundedVarElim,
88    /// The binary-implication graph's SCCs forced `x ≡ ¬x` — the 2-clauses alone refute the formula. Catches
89    /// general (non-pure-2SAT) formulas whose binary sub-part is contradictory, which the pure-TwoSat route
90    /// misses. Certified by a short RUP chain (`(x)`, `(¬x)`, `⊥`), re-checkable by propagation.
91    EquivLit,
92    /// Davis–Putnam bucket elimination refuted the formula with every resolvent width ≤ a cap — a bounded-
93    /// treewidth resolution certificate (`2^w·n`). Covers the medium-treewidth families that BVE's non-growing
94    /// rule misses; declines (leaving `Incompressible`) on the high-treewidth residue where width would blow up.
95    TreeWidth,
96    Cdcl,
97}
98
99/// The verdict; a model on SAT, with any UNSAT certificate carried in [`Solved::proof`].
100#[derive(Clone, Debug)]
101pub enum Answer {
102    Sat(Vec<bool>),
103    Unsat,
104}
105
106/// A decided instance.
107#[derive(Clone, Debug)]
108pub struct Solved {
109    pub answer: Answer,
110    pub via: Route,
111    /// UNSAT certificate as a proof stream where one exists (RUP for the CDCL route); empty for the
112    /// polynomial specialists, which certify internally.
113    pub proof: Vec<ProofStep>,
114    /// CDCL conflicts spent (0 whenever a specialist collapsed the instance without search).
115    pub conflicts: u64,
116}
117
118impl Solved {
119    fn unsat(via: Route) -> Self {
120        Solved {
121            answer: Answer::Unsat,
122            via,
123            proof: Vec::new(),
124            conflicts: 0,
125        }
126    }
127}
128
129/// Decide `clauses` over `num_vars` variables, routing through every cheap specialist before CDCL — the
130/// fast default front-end. For the full arsenal (heavy algebraic + complete symmetry breaking before the
131/// fallback) use [`solve_comprehensive`].
132pub fn solve_structured(num_vars: usize, clauses: &[Vec<Lit>]) -> Solved {
133    structured_prefix(num_vars, clauses).unwrap_or_else(|| cdcl_fallback(num_vars, clauses))
134}
135
136/// The cheap-specialist chain — every route O(clauses) to apply and reject, so the front-end is never
137/// slower than plain CDCL. Returns the decision if a specialist fires, or `None` (the CDCL fallback is
138/// needed). Public so callers that only want the O(clauses) specialist verdict — e.g. a per-node
139/// cofactor-DAG leaf check — can skip the expensive CDCL search entirely.
140pub fn structured_prefix(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Solved> {
141    // 1. 2-SAT: a complete polynomial decision procedure with a model.
142    if let Some(binary) = as_two_sat(clauses) {
143        return Some(match crate::twosat::solve(&binary, num_vars) {
144            crate::twosat::TwoSatOutcome::Sat(model) => Solved {
145                answer: Answer::Sat(model),
146                via: Route::TwoSat,
147                proof: Vec::new(),
148                conflicts: 0,
149            },
150            crate::twosat::TwoSatOutcome::Unsat(_) => Solved::unsat(Route::TwoSat),
151        });
152    }
153
154    // 2. Horn: linear least-model / forward-chaining refutation.
155    if let Some(horn) = as_horn(clauses) {
156        return Some(match crate::hornsat::solve(&horn, num_vars) {
157            crate::hornsat::HornOutcome::Sat(model) => Solved {
158                answer: Answer::Sat(model),
159                via: Route::Horn,
160                proof: Vec::new(),
161                conflicts: 0,
162            },
163            crate::hornsat::HornOutcome::Unsat(_) => Solved::unsat(Route::Horn),
164        });
165    }
166
167    // 3. LLL: satisfiability from sparsity. If the local-lemma condition holds a model is guaranteed;
168    //    construct it with Moser–Tardos. The check is O(clauses) and an empty clause fails it, so this
169    //    only fires on genuinely sparse (SAT) instances and never claims SAT without a re-checked model.
170    if !clauses.is_empty() && crate::lll::lll_certifies_sat(clauses).is_some() {
171        let budget = 1000 + 64 * clauses.len();
172        if let Some(model) =
173            crate::lll::moser_tardos_witness(num_vars, clauses, 0x10C0_5EED_C0DE_F00D, budget)
174        {
175            // Fail-closed: only accept a witness that genuinely satisfies every clause.
176            if clauses.iter().all(|c| {
177                c.iter().any(|l| {
178                    model.get(l.var() as usize).copied().unwrap_or(false) == l.is_positive()
179                })
180            }) {
181                return Some(Solved {
182                    answer: Answer::Sat(model),
183                    via: Route::Lll,
184                    proof: Vec::new(),
185                    conflicts: 0,
186                });
187            }
188        }
189    }
190
191    // 4-6. Polynomial UNSAT recognizers over the formula's ProofExpr view.
192    if let Some(expr) = cnf_to_expr(clauses) {
193        if crate::pigeonhole::decide_pigeonhole_unsat(&expr) {
194            return Some(Solved::unsat(Route::Pigeonhole));
195        }
196        if crate::pseudo_boolean::refute_clausal(&expr) {
197            return Some(Solved::unsat(Route::CuttingPlanes));
198        }
199        if crate::xorsat::refute_via_parity(&expr) {
200            return Some(Solved::unsat(Route::Parity));
201        }
202    }
203
204    // 6¼. Exact-cover lift: harvest exactly-one groups (covering encodings — modular counting,
205    //     domino tilings) and Gaussian-eliminate their `Σ x = 1` equations over GF(2), GF(3), GF(5).
206    //     The equations are consequences over EVERY modulus, so any inconsistency — re-checked
207    //     fail-closed — is a certified UNSAT with zero search. Never claims SAT (declines onward).
208    if let Some(solved) = exact_cover_route(num_vars, clauses) {
209        return Some(solved);
210    }
211
212    // 6½. GF(p)/ℤ/m lift: recover a mod-m one-hot system from the raw clauses and decide it by Gaussian
213    //     elimination over the right field/ring — the parity cut carried to every modulus. Crushes the
214    //     mod-m counting obstruction that GF(2) is blind to and resolution (CDCL, Z3, Kissat) needs
215    //     2^Ω(n) for. Sound: UNSAT carries the certified refutation; a SAT model is re-checked.
216    if let Some(solved) = modp_route(num_vars, clauses) {
217        return Some(solved);
218    }
219
220    // 6. Covering / algebraic collapse: auto-discover the symmetry or parity that flattens it.
221    match auto_collapse(num_vars, clauses) {
222        AutoCollapse::None => {}
223        // Any recognized collapse (covering symmetry, parity, cardinality, …) is a certified UNSAT.
224        _ => return Some(Solved::unsat(Route::Collapse)),
225    }
226
227    // 7. Hybrid XOR: for XOR-heavy formulas (e.g. parity-learning) that are neither pure-XOR nor
228    //    caught above, solve the recovered GF(2) subsystem and seed CDCL with that assignment so it
229    //    starts on the linear-system's solution manifold and only repairs the residual clauses.
230    if let Some(solved) = hybrid_xor(num_vars, clauses) {
231        return Some(solved);
232    }
233
234    // 7½. Sum-of-Squares / Positivstellensatz: a degree-2 algebraic refutation over ℚ for a small core
235    //     no cheaper recognizer caught — the ordered-field cut beyond the linear/parity engines (it
236    //     closes integrality gaps GF(2) cannot see). Sound and bounded (num_vars ≤ 6). A certified-
237    //     specialist backstop; the standalone engine (`crate::sos`) is where its degree-2 power lives.
238    if num_vars <= 6 && crate::sos::sos_refutes(num_vars, clauses) {
239        return Some(Solved::unsat(Route::Sos));
240    }
241
242    // 7¾. Bounded-degree **Nullstellensatz (degree ≤ 3)** — the algebraic obstruction *beyond* SoS's
243    //      degree-2. The residue-map census showed the symmetric-but-uncrushed families sit at
244    //      Nullstellensatz degree 3: their symmetry is *already fully broken* (0 underbroken), so no
245    //      symmetry route can touch them — the only remaining lens is the deeper algebraic one. Small-core
246    //      gated (num_vars ≤ 12) so the fast router stays bounded; sound (a genuine degree-d NS refutation).
247    if num_vars <= 12 {
248        for d in 2..=num_vars.min(3) {
249            if crate::polycalc::nullstellensatz_refutes(num_vars, clauses, d) {
250                return Some(Solved::unsat(Route::Nullstellensatz));
251            }
252        }
253    }
254
255    None
256}
257
258/// **The exact-cover lift.** Harvest every exactly-one group — an all-positive clause of size ≥ 2
259/// whose variables are pairwise at-most-one-forbidden — and read off the equation `Σ_{v∈g} x_v = 1`.
260/// Exactly-one semantics makes the equation a valid consequence over *every* modulus, so the group
261/// system is checked for inconsistency by Gaussian elimination over `GF(2)` (via `xorsat`) and
262/// `GF(3)`, `GF(5)` (via `modp`); every refutation is re-checked fail-closed before the route
263/// reports. This is the covering-encoded face of the counting cut: `Count_2`'s parity sum, the
264/// mutilated chessboard's black-minus-white combination (a `GF(3)` linear dependency the Gaussian
265/// finds unaided), the mod-3/5 sums of `Count_{3,5}`. UNSAT-only: a consistent system proves
266/// nothing about the rest of the formula, so the route declines rather than guess.
267fn exact_cover_route(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Solved> {
268    use std::collections::HashSet;
269    let mut amo: HashSet<(u32, u32)> = HashSet::new();
270    for c in clauses {
271        if c.len() == 2 && c.iter().all(|l| !l.is_positive()) {
272            let (a, b) = (c[0].var(), c[1].var());
273            amo.insert((a.min(b), a.max(b)));
274        }
275    }
276    if amo.is_empty() {
277        return None;
278    }
279    let mut groups: Vec<Vec<u32>> = Vec::new();
280    for c in clauses {
281        if c.len() < 2 || !c.iter().all(|l| l.is_positive()) {
282            continue;
283        }
284        let mut g: Vec<u32> = c.iter().map(|l| l.var()).collect();
285        g.sort_unstable();
286        g.dedup();
287        if g.len() != c.len() {
288            continue;
289        }
290        let full_amo = (0..g.len()).all(|i| (i + 1..g.len()).all(|j| amo.contains(&(g[i], g[j]))));
291        if full_amo {
292            groups.push(g);
293        }
294    }
295    if groups.len() < 2 {
296        return None; // one equation is never inconsistent — nothing to combine
297    }
298    // GF(2): the parity rung, certificate re-checked by the XOR checker.
299    let eqs: Vec<crate::xorsat::XorEquation> = groups
300        .iter()
301        .map(|g| {
302            crate::xorsat::XorEquation::new(g.iter().map(|&v| v as usize).collect::<Vec<_>>(), true)
303        })
304        .collect();
305    if let crate::xorsat::XorOutcome::Unsat(refutation) = crate::xorsat::solve(&eqs, num_vars) {
306        if crate::xorsat::is_refutation(&eqs, num_vars, &refutation) {
307            return Some(Solved::unsat(Route::ExactCover));
308        }
309    }
310    // GF(3), GF(5): the higher rungs of the same harvest, re-checked by the mod-p checker.
311    for p in [3u64, 5] {
312        let meqs: Vec<crate::modp::ModpEquation> = groups
313            .iter()
314            .map(|g| {
315                crate::modp::ModpEquation::new(
316                    g.iter().map(|&v| (v as usize, 1u64)).collect::<Vec<_>>(),
317                    1,
318                )
319            })
320            .collect();
321        if let crate::modp::ModpOutcome::Unsat(combo) = crate::modp::solve(&meqs, num_vars, p) {
322            if crate::modp::is_refutation(&meqs, num_vars, p, &combo) {
323                return Some(Solved::unsat(Route::ExactCover));
324            }
325        }
326    }
327    None
328}
329
330/// The authoritative CDCL fallback — enriched with the mined clause bundle: every structure-mining
331/// contributor's implied no-goods, unioned into the formula so CDCL inherits the discovered structure.
332/// Sound (only implied clauses) and never-worse.
333fn cdcl_fallback(num_vars: usize, clauses: &[Vec<Lit>]) -> Solved {
334    let mut solver = Solver::new(num_vars);
335    for c in clauses {
336        solver.add_clause(c.clone());
337    }
338    for c in mine_clauses(num_vars, clauses) {
339        solver.add_clause(c);
340    }
341    match solver.solve() {
342        SolveResult::Sat(model) => Solved {
343            answer: Answer::Sat(model),
344            via: Route::Cdcl,
345            proof: Vec::new(),
346            conflicts: solver.conflicts(),
347        },
348        SolveResult::Unsat => {
349            let proof = solver
350                .learned()
351                .iter()
352                .map(|lc| ProofStep::Rup(lc.lits.clone()))
353                .collect();
354            Solved {
355                answer: Answer::Unsat,
356                via: Route::Cdcl,
357                proof,
358                conflicts: solver.conflicts(),
359            }
360        }
361    }
362}
363
364/// **The full arsenal in one call** — the opt-in power-mode solver. Runs the cheap specialists
365/// ([`structured_prefix`]); then, *before* the exponential CDCL fallback, the heavier engines the fast
366/// path skips: bounded-degree **Nullstellensatz / Polynomial Calculus** (the nonlinear algebraic
367/// refutation, [`crate::polycalc`]) and **complete lex-leader symmetry breaking** ([`crate::sym_break`]:
368/// the whole automorphism group from the Schreier–Sims backend, feeding CDCL a one-model-per-orbit
369/// formula). Slower than [`solve_structured`] (it may run Nullstellensatz and automorphism detection),
370/// so it is the maximum-power entry, not the default. Always correct — the CDCL fallback is complete.
371pub fn solve_comprehensive(num_vars: usize, clauses: &[Vec<Lit>]) -> Solved {
372    if let Some(s) = structured_prefix(num_vars, clauses) {
373        return s;
374    }
375    // Certified bounded variable elimination: eliminate every non-growing variable (Davis–Putnam) to a
376    // fixpoint. If the residue contains `⊥`, that IS a certified (RUP) refutation — the bounded-treewidth
377    // crusher the fast chain lacks. Runs before the incompressibility verdict so bve-easy cores are decided
378    // honestly (they were never truly rigid-hard) rather than mislabeled `Incompressible`.
379    // Certified equivalent-literal detection: the binary-implication graph's SCCs. If some `x ≡ ¬x` the
380    // 2-clauses alone refute the formula (a contradictory binary sub-part the pure-TwoSat route, which needs a
381    // fully-binary formula, does not see). Cheap (Tarjan on the 2-clauses) and certified by a short RUP chain.
382    if let crate::inprocess::EquivResult::Unsat(steps) =
383        crate::inprocess::equivalent_literal_scc(num_vars, clauses)
384    {
385        return Solved {
386            answer: Answer::Unsat,
387            via: Route::EquivLit,
388            proof: steps,
389            conflicts: 0,
390        };
391    }
392    let (reduced, steps) = crate::inprocess::bve(num_vars, clauses);
393    if reduced.iter().any(|c| c.is_empty()) {
394        return Solved {
395            answer: Answer::Unsat,
396            via: Route::BoundedVarElim,
397            proof: steps,
398            conflicts: 0,
399        };
400    }
401    // Certified bucket elimination (tree-width): full Davis–Putnam in min-degree order, capping resolvent width.
402    // A refutation within the cap is a `2^cap·n` resolution certificate — crushes bounded-treewidth families
403    // BVE's non-growing rule misses. Declines on the high-treewidth residue (width exceeds the cap).
404    if let Some(steps) = crate::inprocess::bucket_elimination_refute(num_vars, clauses, 12) {
405        return Solved {
406            answer: Answer::Unsat,
407            via: Route::TreeWidth,
408            proof: steps,
409            conflicts: 0,
410        };
411    }
412    // Certified incompressibility: if the formula's parity structure is fully exposed AND it is provably
413    // rigid (|Aut| = 1, no symmetry to exploit — the exact check is size-gated so it stays cheap), then
414    // the entire symmetry arsenal below is provably useless on it. Decide it with CDCL and record the
415    // honest "no shortcut of this class" route. Fail-closed: any doubt falls through unchanged.
416    if crate::ait::incompressibility_gate(num_vars, clauses).is_some() {
417        let mut solved = cdcl_fallback(num_vars, clauses);
418        solved.via = Route::Incompressible;
419        return solved;
420    }
421    // Symmetric COMPONENT decomposition: when the formula splits into independent components and the
422    // automorphism group maps some onto each other (isomorphic copies), solve one representative per
423    // component-orbit and replicate its model through the symmetry — `k` identical sub-problems for the
424    // price of one. Each representative goes back through the full arsenal recursively.
425    if let Some(s) = symmetric_component_solve(num_vars, clauses) {
426        return s;
427    }
428    // Symmetry hidden by units: propagate the formula's unit clauses, then detect symmetry on the
429    // SIMPLIFIED residual. Units can mask automorphisms the raw-formula routes structurally cannot see;
430    // once revealed, the residual is solved with the full arsenal and the forced assignment re-applied.
431    if let Some(s) = symmetry_via_simplification_solve(num_vars, clauses) {
432        return s;
433    }
434    // Orbit-weight QUOTIENT: when the symmetry group is the full product of symmetric groups on its
435    // orbits, satisfiability depends only on the per-orbit weights — so the whole 2ⁿ space collapses to
436    // Π(|Oᵢ|+1) weight-tuple representatives, decided exactly by evaluation. Complete, not just sound.
437    if let Some(s) = orbit_weight_quotient_solve(num_vars, clauses) {
438        return s;
439    }
440    // Nonlinear algebraic: a degree-d Nullstellensatz refutation (subsumes parity at d=1; d ≥ 2 reaches
441    // counting-style obstructions). Bounded to the explicit-monomial regime.
442    if num_vars <= 16 {
443        for d in 2..=num_vars.min(3) {
444            if crate::polycalc::nullstellensatz_refutes(num_vars, clauses, d) {
445                return Solved::unsat(Route::Nullstellensatz);
446            }
447        }
448    }
449    // Dynamic in-CDCL symmetry breaking — Symmetric Explanation Learning. Amplify each learned clause by
450    // the symmetry group during a budgeted search, so symmetric conflicts are never re-derived (the
451    // conflict count collapses on symmetry-rich instances). For symmetric UNSAT it usually wins outright;
452    // a SAT model or an honest Unknown falls through to the static / complete routes.
453    if let Some(s) = dynamic_sel(num_vars, clauses) {
454        return s;
455    }
456    // Symmetric inference (not breaking): probe one representative per literal-orbit for a failed literal
457    // (`F ∧ ℓ` UNSAT ⟹ `F ⊨ ¬ℓ`); symmetry then forces the *whole orbit* false from that single probe.
458    // The strengthened formula is solved directly. Sound — it only adds implied units.
459    if let Some(s) = symmetric_probe_solve(num_vars, clauses) {
460        return s;
461    }
462    // Symmetric hyper-binary inference: where the probe derives a UNIT (a failed literal), this derives an
463    // IMPLICATION — BCP under `ℓ` forcing `m` means `F ⊨ ℓ→m` — and symmetry adds the whole orbit of that
464    // binary clause from one probe. Sound (only implied clauses); strengthens the formula, then solves.
465    if let Some(s) = symmetric_binary_inference_solve(num_vars, clauses) {
466        return s;
467    }
468    // Nested (multi-dimensional) symmetry: a grid of three or more axes has a TOWER of block systems
469    // (cells ⊂ lines ⊂ planes ⊂ …), not just one. Break structured swaps at every level of the tower,
470    // each verified to lie in the group — the d-dimensional generalisation of the 2-D double-lex break.
471    if let Some(s) = nested_symmetry_solve(num_vars, clauses) {
472        return s;
473    }
474    // Orbital branching — break symmetry in the decision tree, not by clauses. When a large variable orbit
475    // exists, fixing one representative collapses all its symmetric "some-member-true" branches into one,
476    // so the search explores a single branch where a complete lex-leader would still enumerate the orbit.
477    if let Some(s) = orbital_branch_solve(num_vars, clauses) {
478        return s;
479    }
480    // Symmetry breaking DURING search (SBDS): a lex-leader propagator enforces `a ≤ₗₑₓ a∘g` for each
481    // generator dynamically through the DPLL(T) interface — no static SBP clauses, no aux variables.
482    if let Some(s) = symmetry_propagate_solve(num_vars, clauses) {
483        return s;
484    }
485    // Static complete/partial symmetry breaking (handles SAT, and is complete): add the lex-leader
486    // predicate and let CDCL decide the broken formula.
487    if let Some(s) = symmetry_break_solve(num_vars, clauses) {
488        return s;
489    }
490    // Local symmetry breaking: split on a variable whose residuals carry the most conditional symmetry,
491    // break each residual's symmetry, and solve the branches — exploiting symmetry that emerges only down
492    // a branch, invisible to the global routes above.
493    if let Some(s) = local_symmetry_solve(num_vars, clauses) {
494        return s;
495    }
496    // Semantic symmetry: a permutation that preserves the MODEL SET (`F ≡ σ(F)`) without preserving the
497    // clause set — invisible to the syntactic detector. Detected by logical implication, broken by the
498    // (sound-for-any-model-preserving-permutation) lex-leader. The last symmetry route before search.
499    if let Some(s) = semantic_symmetry_solve(num_vars, clauses) {
500        return s;
501    }
502    // Almost-symmetry: a swap that preserves all but a few clauses is an automorphism of the rest, so it
503    // maps a model to a model only when the broken clauses' images also hold — break it CONDITIONALLY,
504    // guarded by those images. The weakest, most general symmetry; the last route before search.
505    if let Some(s) = almost_symmetry_solve(num_vars, clauses) {
506        return s;
507    }
508    // The hard ones: nothing above decided it. Try the RECURSIVE breaker — iterate detect-and-break to a
509    // fixpoint (composing symmetry that earlier single passes leave behind), then decide the reduced
510    // formula by search. Fires only when it actually breaks symmetry; otherwise the plain CDCL fallback.
511    if let Some(s) = recursive_break_solve(num_vars, clauses) {
512        return s;
513    }
514    // Fused parity + cardinality — applied BEFORE the affine reduction so a *mixed* instance (one carrying
515    // BOTH a recovered GF(2) parity substructure AND an at-most-one cardinality substructure) is decided by
516    // the two live theories reasoning together on one trail, rather than letting the affine rung reduce only
517    // its linear half. Gated on both substructures, so pure-parity / pure-cardinality instances fall through
518    // untouched to the affine and covering routes below.
519    if let Some(s) = fused_modular_solve(num_vars, clauses) {
520        return s;
521    }
522    // Affine (GF(2)) reduction — the symmetry every breaker above is *structurally* blind to: a shear
523    // `xᵢ↦xᵢ⊕xⱼ` maps a clause to a non-subcube, so no clause permutation can reach it. Recover the
524    // formula's linear substructure and Gauss-eliminate it — an inconsistent linear core refutes outright
525    // (a GF(2) obstruction, hence Route::Parity), and otherwise the derived forced units / equivalences
526    // (linear consequences no single clause states) strengthen the formula for the CDCL fallback.
527    match crate::affine::affine_canonicalize(num_vars, clauses) {
528        crate::affine::AffineCanon::Refuted(drat) => {
529            // Carry the xor_drat certificate: the GF(2) linear-dependency refutation compiled to RUP
530            // resolvents, drat-trim-checkable against the original CNF (None only if the resolution
531            // expansion overran its budget — the verdict still stands on the algebraic certificate).
532            let proof = drat
533                .map(|res| res.into_iter().map(ProofStep::Rup).collect())
534                .unwrap_or_default();
535            return Solved {
536                answer: Answer::Unsat,
537                via: Route::Parity,
538                proof,
539                conflicts: 0,
540            };
541        }
542        crate::affine::AffineCanon::Canonical(canon) => {
543            // The canonical RREF break: solve the formula reduced to its free generators, then lift the
544            // model back through the affine quotient. UNSAT of the reduced ⇒ UNSAT of the original.
545            let sub = cdcl_fallback(canon.num_vars, &canon.clauses);
546            return match sub.answer {
547                Answer::Unsat => Solved {
548                    answer: Answer::Unsat,
549                    via: sub.via,
550                    proof: Vec::new(),
551                    conflicts: sub.conflicts,
552                },
553                Answer::Sat(model) => {
554                    let lifted = canon.lift(&model);
555                    // Fail-closed: the lifted model must satisfy the original formula.
556                    if clauses.iter().all(|c| {
557                        c.iter()
558                            .any(|l| lifted[l.var() as usize] == l.is_positive())
559                    }) {
560                        Solved {
561                            answer: Answer::Sat(lifted),
562                            via: sub.via,
563                            proof: Vec::new(),
564                            conflicts: sub.conflicts,
565                        }
566                    } else {
567                        cdcl_fallback(num_vars, clauses) // defensive: re-solve raw (unreachable for a sound lift)
568                    }
569                }
570            };
571        }
572        crate::affine::AffineCanon::Unchanged => {}
573    }
574    // The GF(p) affine break — the one-hot mod-p analogue of the GF(2) RREF reduction above. An
575    // inconsistent mod-p core refutes (Route::ModP); otherwise *eliminate* the determined one-hot groups
576    // (forced bits → constants, value-permuted linked bits → aliases), solve the reduced formula, and lift
577    // the model back through the affine quotient (fail-closed). UNSAT of the reduced ⇒ UNSAT of the original.
578    match crate::affine_gfp::affine_p_canonicalize(num_vars, clauses) {
579        crate::affine_gfp::AffinePCanon::Refuted(drat) => {
580            let proof = drat
581                .map(|res| res.into_iter().map(ProofStep::Rup).collect())
582                .unwrap_or_default();
583            return Solved {
584                answer: Answer::Unsat,
585                via: Route::ModP,
586                proof,
587                conflicts: 0,
588            };
589        }
590        crate::affine_gfp::AffinePCanon::Canonical(canon) => {
591            let sub = cdcl_fallback(canon.num_vars, &canon.clauses);
592            return match sub.answer {
593                Answer::Unsat => Solved {
594                    answer: Answer::Unsat,
595                    via: sub.via,
596                    proof: Vec::new(),
597                    conflicts: sub.conflicts,
598                },
599                Answer::Sat(model) => {
600                    let lifted = canon.lift(&model);
601                    if clauses.iter().all(|c| {
602                        c.iter()
603                            .any(|l| lifted[l.var() as usize] == l.is_positive())
604                    }) {
605                        Solved {
606                            answer: Answer::Sat(lifted),
607                            via: sub.via,
608                            proof: Vec::new(),
609                            conflicts: sub.conflicts,
610                        }
611                    } else {
612                        cdcl_fallback(num_vars, clauses) // defensive: re-solve raw (unreachable for a sound lift)
613                    }
614                }
615            };
616        }
617        crate::affine_gfp::AffinePCanon::Unchanged => {}
618    }
619    // The composite ℤ/m affine break — the same eliminate-and-lift move over a one-hot encoding with a
620    // composite modulus, decomposed by CRT into the prime-power components (Smith normal form per ring). An
621    // inconsistent ring core refutes (Route::ModM); otherwise the forced / partially-forced / ring-linked
622    // groups are eliminated, the reduced formula solved, and its model lifted (fail-closed).
623    match crate::affine_gfp::affine_m_canonicalize(num_vars, clauses) {
624        crate::affine_gfp::AffinePCanon::Refuted(drat) => {
625            let proof = drat
626                .map(|res| res.into_iter().map(ProofStep::Rup).collect())
627                .unwrap_or_default();
628            return Solved {
629                answer: Answer::Unsat,
630                via: Route::ModM,
631                proof,
632                conflicts: 0,
633            };
634        }
635        crate::affine_gfp::AffinePCanon::Canonical(canon) => {
636            let sub = cdcl_fallback(canon.num_vars, &canon.clauses);
637            return match sub.answer {
638                Answer::Unsat => Solved {
639                    answer: Answer::Unsat,
640                    via: sub.via,
641                    proof: Vec::new(),
642                    conflicts: sub.conflicts,
643                },
644                Answer::Sat(model) => {
645                    let lifted = canon.lift(&model);
646                    if clauses.iter().all(|c| {
647                        c.iter()
648                            .any(|l| lifted[l.var() as usize] == l.is_positive())
649                    }) {
650                        Solved {
651                            answer: Answer::Sat(lifted),
652                            via: sub.via,
653                            proof: Vec::new(),
654                            conflicts: sub.conflicts,
655                        }
656                    } else {
657                        cdcl_fallback(num_vars, clauses) // defensive: re-solve raw (unreachable for a sound lift)
658                    }
659                }
660            };
661        }
662        crate::affine_gfp::AffinePCanon::Unchanged => {}
663    }
664    // Plain component decomposition: nothing above split it, but if the formula still separates into
665    // independent components, solve each apart through the full arsenal — a component may match a route the
666    // whole formula did not — and combine, fail-closed. The last structural move before raw search.
667    if let Some(s) = component_solve(num_vars, clauses) {
668        return s;
669    }
670    cdcl_fallback(num_vars, clauses)
671}
672
673/// Decide via the **recursive breaker** as a dispatcher route for hard instances: iterate symmetry
674/// detection and breaking to a fixpoint ([`break_all_symmetry`], aux-free), then solve the reduced formula
675/// with CDCL. Sound — the breaker is equisatisfiable, so a model satisfies the original (re-checked
676/// fail-closed) and an UNSAT verdict carries over. `None` when no symmetry is broken (the plain fallback
677/// then handles it).
678fn recursive_break_solve(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Solved> {
679    if num_vars == 0 || num_vars > 64 {
680        return None;
681    }
682    let broken = break_all_symmetry(num_vars, clauses);
683    if broken.len() == clauses.len() {
684        return None; // nothing broken ⇒ defer to the plain CDCL fallback
685    }
686    let mut solver = Solver::new(num_vars);
687    for c in &broken {
688        solver.add_clause(c.clone());
689    }
690    match solver.solve() {
691        SolveResult::Sat(model) => {
692            let projected: Vec<bool> = model[..num_vars].to_vec();
693            clauses
694                .iter()
695                .all(|c| {
696                    c.iter()
697                        .any(|l| projected[l.var() as usize] == l.is_positive())
698                })
699                .then_some(Solved {
700                    answer: Answer::Sat(projected),
701                    via: Route::RecursiveBreak,
702                    proof: Vec::new(),
703                    conflicts: solver.conflicts(),
704                })
705        }
706        SolveResult::Unsat => Some(Solved {
707            answer: Answer::Unsat,
708            via: Route::RecursiveBreak,
709            proof: Vec::new(),
710            conflicts: solver.conflicts(),
711        }),
712    }
713}
714
715/// Decide by a one-level **local-symmetry branch**: pick the variable whose two residuals carry the most
716/// conditional symmetry (fixing that variable), split on it, break each residual's local symmetry, and
717/// solve the branches with CDCL. `F` is SAT iff either branch is. Sound: a residual symmetry `σ` is used
718/// only if it FIXES the branched variable (so it permutes that branch's models), making the lex-leader
719/// sound for the branch. `None` if no branch reveals usable local symmetry (CDCL handles it) or the
720/// instance is too large for the per-variable residual scan.
721fn local_symmetry_solve(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Solved> {
722    if num_vars == 0 || num_vars > 24 {
723        return None;
724    }
725    // Residual symmetry generators for the branch `lit`, keeping only those that fix the branched variable.
726    let fixed_gens = |lit: Lit| -> Vec<Vec<Lit>> {
727        let v = lit.var() as usize;
728        crate::sym_break::conditional_symmetry_generators(num_vars, clauses, &[lit])
729            .into_iter()
730            .filter(|img| img[v] == Lit::pos(v as u32))
731            .collect()
732    };
733    let mut best: Option<usize> = None;
734    let mut best_score = 0usize;
735    for v in 0..num_vars {
736        let score = fixed_gens(Lit::pos(v as u32)).len() + fixed_gens(Lit::neg(v as u32)).len();
737        if score > best_score {
738            best_score = score;
739            best = Some(v);
740        }
741    }
742    let v = best?; // no branch reveals usable local symmetry
743
744    let mut conflicts = 0u64;
745    for polarity in [false, true] {
746        let lit = Lit::new(v as u32, polarity);
747        let (sbp, total) = crate::sym_break::lex_leader_sbp_lit(num_vars, &fixed_gens(lit));
748        let mut solver = Solver::new(total.max(num_vars));
749        for c in clauses {
750            solver.add_clause(c.clone());
751        }
752        solver.add_clause(vec![lit]); // commit the branch
753        for c in &sbp {
754            solver.add_clause(c.clone());
755        }
756        match solver.solve() {
757            SolveResult::Sat(model) => {
758                return Some(Solved {
759                    answer: Answer::Sat(model[..num_vars].to_vec()),
760                    via: Route::LocalSymmetry,
761                    proof: Vec::new(),
762                    conflicts: conflicts + solver.conflicts(),
763                });
764            }
765            SolveResult::Unsat => conflicts += solver.conflicts(),
766        }
767    }
768    Some(Solved {
769        answer: Answer::Unsat,
770        via: Route::LocalSymmetry,
771        proof: Vec::new(),
772        conflicts,
773    })
774}
775
776/// Dynamic in-CDCL symmetry breaking — Symmetric Explanation Learning ([`crate::sym_dynamic::sel_refute`]).
777/// During a budgeted CDCL search, each learned clause is multiplied by the formula's symmetry group, so
778/// symmetric conflicts are learned for free and symmetric subtrees are never re-explored. Sound:
779/// UNSAT carries a checked PR/RUP proof, SAT a model, else an honest Unknown. Gated by a quick symmetry
780/// check (skip if the formula is asymmetric — SEL would just burn budget) and `num_vars ≤ 64`.
781fn dynamic_sel(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Solved> {
782    use crate::sym_dynamic::{sel_refute, SelOutcome};
783    if num_vars > 64
784        || crate::sym_break::literal_automorphism_generators(num_vars, clauses).is_empty()
785    {
786        return None;
787    }
788    match sel_refute(num_vars, clauses) {
789        SelOutcome::Unsat {
790            steps, conflicts, ..
791        } => Some(Solved {
792            answer: Answer::Unsat,
793            via: Route::Sel,
794            proof: steps,
795            conflicts,
796        }),
797        SelOutcome::Sat(model) => Some(Solved {
798            answer: Answer::Sat(model),
799            via: Route::Sel,
800            proof: Vec::new(),
801            conflicts: 0,
802        }),
803        SelOutcome::Unknown { .. } => None,
804    }
805}
806
807/// Decide via complete symmetry breaking: detect the variable-automorphism group (Schreier–Sims
808/// backend), add the complete lex-leader SBP, and run CDCL on the broken formula. `None` when there is no
809/// usable (phase-free, moderate, non-trivial) symmetry, the instance is too large for automorphism
810/// detection, or the model fails the fail-closed re-check.
811fn symmetry_break_solve(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Solved> {
812    if num_vars > 64 {
813        return None; // automorphism detection does not scale; leave it to CDCL
814    }
815    // Literal symmetries — variable AND value/phase — as image-literal vectors, on the 2·num_vars points.
816    let gens = crate::sym_break::literal_automorphism_generators(num_vars, clauses);
817    if gens.is_empty() {
818        return None; // no non-trivial symmetry
819    }
820    let point_gens: Vec<_> = gens
821        .iter()
822        .map(|s| crate::sym_break::litsym_to_points(s, num_vars))
823        .collect();
824    let bsgs = crate::permgroup::schreier_sims(2 * num_vars, &point_gens);
825    if bsgs.order() <= 1 {
826        return None;
827    }
828    // Choose the break by group size and structure:
829    //   • small group       → COMPLETE break (exactly one model per orbit, optimal);
830    //   • large grid         → HIERARCHICAL block-wise break (polynomial, structured — for the imprimitive
831    //                          product symmetries the complete enumeration could never touch);
832    //   • large non-grid     → stabilizer-chain break (generators ∪ transversal coset reps, polynomial).
833    let (sbp, total) = match bsgs.elements(50_000) {
834        Some(pts) => crate::sym_break::lex_leader_sbp_lit(
835            num_vars,
836            &pts.iter()
837                .map(|p| crate::sym_break::litsym_from_points(p, num_vars))
838                .collect::<Vec<_>>(),
839        ),
840        None => crate::sym_break::hierarchical_break(num_vars, clauses).unwrap_or_else(|| {
841            let mut s = gens;
842            s.extend(
843                bsgs.transversal_elements()
844                    .iter()
845                    .map(|p| crate::sym_break::litsym_from_points(p, num_vars)),
846            );
847            crate::sym_break::lex_leader_sbp_lit(num_vars, &s)
848        }),
849    };
850    let mut solver = Solver::new(total);
851    for c in clauses {
852        solver.add_clause(c.clone());
853    }
854    for c in &sbp {
855        solver.add_clause(c.clone());
856    }
857    match solver.solve() {
858        SolveResult::Sat(model) => {
859            let projected: Vec<bool> = model[..num_vars].to_vec();
860            // Fail-closed: the projection must satisfy the original formula.
861            clauses
862                .iter()
863                .all(|c| {
864                    c.iter()
865                        .any(|l| projected[l.var() as usize] == l.is_positive())
866                })
867                .then_some(Solved {
868                    answer: Answer::Sat(projected),
869                    via: Route::SymmetryBreak,
870                    proof: Vec::new(),
871                    conflicts: solver.conflicts(),
872                })
873        }
874        SolveResult::Unsat => Some(Solved::unsat(Route::SymmetryBreak)),
875    }
876}
877
878/// Decide via **recursive orbital branching** (Margot) — symmetry breaking in the *decision tree* rather
879/// than by added clauses, applied down the whole tree. For a variable orbit `O` under the residual
880/// automorphism group, "*some* variable in `O` is true" is symmetric to "*the representative* `O[0]` is
881/// true" (the group is transitive on `O`, and an automorphism maps models to models). So
882///
883/// > `F` is SAT  ⟺  `F ∧ (rep = true)` is SAT  **or**  `F ∧ (all of O false)` is SAT,
884///
885/// collapsing the `|O|` symmetric "some-`O`-true" branches into a single representative branch. The
886/// representative branch still carries the residual symmetry (the generators fixing `rep`), so we recurse
887/// — at every node taking the largest free-variable orbit of the generators that fix the committed
888/// variables — until the residual is asymmetric and plain CDCL finishes. Sound at each level by the
889/// orbital argument; the filtered generators are a genuine subgroup of the residual's automorphisms (an
890/// under-approximation: always correct, never enumerates more than the true group would). Every model is
891/// re-checked fail-closed; UNSAT is returned only when both branches are genuinely UNSAT. `None` when
892/// there is no phase-free variable symmetry with an orbit of size ≥ 3 (nothing to collapse) or the
893/// instance is too large for automorphism detection.
894fn orbital_branch_solve(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Solved> {
895    if num_vars == 0 || num_vars > 64 {
896        return None;
897    }
898    // Variable (phase-free) automorphisms — orbital branching reasons about variable orbits, so a phase
899    // flip (which sends a literal to its negation) is not a usable generator here.
900    let gens = crate::sym_break::variable_automorphism_generators(num_vars, clauses)?;
901    if gens.is_empty() {
902        return None;
903    }
904    // Gate: a ≥3 orbit somewhere is the reduction over the plain two-branch baseline that earns the route.
905    if !crate::permgroup::orbits(num_vars, &gens)
906        .iter()
907        .any(|o| o.len() >= 3)
908    {
909        return None;
910    }
911    let mut conflicts = 0u64;
912    let mut budget = 1024u64; // node cap; on exhaustion a node finishes its residual with plain CDCL
913    let answer = orbital_node(
914        num_vars,
915        clauses,
916        &gens,
917        &mut Vec::new(),
918        &mut budget,
919        &mut conflicts,
920    )?;
921    Some(Solved {
922        answer,
923        via: Route::OrbitalBranch,
924        proof: Vec::new(),
925        conflicts,
926    })
927}
928
929/// One node of the recursive orbital-branching tree over the residual `clauses ∧ committed`. Returns the
930/// node's verdict, or `None` if a returned model fails its fail-closed re-check (the caller must then
931/// decline rather than conclude UNSAT).
932fn orbital_node(
933    num_vars: usize,
934    clauses: &[Vec<Lit>],
935    gens: &[crate::permgroup::Perm],
936    committed: &mut Vec<Lit>,
937    budget: &mut u64,
938    conflicts: &mut u64,
939) -> Option<Answer> {
940    let checked = |m: Vec<bool>| -> Option<Answer> {
941        clauses
942            .iter()
943            .all(|c| c.iter().any(|l| m[l.var() as usize] == l.is_positive()))
944            .then_some(Answer::Sat(m))
945    };
946    // Residual symmetry: the generators that fix every committed variable (so they preserve the unit
947    // commitments) — a genuine subgroup of the residual formula's automorphisms.
948    let committed_vars: HashSet<usize> = committed.iter().map(|l| l.var() as usize).collect();
949    let live: Vec<crate::permgroup::Perm> = if committed_vars.is_empty() {
950        gens.to_vec()
951    } else {
952        gens.iter()
953            .filter(|g| committed_vars.iter().all(|&v| g[v] == v))
954            .cloned()
955            .collect()
956    };
957    // Largest free-variable orbit (committed variables are fixed points of `live`, hence singletons).
958    let orbit = (*budget > 0)
959        .then(|| {
960            crate::permgroup::orbits(num_vars, &live)
961                .into_iter()
962                .filter(|o| o.len() >= 2 && o.iter().all(|v| !committed_vars.contains(v)))
963                .max_by_key(|o| o.len())
964        })
965        .flatten();
966    let orbit = match orbit {
967        Some(o) => o,
968        None => return solve_residual(num_vars, clauses, committed, conflicts), // asymmetric / budget out
969    };
970    *budget -= 1;
971    let rep = orbit[0];
972
973    // Branch A: rep = true — the representative of every model in which some orbit member is true.
974    committed.push(Lit::pos(rep as u32));
975    let a = orbital_node(num_vars, clauses, gens, committed, budget, conflicts);
976    committed.pop();
977    match a {
978        Some(Answer::Sat(m)) => return checked(m),
979        None => return None, // branch A undecidable ⟹ this node is undecidable (fail-closed)
980        Some(Answer::Unsat) => {}
981    }
982
983    // Branch B: every orbit member false — the only models branch A does not cover.
984    let n0 = committed.len();
985    committed.extend(orbit.iter().map(|&v| Lit::neg(v as u32)));
986    let b = orbital_node(num_vars, clauses, gens, committed, budget, conflicts);
987    committed.truncate(n0);
988    match b {
989        Some(Answer::Sat(m)) => checked(m),
990        Some(Answer::Unsat) => Some(Answer::Unsat), // both branches genuinely UNSAT ⟹ node UNSAT
991        None => None,
992    }
993}
994
995/// CDCL the residual `clauses ∧ committed` — the base case of [`orbital_node`].
996fn solve_residual(
997    num_vars: usize,
998    clauses: &[Vec<Lit>],
999    committed: &[Lit],
1000    conflicts: &mut u64,
1001) -> Option<Answer> {
1002    let mut s = Solver::new(num_vars);
1003    for c in clauses {
1004        s.add_clause(c.clone());
1005    }
1006    for &l in committed {
1007        s.add_clause(vec![l]);
1008    }
1009    let r = s.solve();
1010    *conflicts += s.conflicts();
1011    Some(match r {
1012        SolveResult::Sat(model) => Answer::Sat(model[..num_vars].to_vec()),
1013        SolveResult::Unsat => Answer::Unsat,
1014    })
1015}
1016
1017/// Decide via **symmetric failed-literal inference** — symmetry used to *derive* consequences rather than
1018/// to *break* the search. A literal `ℓ` is a *failed literal* when `F ∧ ℓ` is UNSAT, which means `F ⊨ ¬ℓ`.
1019/// If `ℓ` is failed then *every* literal in its automorphism orbit is failed (an automorphism maps the
1020/// refutation of `F ∧ ℓ` onto a refutation of `F ∧ σ(ℓ)`), so a single probe forces the whole orbit. We
1021/// probe one representative per literal-orbit (budgeted, so a hard probe is simply skipped), accumulate the
1022/// implied units over the orbits, and solve the strengthened formula. Sound in both directions: only
1023/// *implied* units are added, so `F ∧ forced` is equisatisfiable with `F` (a SAT model is re-checked, and
1024/// UNSAT of the strengthened formula is UNSAT of `F`). `None` when there is no non-trivial symmetry or no
1025/// orbit yields a failed literal — the other routes then decide.
1026fn symmetric_probe_solve(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Solved> {
1027    if num_vars == 0 || num_vars > 64 {
1028        return None;
1029    }
1030    // Literal symmetries (variable AND phase) as image-literal vectors, lifted to the 2·num_vars points.
1031    let gens = crate::sym_break::literal_automorphism_generators(num_vars, clauses);
1032    if gens.is_empty() {
1033        return None;
1034    }
1035    let point_gens: Vec<_> = gens
1036        .iter()
1037        .map(|s| crate::sym_break::litsym_to_points(s, num_vars))
1038        .collect();
1039    let lit_orbits = crate::permgroup::orbits(2 * num_vars, &point_gens);
1040    let point_to_lit = |p: usize| Lit::new((p / 2) as u32, p % 2 == 0);
1041
1042    // A budgeted probe: `F ∧ ℓ` proven UNSAT within budget ⟹ `ℓ` is a failed literal (`F ⊨ ¬ℓ`).
1043    const PROBE_BUDGET: u64 = 200;
1044    let probe_fails = |lit: Lit| -> bool {
1045        let mut s = Solver::new(num_vars);
1046        for c in clauses {
1047            s.add_clause(c.clone());
1048        }
1049        s.add_clause(vec![lit]);
1050        matches!(s.solve_budgeted(PROBE_BUDGET), BudgetedResult::Unsat)
1051    };
1052
1053    // One probe per multi-element literal-orbit (a singleton offers no symmetry amplification); a failed
1054    // representative forces ¬m for every m in its orbit.
1055    let mut forced: Vec<Lit> = Vec::new();
1056    for orbit in &lit_orbits {
1057        if orbit.len() < 2 {
1058            continue;
1059        }
1060        if probe_fails(point_to_lit(orbit[0])) {
1061            forced.extend(orbit.iter().map(|&p| point_to_lit(p).negated()));
1062        }
1063    }
1064    if forced.is_empty() {
1065        return None; // nothing inferred — defer to the breaking routes
1066    }
1067
1068    let mut solver = Solver::new(num_vars);
1069    for c in clauses {
1070        solver.add_clause(c.clone());
1071    }
1072    for &l in &forced {
1073        solver.add_clause(vec![l]);
1074    }
1075    let r = solver.solve();
1076    let conflicts = solver.conflicts();
1077    match r {
1078        SolveResult::Sat(model) => {
1079            let projected: Vec<bool> = model[..num_vars].to_vec();
1080            clauses
1081                .iter()
1082                .all(|c| {
1083                    c.iter()
1084                        .any(|l| projected[l.var() as usize] == l.is_positive())
1085                })
1086                .then_some(Solved {
1087                    answer: Answer::Sat(projected),
1088                    via: Route::SymmetricProbe,
1089                    proof: Vec::new(),
1090                    conflicts,
1091                })
1092        }
1093        SolveResult::Unsat => Some(Solved {
1094            answer: Answer::Unsat,
1095            via: Route::SymmetricProbe,
1096            proof: Vec::new(),
1097            conflicts,
1098        }),
1099    }
1100}
1101
1102/// Root-level Boolean constraint propagation from a single assumed literal. Returns the literals forced by
1103/// unit propagation (including the assumption), or `None` if it propagates to a conflict (`ℓ` is a failed
1104/// literal). Every forced `m ≠ ℓ` is a sound consequence: `F ∧ ℓ ⊨ m`, i.e. `F ⊨ ℓ → m`.
1105fn bcp_forced(num_vars: usize, clauses: &[Vec<Lit>], assume: Lit) -> Option<Vec<Lit>> {
1106    let mut val: Vec<Option<bool>> = vec![None; num_vars];
1107    val[assume.var() as usize] = Some(assume.is_positive());
1108    let mut forced = vec![assume];
1109    loop {
1110        let mut changed = false;
1111        for c in clauses {
1112            let mut sat = false;
1113            let mut unassigned: Option<Lit> = None;
1114            let mut count = 0;
1115            for &l in c {
1116                match val[l.var() as usize] {
1117                    Some(b) if b == l.is_positive() => {
1118                        sat = true;
1119                        break;
1120                    }
1121                    Some(_) => {}
1122                    None => {
1123                        count += 1;
1124                        unassigned = Some(l);
1125                    }
1126                }
1127            }
1128            if sat {
1129                continue;
1130            }
1131            if count == 0 {
1132                return None; // conflict
1133            }
1134            if count == 1 {
1135                let u = unassigned.unwrap();
1136                val[u.var() as usize] = Some(u.is_positive());
1137                forced.push(u);
1138                changed = true;
1139            }
1140        }
1141        if !changed {
1142            break;
1143        }
1144    }
1145    Some(forced)
1146}
1147
1148/// Decide via **symmetric hyper-binary inference**. For one representative per variable-orbit, propagate
1149/// each polarity ([`bcp_forced`]); a non-conflicting probe of `ℓ` that forces `m` yields the implied
1150/// binary `¬ℓ ∨ m` (`F ⊨ ℓ → m`). Each such implication is then expanded over its **variable-symmetry
1151/// orbit** — `{¬σ(ℓ) ∨ σ(m)}` — so a single probe contributes the whole orbit of implied binaries, which
1152/// strengthen the formula before CDCL decides it. Sound: every added clause is a logical consequence of
1153/// `F` (a BCP implication, or an automorphic image of one), so `F` with them is equisatisfiable with `F`
1154/// (a SAT model is re-checked). `None` when there is no phase-free variable symmetry or no probe yields a
1155/// binary not already present (nothing new to learn — the other routes decide).
1156fn symmetric_binary_inference_solve(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Solved> {
1157    if num_vars == 0 || num_vars > 64 {
1158        return None;
1159    }
1160    let gens = crate::sym_break::variable_automorphism_generators(num_vars, clauses)?;
1161    if gens.is_empty() {
1162        return None;
1163    }
1164    let key2 = |a: Lit, b: Lit| -> [(u32, bool); 2] {
1165        let mut k = [(a.var(), a.is_positive()), (b.var(), b.is_positive())];
1166        k.sort_unstable();
1167        k
1168    };
1169    let lit_apply = |g: &[usize], l: Lit| Lit::new(g[l.var() as usize] as u32, l.is_positive());
1170
1171    // Already-present binaries — only genuinely new implications are worth adding.
1172    let mut seen: HashSet<[(u32, bool); 2]> = clauses
1173        .iter()
1174        .filter(|c| c.len() == 2)
1175        .map(|c| key2(c[0], c[1]))
1176        .collect();
1177
1178    const CAP: usize = 4096;
1179    let mut new_bins: Vec<Vec<Lit>> = Vec::new();
1180    'outer: for orbit in crate::permgroup::orbits(num_vars, &gens) {
1181        let v = orbit[0];
1182        for pol in [false, true] {
1183            let lit = Lit::new(v as u32, pol);
1184            let Some(forced) = bcp_forced(num_vars, clauses, lit) else {
1185                continue; // a failed literal — symmetric_probe_solve handles units
1186            };
1187            for &m in &forced {
1188                if m.var() == lit.var() {
1189                    continue;
1190                }
1191                // ℓ → m, i.e. the binary ¬ℓ ∨ m; expand its variable-symmetry orbit.
1192                let mut local: HashSet<[(u32, bool); 2]> = HashSet::new();
1193                let mut stack = vec![(lit.negated(), m)];
1194                while let Some((a, b)) = stack.pop() {
1195                    if a.var() == b.var() {
1196                        continue;
1197                    }
1198                    let k = key2(a, b);
1199                    if !local.insert(k) {
1200                        continue;
1201                    }
1202                    if seen.insert(k) {
1203                        new_bins.push(vec![a, b]);
1204                        if new_bins.len() >= CAP {
1205                            break 'outer;
1206                        }
1207                    }
1208                    for g in &gens {
1209                        stack.push((lit_apply(g, a), lit_apply(g, b)));
1210                    }
1211                }
1212            }
1213        }
1214    }
1215    if new_bins.is_empty() {
1216        return None; // nothing new to learn
1217    }
1218
1219    let mut solver = Solver::new(num_vars);
1220    for c in clauses {
1221        solver.add_clause(c.clone());
1222    }
1223    for c in &new_bins {
1224        solver.add_clause(c.clone());
1225    }
1226    let r = solver.solve();
1227    let conflicts = solver.conflicts();
1228    match r {
1229        SolveResult::Sat(model) => {
1230            let projected: Vec<bool> = model[..num_vars].to_vec();
1231            clauses
1232                .iter()
1233                .all(|c| {
1234                    c.iter()
1235                        .any(|l| projected[l.var() as usize] == l.is_positive())
1236                })
1237                .then_some(Solved {
1238                    answer: Answer::Sat(projected),
1239                    via: Route::SymmetricBinary,
1240                    proof: Vec::new(),
1241                    conflicts,
1242                })
1243        }
1244        SolveResult::Unsat => Some(Solved {
1245            answer: Answer::Unsat,
1246            via: Route::SymmetricBinary,
1247            proof: Vec::new(),
1248            conflicts,
1249        }),
1250    }
1251}
1252
1253/// Decide by collapsing the formula onto its **orbit-weight quotient**. When the variable-automorphism
1254/// group is the *full* product of symmetric groups on its orbits — `G = S_{O₁} × … × S_{O_k}` — every
1255/// assignment is `G`-equivalent to one determined solely by its *weight* per orbit (how many variables in
1256/// each orbit are true): the sorting permutation lies in `G`, and an automorphism maps models to models.
1257/// So `F` is satisfiable iff some weight-tuple representative satisfies it, and the `2ⁿ` search space
1258/// collapses to `Π(|Oᵢ|+1)` representatives decided by direct evaluation. This is **complete and exact**
1259/// (not merely sound): a real decision, with an exponential collapse on fully-interchangeable instances.
1260///
1261/// The full-product gate is checked without factorials: for each orbit, every adjacent transposition
1262/// (swapping two members, fixing all else) must lie in the group ([`Bsgs::contains`]) — those generate
1263/// each `S_{Oᵢ}`, and the group is always a *subgroup* of the product, so membership of all of them gives
1264/// equality. `None` when the group is not the full product, there is no phase-free symmetry, or the
1265/// representative count is not a genuine (bounded) collapse over `2ⁿ`.
1266fn orbit_weight_quotient_solve(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Solved> {
1267    if num_vars == 0 || num_vars > 64 {
1268        return None;
1269    }
1270    let gens = crate::sym_break::variable_automorphism_generators(num_vars, clauses)?;
1271    if gens.is_empty() {
1272        return None;
1273    }
1274    let orbits = crate::permgroup::orbits(num_vars, &gens);
1275    let bsgs = crate::permgroup::schreier_sims(num_vars, &gens);
1276
1277    // Full-product gate: every adjacent transposition within every orbit must be in the group.
1278    for orbit in &orbits {
1279        for w in orbit.windows(2) {
1280            let mut t: Vec<usize> = (0..num_vars).collect();
1281            t.swap(w[0], w[1]);
1282            if !bsgs.contains(&t) {
1283                return None; // an orbit on which G is not the full symmetric group
1284            }
1285        }
1286    }
1287
1288    // Representative count Π(|Oᵢ|+1) — bounded, and a genuine collapse over 2ⁿ.
1289    let mut num_reps: u128 = 1;
1290    for o in &orbits {
1291        num_reps = num_reps.saturating_mul(o.len() as u128 + 1);
1292    }
1293    if num_reps > 200_000 || num_reps >= (1u128 << num_vars) {
1294        return None;
1295    }
1296
1297    // Enumerate every weight-tuple (w₀,…,w_{k-1}), build its representative (the first wᵢ members of orbit
1298    // i set true), and evaluate. The first satisfying representative is a genuine model of F.
1299    let dims: Vec<usize> = orbits.iter().map(|o| o.len() + 1).collect();
1300    let total = num_reps as usize;
1301    let satisfies = |a: &[bool]| -> bool {
1302        clauses
1303            .iter()
1304            .all(|c| c.iter().any(|l| a[l.var() as usize] == l.is_positive()))
1305    };
1306    for idx in 0..total {
1307        let mut rem = idx;
1308        let mut assign = vec![false; num_vars];
1309        for (oi, orbit) in orbits.iter().enumerate() {
1310            let w = rem % dims[oi];
1311            rem /= dims[oi];
1312            for &v in orbit.iter().take(w) {
1313                assign[v] = true;
1314            }
1315        }
1316        if satisfies(&assign) {
1317            return Some(Solved {
1318                answer: Answer::Sat(assign),
1319                via: Route::OrbitWeightQuotient,
1320                proof: Vec::new(),
1321                conflicts: 0,
1322            });
1323        }
1324    }
1325    // No weight-tuple representative satisfies F, and every assignment reduces to one ⟹ UNSAT.
1326    Some(Solved::unsat(Route::OrbitWeightQuotient))
1327}
1328
1329/// A **lex-leader propagator** (Symmetry Breaking During Search) presented as a DPLL(T) theory. For each
1330/// generator `g` it enforces the symmetry-breaking constraint `a ≤_lex a∘g` (with `(a∘g)[j] = a[g[j]]`)
1331/// *dynamically* against the trail — no static SBP clauses, no auxiliary variables. Walking the variable
1332/// order, while the prefix is equal it records the equality-break literals; at the first position `j`
1333/// where `a[j]` and `a[g[j]]` are not (yet) equal it forms the lex clause
1334/// `(prefix equalities break) ∨ ¬a[j] ∨ a[g[j]]` — "if the prefix is equal then `a[j] ≤ a[g[j]]`" — and
1335/// emits it only when it is currently unit or falsified, so the core propagates or conflicts. Every
1336/// emitted clause is a sound consequence of `a ≤_lex a∘g`, which is satisfiability-preserving (the lex-min
1337/// of each orbit survives), so `F` with the theory is equisatisfiable with `F`.
1338struct LexLeaderTheory {
1339    num_vars: usize,
1340    generators: Vec<crate::permgroup::Perm>,
1341}
1342
1343impl crate::cdcl::Theory for LexLeaderTheory {
1344    fn propagate(&mut self, trail: &[Lit]) -> Vec<Vec<Lit>> {
1345        let mut val: Vec<Option<bool>> = vec![None; self.num_vars];
1346        for &l in trail {
1347            let v = l.var() as usize;
1348            if v < self.num_vars {
1349                val[v] = Some(l.is_positive());
1350            }
1351        }
1352        // Keep a clause only if it is currently unit (one unassigned, rest false) or falsified (all false);
1353        // a satisfied or under-determined clause carries no immediate force and is dropped.
1354        let actionable = |c: &[Lit]| -> bool {
1355            let mut unassigned = 0;
1356            for &lit in c {
1357                match val[lit.var() as usize] {
1358                    Some(b) if b == lit.is_positive() => return false, // already satisfied
1359                    Some(_) => {}
1360                    None => unassigned += 1,
1361                }
1362            }
1363            unassigned <= 1
1364        };
1365
1366        let mut out: Vec<Vec<Lit>> = Vec::new();
1367        for g in &self.generators {
1368            let mut prefix: Vec<Lit> = Vec::new();
1369            for j in 0..self.num_vars {
1370                let k = g[j];
1371                if k == j {
1372                    continue; // a[j] = a[g[j]] identically; the prefix is unaffected
1373                }
1374                match (val[j], val[k]) {
1375                    (Some(a), Some(b)) if a == b => {
1376                        // prefix still equal: the clause is satisfied if either side flips off this value
1377                        prefix.push(Lit::new(j as u32, !a));
1378                        prefix.push(Lit::new(k as u32, !b));
1379                    }
1380                    _ => {
1381                        // first position where the prefix is not (yet) equal: enforce a[j] ≤ a[g[j]].
1382                        let mut c = prefix.clone();
1383                        c.push(Lit::new(j as u32, false)); // ¬a[j]
1384                        c.push(Lit::new(k as u32, true)); //  a[g[j]]
1385                        if actionable(&c) {
1386                            out.push(c);
1387                        }
1388                        break;
1389                    }
1390                }
1391            }
1392        }
1393        out
1394    }
1395}
1396
1397/// Decide via **symmetry breaking during search**: drive CDCL with the [`LexLeaderTheory`] propagator so
1398/// non-canonical (non-lex-leader) assignments are pruned on the fly through the DPLL(T) interface, rather
1399/// than by the static lex-leader clauses of [`symmetry_break_solve`]. Sound: the propagator only adds
1400/// consequences of `a ≤_lex a∘g`, which is satisfiability-preserving, so the verdict is correct (a SAT
1401/// model is re-checked fail-closed). `None` when there is no phase-free variable symmetry.
1402fn symmetry_propagate_solve(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Solved> {
1403    if num_vars == 0 || num_vars > 64 {
1404        return None;
1405    }
1406    let gens = crate::sym_break::variable_automorphism_generators(num_vars, clauses)?;
1407    if gens.is_empty() {
1408        return None;
1409    }
1410    let mut solver = Solver::new(num_vars);
1411    for c in clauses {
1412        solver.add_clause(c.clone());
1413    }
1414    let mut theories: Vec<Box<dyn crate::cdcl::Theory>> = vec![Box::new(LexLeaderTheory {
1415        num_vars,
1416        generators: gens,
1417    })];
1418    match solver.solve_with(&mut theories) {
1419        SolveResult::Sat(model) => {
1420            let projected: Vec<bool> = model[..num_vars].to_vec();
1421            clauses
1422                .iter()
1423                .all(|c| {
1424                    c.iter()
1425                        .any(|l| projected[l.var() as usize] == l.is_positive())
1426                })
1427                .then_some(Solved {
1428                    answer: Answer::Sat(projected),
1429                    via: Route::SymmetryPropagate,
1430                    proof: Vec::new(),
1431                    conflicts: solver.conflicts(),
1432                })
1433        }
1434        SolveResult::Unsat => Some(Solved {
1435            answer: Answer::Unsat,
1436            via: Route::SymmetryPropagate,
1437            proof: Vec::new(),
1438            conflicts: solver.conflicts(),
1439        }),
1440    }
1441}
1442
1443/// Union-find root with path halving.
1444fn uf_find(parent: &mut [usize], mut x: usize) -> usize {
1445    while parent[x] != x {
1446        parent[x] = parent[parent[x]];
1447        x = parent[x];
1448    }
1449    x
1450}
1451
1452/// Decide by **plain component decomposition** — the payoff of separability in the solver. When the formula
1453/// splits into independent components (variables linked when they share a clause) with NO symmetry relating
1454/// them — exactly the case [`symmetric_component_solve`] declines — solve each component apart through the
1455/// full arsenal and combine: `F` is UNSAT iff any component is, and a model is the disjoint union of the
1456/// components' models (re-checked fail-closed). Solving apart avoids wrestling the whole formula at once and
1457/// lets a specialized route fire on a component that stumped it on the whole. Sound in both directions:
1458/// a component UNSAT ⟹ `F` UNSAT; and disjoint variable sets make the assembled model conflict-free.
1459/// `None` for a single component (nothing to split).
1460fn component_solve(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Solved> {
1461    if num_vars == 0 || num_vars > 64 || clauses.is_empty() {
1462        return None;
1463    }
1464    let mut parent: Vec<usize> = (0..num_vars).collect();
1465    for c in clauses {
1466        if c.is_empty() {
1467            return Some(Solved::unsat(Route::Component)); // an empty clause is UNSAT
1468        }
1469        let r0 = uf_find(&mut parent, c[0].var() as usize);
1470        for l in &c[1..] {
1471            let r = uf_find(&mut parent, l.var() as usize);
1472            parent[r] = r0;
1473        }
1474    }
1475    let mut comp_clauses: Vec<Vec<Vec<Lit>>> = vec![Vec::new(); num_vars];
1476    for c in clauses {
1477        let r = uf_find(&mut parent, c[0].var() as usize);
1478        comp_clauses[r].push(c.clone());
1479    }
1480    let roots: Vec<usize> = (0..num_vars)
1481        .filter(|&r| !comp_clauses[r].is_empty())
1482        .collect();
1483    if roots.len() <= 1 {
1484        return None; // a single component — nothing to decompose
1485    }
1486    let mut model = vec![false; num_vars];
1487    let mut conflicts = 0u64;
1488    for &r in &roots {
1489        let sub = solve_comprehensive(num_vars, &comp_clauses[r]);
1490        conflicts += sub.conflicts;
1491        match sub.answer {
1492            Answer::Unsat => {
1493                return Some(Solved {
1494                    answer: Answer::Unsat,
1495                    via: Route::Component,
1496                    proof: Vec::new(),
1497                    conflicts,
1498                });
1499            }
1500            Answer::Sat(m) => {
1501                let vars: std::collections::BTreeSet<usize> = comp_clauses[r]
1502                    .iter()
1503                    .flatten()
1504                    .map(|l| l.var() as usize)
1505                    .collect();
1506                for v in vars {
1507                    model[v] = m[v];
1508                }
1509            }
1510        }
1511    }
1512    // Fail-closed: the assembled model must satisfy every clause, or defer.
1513    clauses
1514        .iter()
1515        .all(|c| c.iter().any(|l| model[l.var() as usize] == l.is_positive()))
1516        .then_some(Solved {
1517            answer: Answer::Sat(model),
1518            via: Route::Component,
1519            proof: Vec::new(),
1520            conflicts,
1521        })
1522}
1523
1524/// Decide via **plain component decomposition** as a public dispatcher route: split into independent
1525/// components and solve each apart through the full arsenal, combining the verdicts. A single component (or
1526/// a model that fails the fail-closed recheck) defers to the plain CDCL fallback.
1527pub fn solve_by_components(num_vars: usize, clauses: &[Vec<Lit>]) -> Solved {
1528    component_solve(num_vars, clauses).unwrap_or_else(|| cdcl_fallback(num_vars, clauses))
1529}
1530
1531/// Decide by **symmetric component decomposition** — divide-and-conquer with symmetry. The formula splits
1532/// into independent components (variables linked when they share a clause); `F` is SAT iff every component
1533/// is. The automorphism group permutes the components, and components in the same orbit are *isomorphic
1534/// copies*, so we solve **one representative per component-orbit** (recursively, through the full arsenal)
1535/// and replicate its model through the symmetry — `k` identical sub-problems solved once. Sound: a
1536/// component is UNSAT ⟹ `F` is UNSAT; and for a copy `C = ρ(rep)` with `ρ` an automorphism, `ρ(rep-model)`
1537/// satisfies `C`'s clauses, so the assembled assignment (re-checked fail-closed) is a genuine model of
1538/// `F`. `None` for a single component, no phase-free symmetry, or no orbit with ≥ 2 components (no
1539/// symmetric copies to exploit — plain CDCL handles the rest).
1540fn symmetric_component_solve(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Solved> {
1541    if num_vars == 0 || num_vars > 64 || clauses.is_empty() {
1542        return None;
1543    }
1544    // Connected components of the variable-interaction graph.
1545    let mut parent: Vec<usize> = (0..num_vars).collect();
1546    for c in clauses {
1547        if c.is_empty() {
1548            return Some(Solved::unsat(Route::SymmetricComponent)); // an empty clause is UNSAT
1549        }
1550        let r0 = uf_find(&mut parent, c[0].var() as usize);
1551        for l in &c[1..] {
1552            let r = uf_find(&mut parent, l.var() as usize);
1553            parent[r] = r0;
1554        }
1555    }
1556    let mut appears = vec![false; num_vars];
1557    for c in clauses {
1558        for l in c {
1559            appears[l.var() as usize] = true;
1560        }
1561    }
1562    let mut comp_vars: Vec<Vec<usize>> = vec![Vec::new(); num_vars];
1563    for v in 0..num_vars {
1564        if appears[v] {
1565            let r = uf_find(&mut parent, v);
1566            comp_vars[r].push(v);
1567        }
1568    }
1569    let roots: Vec<usize> = (0..num_vars)
1570        .filter(|&r| !comp_vars[r].is_empty())
1571        .collect();
1572    if roots.len() <= 1 {
1573        return None; // a single component — nothing to decompose
1574    }
1575    let mut comp_clauses: Vec<Vec<Vec<Lit>>> = vec![Vec::new(); num_vars];
1576    for c in clauses {
1577        let r = uf_find(&mut parent, c[0].var() as usize);
1578        comp_clauses[r].push(c.clone());
1579    }
1580    // Phase-free variable automorphisms identify isomorphic components.
1581    let gens = crate::sym_break::variable_automorphism_generators(num_vars, clauses)?;
1582    if gens.is_empty() {
1583        return None;
1584    }
1585    // Component orbits, each component tagged with the permutation mapping the orbit representative onto it.
1586    let identity: Vec<usize> = (0..num_vars).collect();
1587    let mut orbit_of: Vec<Option<usize>> = vec![None; num_vars];
1588    let mut orbits: Vec<Vec<(usize, Vec<usize>)>> = Vec::new();
1589    for &r in &roots {
1590        if orbit_of[r].is_some() {
1591            continue;
1592        }
1593        let oi = orbits.len();
1594        orbit_of[r] = Some(oi);
1595        let mut orbit: Vec<(usize, Vec<usize>)> = vec![(r, identity.clone())];
1596        let mut i = 0;
1597        while i < orbit.len() {
1598            let (cr, perm) = orbit[i].clone();
1599            i += 1;
1600            for g in &gens {
1601                let img_root = uf_find(&mut parent, g[comp_vars[cr][0]]);
1602                if orbit_of[img_root].is_none() {
1603                    orbit_of[img_root] = Some(oi);
1604                    let new_perm: Vec<usize> = (0..num_vars).map(|v| g[perm[v]]).collect();
1605                    orbit.push((img_root, new_perm));
1606                }
1607            }
1608        }
1609        orbits.push(orbit);
1610    }
1611    // A genuine symmetric copy is required — otherwise there is no symmetry redundancy to exploit here.
1612    if !orbits.iter().any(|o| o.len() >= 2) {
1613        return None;
1614    }
1615    // Solve one representative per orbit (recursively, through the full arsenal); assemble or refute.
1616    let mut model = vec![false; num_vars];
1617    let mut conflicts = 0u64;
1618    for orbit in &orbits {
1619        let rep_root = orbit[0].0;
1620        let solved = solve_comprehensive(num_vars, &comp_clauses[rep_root]);
1621        conflicts += solved.conflicts;
1622        match solved.answer {
1623            Answer::Unsat => {
1624                return Some(Solved {
1625                    answer: Answer::Unsat,
1626                    via: Route::SymmetricComponent,
1627                    proof: Vec::new(),
1628                    conflicts,
1629                });
1630            }
1631            Answer::Sat(rep_model) => {
1632                for (_, perm) in orbit {
1633                    for &v in &comp_vars[rep_root] {
1634                        model[perm[v]] = rep_model[v];
1635                    }
1636                }
1637            }
1638        }
1639    }
1640    clauses
1641        .iter()
1642        .all(|c| c.iter().any(|l| model[l.var() as usize] == l.is_positive()))
1643        .then_some(Solved {
1644            answer: Answer::Sat(model),
1645            via: Route::SymmetricComponent,
1646            proof: Vec::new(),
1647            conflicts,
1648        })
1649}
1650
1651/// Propagate the formula's unit clauses to a fixpoint. Returns the forced literals and the simplified
1652/// residual (satisfied clauses dropped, falsified literals removed — so forced variables appear in no
1653/// residual clause and the residual has no units), or `None` if propagation reaches a conflict.
1654fn root_propagate(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<(Vec<Lit>, Vec<Vec<Lit>>)> {
1655    let mut val: Vec<Option<bool>> = vec![None; num_vars];
1656    loop {
1657        let mut changed = false;
1658        for c in clauses {
1659            let mut sat = false;
1660            let mut unit: Option<Lit> = None;
1661            let mut count = 0;
1662            for &l in c {
1663                match val[l.var() as usize] {
1664                    Some(b) if b == l.is_positive() => {
1665                        sat = true;
1666                        break;
1667                    }
1668                    Some(_) => {}
1669                    None => {
1670                        count += 1;
1671                        unit = Some(l);
1672                    }
1673                }
1674            }
1675            if sat {
1676                continue;
1677            }
1678            if count == 0 {
1679                return None; // conflict
1680            }
1681            if count == 1 {
1682                let u = unit.unwrap();
1683                val[u.var() as usize] = Some(u.is_positive());
1684                changed = true;
1685            }
1686        }
1687        if !changed {
1688            break;
1689        }
1690    }
1691    let forced: Vec<Lit> = (0..num_vars)
1692        .filter_map(|v| val[v].map(|b| Lit::new(v as u32, b)))
1693        .collect();
1694    let mut residual: Vec<Vec<Lit>> = Vec::new();
1695    for c in clauses {
1696        let mut sat = false;
1697        let mut shrunk: Vec<Lit> = Vec::new();
1698        for &l in c {
1699            match val[l.var() as usize] {
1700                Some(b) if b == l.is_positive() => {
1701                    sat = true;
1702                    break;
1703                }
1704                Some(_) => {} // a falsified literal — drop it
1705                None => shrunk.push(l),
1706            }
1707        }
1708        if !sat {
1709            if shrunk.is_empty() {
1710                return None; // an emptied clause (cannot occur past the fixpoint, but stay safe)
1711            }
1712            residual.push(shrunk);
1713        }
1714    }
1715    Some((forced, residual))
1716}
1717
1718/// Decide via **symmetry unlocked by simplification**. Unit clauses can mask automorphisms — a symmetry of
1719/// the residual `F|ρ` need not be a symmetry of the raw `F`, so the raw-formula detectors structurally miss
1720/// it. This route propagates the units ([`root_propagate`]), detects symmetry on the simplified residual,
1721/// and fires only when that symmetry is genuinely *new* (some residual generator is not a symmetry of the
1722/// raw clauses). It then solves the residual with the full arsenal — which now sees the revealed symmetry —
1723/// and re-applies the forced assignment. Sound: `ρ` is implied (BCP), `F` is equisatisfiable with `F|ρ`,
1724/// and the assembled model is re-checked fail-closed. `None` when nothing propagates, the residual is
1725/// asymmetric, or its symmetry was already visible on the raw formula.
1726fn symmetry_via_simplification_solve(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Solved> {
1727    if num_vars == 0 || num_vars > 64 {
1728        return None;
1729    }
1730    let (rho, residual) = match root_propagate(num_vars, clauses) {
1731        None => return Some(Solved::unsat(Route::SymmetrySimplify)), // refuted by propagation
1732        Some(x) => x,
1733    };
1734    if rho.is_empty() {
1735        return None; // nothing to simplify — no symmetry could be unlocked
1736    }
1737    // Detect on the residual with the forced literals re-pinned as units: this keeps the forced variables
1738    // constrained (an isolated variable carries a spurious phase symmetry that would mask the real ones)
1739    // while still exposing the symmetry that simplification revealed.
1740    let mut detect = residual.clone();
1741    for &l in &rho {
1742        detect.push(vec![l]);
1743    }
1744    let res_gens =
1745        crate::sym_break::variable_automorphism_generators(num_vars, &detect).unwrap_or_default();
1746    if res_gens.is_empty() {
1747        return None; // the residual carries no usable symmetry
1748    }
1749    // Fire only if simplification revealed symmetry the raw formula did not already have.
1750    let raw_set: HashSet<Vec<(u32, bool)>> = clauses
1751        .iter()
1752        .map(|c| {
1753            let mut k: Vec<(u32, bool)> = c.iter().map(|l| (l.var(), l.is_positive())).collect();
1754            k.sort_unstable();
1755            k
1756        })
1757        .collect();
1758    let is_raw_symmetry = |g: &[usize]| -> bool {
1759        clauses.iter().all(|c| {
1760            let mut img: Vec<(u32, bool)> = c
1761                .iter()
1762                .map(|l| (g[l.var() as usize] as u32, l.is_positive()))
1763                .collect();
1764            img.sort_unstable();
1765            raw_set.contains(&img)
1766        })
1767    };
1768    if res_gens.iter().all(|g| is_raw_symmetry(g)) {
1769        return None; // the raw-formula routes already see this symmetry
1770    }
1771
1772    // Solve the simplified residual with the full arsenal, then re-apply the forced assignment.
1773    let solved = solve_comprehensive(num_vars, &residual);
1774    match solved.answer {
1775        Answer::Unsat => Some(Solved {
1776            answer: Answer::Unsat,
1777            via: Route::SymmetrySimplify,
1778            proof: Vec::new(),
1779            conflicts: solved.conflicts,
1780        }),
1781        Answer::Sat(mut model) => {
1782            for &l in &rho {
1783                model[l.var() as usize] = l.is_positive();
1784            }
1785            clauses
1786                .iter()
1787                .all(|c| c.iter().any(|l| model[l.var() as usize] == l.is_positive()))
1788                .then_some(Solved {
1789                    answer: Answer::Sat(model),
1790                    via: Route::SymmetrySimplify,
1791                    proof: Vec::new(),
1792                    conflicts: solved.conflicts,
1793                })
1794        }
1795    }
1796}
1797
1798/// Build a **lex-leader SBP from the whole tower of block systems** — multi-dimensional symmetry breaking.
1799/// `hierarchical_break` breaks a single (minimal) block system: the inter-block and intra-block swaps of a
1800/// 2-D row/column grid. A `d`-dimensional grid (`S_{n₁} × … × S_{n_d}`) has nested block systems
1801/// `cells ⊂ lines ⊂ planes ⊂ …`; this ascends the tower via the group's *induced action on blocks*,
1802/// emitting the structured swaps at every level. Each candidate swap is verified to lie in the group
1803/// ([`Bsgs::contains`]), so the SBP only ever uses genuine automorphisms and is sound (it keeps the
1804/// lex-leader of each orbit). `None` when there is no phase-free, transitive, imprimitive symmetry.
1805fn nested_block_tower_break(
1806    num_vars: usize,
1807    clauses: &[Vec<Lit>],
1808) -> Option<(Vec<Vec<Lit>>, usize)> {
1809    let gens = crate::sym_break::variable_automorphism_generators(num_vars, clauses)?;
1810    if gens.is_empty() {
1811        return None;
1812    }
1813    let bsgs = crate::permgroup::schreier_sims(num_vars, &gens);
1814    let to_litsym =
1815        |p: &[usize]| -> Vec<Lit> { (0..num_vars).map(|v| Lit::pos(p[v] as u32)).collect() };
1816
1817    let mut structured: Vec<Vec<Lit>> = Vec::new();
1818    let mut blocks = crate::permgroup::minimal_block_system(num_vars, &gens)?; // None if primitive/intransitive
1819    for _level in 0..num_vars {
1820        let k = blocks.len();
1821        let m = blocks[0].len();
1822        if blocks.iter().any(|b| b.len() != m) {
1823            break; // irregular tower — stop ascending
1824        }
1825        // Inter-block adjacent swaps: exchange two whole adjacent blocks position-wise.
1826        for i in 0..k.saturating_sub(1) {
1827            let mut p: Vec<usize> = (0..num_vars).collect();
1828            for j in 0..m {
1829                p[blocks[i][j]] = blocks[i + 1][j];
1830                p[blocks[i + 1][j]] = blocks[i][j];
1831            }
1832            if bsgs.contains(&p) {
1833                structured.push(to_litsym(&p));
1834            }
1835        }
1836        // Intra-block uniform adjacent swaps: exchange positions j, j+1 within every block at once.
1837        for j in 0..m.saturating_sub(1) {
1838            let mut p: Vec<usize> = (0..num_vars).collect();
1839            for b in &blocks {
1840                p[b[j]] = b[j + 1];
1841                p[b[j + 1]] = b[j];
1842            }
1843            if bsgs.contains(&p) {
1844                structured.push(to_litsym(&p));
1845            }
1846        }
1847        if k <= 1 {
1848            break;
1849        }
1850        // Ascend: the group's induced action on the k blocks, then that action's block system.
1851        let mut block_of = vec![usize::MAX; num_vars];
1852        for (bi, b) in blocks.iter().enumerate() {
1853            for &v in b {
1854                block_of[v] = bi;
1855            }
1856        }
1857        let induced: Vec<Vec<usize>> = gens
1858            .iter()
1859            .map(|g| (0..k).map(|bi| block_of[g[blocks[bi][0]]]).collect())
1860            .collect();
1861        let Some(super_blocks) = crate::permgroup::minimal_block_system(k, &induced) else {
1862            break; // the blocks are primitive — top of the tower
1863        };
1864        let mut next: Vec<Vec<usize>> = Vec::new();
1865        for sb in &super_blocks {
1866            let mut nb = Vec::new();
1867            for &bi in sb {
1868                nb.extend_from_slice(&blocks[bi]);
1869            }
1870            next.push(nb);
1871        }
1872        if next.len() >= blocks.len() {
1873            break; // no genuine coarsening
1874        }
1875        blocks = next;
1876    }
1877    if structured.is_empty() {
1878        return None;
1879    }
1880    Some(crate::sym_break::lex_leader_sbp_lit(num_vars, &structured))
1881}
1882
1883/// Decide via **multi-dimensional (nested block-tower) symmetry breaking** — see [`nested_block_tower_break`].
1884/// Adds the tower's lex-leader SBP and lets CDCL decide the broken formula; sound (verified group elements
1885/// only), with a fail-closed re-check on the returned model. `None` when there is no usable nested grid
1886/// symmetry.
1887fn nested_symmetry_solve(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Solved> {
1888    if num_vars == 0 || num_vars > 64 {
1889        return None;
1890    }
1891    let (sbp, total) = nested_block_tower_break(num_vars, clauses)?;
1892    let mut solver = Solver::new(total);
1893    for c in clauses {
1894        solver.add_clause(c.clone());
1895    }
1896    for c in &sbp {
1897        solver.add_clause(c.clone());
1898    }
1899    match solver.solve() {
1900        SolveResult::Sat(model) => {
1901            let projected: Vec<bool> = model[..num_vars].to_vec();
1902            clauses
1903                .iter()
1904                .all(|c| {
1905                    c.iter()
1906                        .any(|l| projected[l.var() as usize] == l.is_positive())
1907                })
1908                .then_some(Solved {
1909                    answer: Answer::Sat(projected),
1910                    via: Route::NestedSymmetry,
1911                    proof: Vec::new(),
1912                    conflicts: solver.conflicts(),
1913                })
1914        }
1915        SolveResult::Unsat => Some(Solved {
1916            answer: Answer::Unsat,
1917            via: Route::NestedSymmetry,
1918            proof: Vec::new(),
1919            conflicts: solver.conflicts(),
1920        }),
1921    }
1922}
1923
1924/// The sorted (var, polarity) signature of a clause, for set membership.
1925fn canon_clause(c: &[Lit]) -> Vec<(u32, bool)> {
1926    let mut k: Vec<(u32, bool)> = c.iter().map(|l| (l.var(), l.is_positive())).collect();
1927    k.sort_unstable();
1928    k
1929}
1930
1931/// A clause with variables `a` and `b` interchanged (polarities preserved).
1932fn swap_clause_vars(c: &[Lit], a: usize, b: usize) -> Vec<Lit> {
1933    c.iter()
1934        .map(|l| {
1935            let v = l.var() as usize;
1936            let nv = if v == a {
1937                b
1938            } else if v == b {
1939                a
1940            } else {
1941                v
1942            };
1943            Lit::new(nv as u32, l.is_positive())
1944        })
1945        .collect()
1946}
1947
1948/// Is the clause `c` a logical consequence of `clauses`? (`F ∧ ¬c` is UNSAT.)
1949fn clause_is_implied(num_vars: usize, clauses: &[Vec<Lit>], c: &[Lit]) -> bool {
1950    let mut s = Solver::new(num_vars);
1951    for cl in clauses {
1952        s.add_clause(cl.clone());
1953    }
1954    for &l in c {
1955        s.add_clause(vec![l.negated()]);
1956    }
1957    matches!(s.solve(), SolveResult::Unsat)
1958}
1959
1960/// The **semantic** symmetries (variable transpositions) of a CNF: pairs `(a,b)` whose swap preserves the
1961/// MODEL SET, `F ≡ swap(F)`, even when it does NOT preserve the clause set. Checked by implication: `F ⊨
1962/// swap(F)` (and, by the involution `swap² = id`, that is full equivalence). Returns the semantic pairs
1963/// and whether any is *non-syntactic* (clause set changed) — i.e. genuinely beyond what the syntactic
1964/// detector ([`crate::sym_break::variable_automorphism_generators`]) can see.
1965pub fn semantic_symmetry_pairs(
1966    num_vars: usize,
1967    clauses: &[Vec<Lit>],
1968) -> (Vec<(usize, usize)>, bool) {
1969    let clause_set: HashSet<Vec<(u32, bool)>> = clauses.iter().map(|c| canon_clause(c)).collect();
1970    let mut pairs = Vec::new();
1971    let mut any_non_syntactic = false;
1972    for a in 0..num_vars {
1973        for b in (a + 1)..num_vars {
1974            let syntactic = clauses
1975                .iter()
1976                .all(|c| clause_set.contains(&canon_clause(&swap_clause_vars(c, a, b))));
1977            let semantic = syntactic
1978                || clauses.iter().all(|c| {
1979                    let sc = swap_clause_vars(c, a, b);
1980                    clause_set.contains(&canon_clause(&sc))
1981                        || clause_is_implied(num_vars, clauses, &sc)
1982                });
1983            if semantic {
1984                pairs.push((a, b));
1985                if !syntactic {
1986                    any_non_syntactic = true;
1987                }
1988            }
1989        }
1990    }
1991    (pairs, any_non_syntactic)
1992}
1993
1994/// Decide via **semantic symmetry breaking**. Detects variable transpositions that preserve the model set
1995/// without preserving the clause set ([`semantic_symmetry_pairs`]) — symmetries the syntactic detector
1996/// structurally cannot find — and breaks them with the lex-leader, which is sound for any model-set-
1997/// preserving permutation. Fires only when there is a genuinely *non-syntactic* symmetry (otherwise
1998/// [`symmetry_break_solve`] already covers it). Detection is `O(n²)` implication checks, so it is gated to
1999/// small instances and runs last, just before search. SAT models are re-checked fail-closed.
2000fn semantic_symmetry_solve(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Solved> {
2001    if num_vars == 0 || num_vars > 20 || clauses.len() > 256 {
2002        return None; // O(n² · clauses) implication probing — bound it
2003    }
2004    let (pairs, any_non_syntactic) = semantic_symmetry_pairs(num_vars, clauses);
2005    if pairs.is_empty() || !any_non_syntactic {
2006        return None; // nothing, or nothing beyond the syntactic routes
2007    }
2008    let gens: Vec<Vec<Lit>> = pairs
2009        .iter()
2010        .map(|&(a, b)| {
2011            (0..num_vars)
2012                .map(|v| {
2013                    let img = if v == a {
2014                        b
2015                    } else if v == b {
2016                        a
2017                    } else {
2018                        v
2019                    };
2020                    Lit::pos(img as u32)
2021                })
2022                .collect()
2023        })
2024        .collect();
2025    let (sbp, total) = crate::sym_break::lex_leader_sbp_lit(num_vars, &gens);
2026    let mut solver = Solver::new(total);
2027    for c in clauses {
2028        solver.add_clause(c.clone());
2029    }
2030    for c in &sbp {
2031        solver.add_clause(c.clone());
2032    }
2033    match solver.solve() {
2034        SolveResult::Sat(model) => {
2035            let projected: Vec<bool> = model[..num_vars].to_vec();
2036            clauses
2037                .iter()
2038                .all(|c| {
2039                    c.iter()
2040                        .any(|l| projected[l.var() as usize] == l.is_positive())
2041                })
2042                .then_some(Solved {
2043                    answer: Answer::Sat(projected),
2044                    via: Route::SemanticSymmetry,
2045                    proof: Vec::new(),
2046                    conflicts: solver.conflicts(),
2047                })
2048        }
2049        SolveResult::Unsat => Some(Solved {
2050            answer: Answer::Unsat,
2051            via: Route::SemanticSymmetry,
2052            proof: Vec::new(),
2053            conflicts: solver.conflicts(),
2054        }),
2055    }
2056}
2057
2058/// The **almost-symmetries** (variable transpositions) of a CNF: pairs `(a,b)` whose swap preserves all but
2059/// at most `max_broken` clauses. Returns each pair with the **broken images** `σ(B) = { swap(c) : swap(c) ∉
2060/// F }` — the clauses that must hold for the swap to map a model to a model, i.e. the guard. An empty image
2061/// set is a true (syntactic) symmetry and is excluded.
2062pub fn almost_symmetry_pairs(
2063    num_vars: usize,
2064    clauses: &[Vec<Lit>],
2065    max_broken: usize,
2066) -> Vec<(usize, usize, Vec<Vec<Lit>>)> {
2067    let clause_set: HashSet<Vec<(u32, bool)>> = clauses.iter().map(|c| canon_clause(c)).collect();
2068    let mut out = Vec::new();
2069    for a in 0..num_vars {
2070        for b in (a + 1)..num_vars {
2071            let mut images = Vec::new();
2072            for c in clauses {
2073                let sc = swap_clause_vars(c, a, b);
2074                if !clause_set.contains(&canon_clause(&sc)) {
2075                    images.push(sc);
2076                }
2077            }
2078            if !images.is_empty() && images.len() <= max_broken {
2079                out.push((a, b, images));
2080            }
2081        }
2082    }
2083    out
2084}
2085
2086/// Decide via **almost-symmetry breaking** (conditional). A transposition `σ = (a,b)` that breaks only a
2087/// few clauses is an automorphism of `F` minus those clauses, so it maps a model `m` of `F` to a model of
2088/// `F` *exactly when* `σ(m)` also satisfies the broken clauses — equivalently when `m` satisfies their
2089/// images `σ(B)`. We therefore add the **guarded** break `(⋀ σ(B)) → (a@0 ≤ b@0)`, encoded with a
2090/// reification `z_c ↔ c` per image clause. Sound: where the guard holds, both `m` and `σ(m)` are models and
2091/// the ordering keeps one; where it does not, `m` is untouched. We break the single almost-symmetry with
2092/// the fewest broken clauses (composing partial breaks can be unsound), so a SAT model is re-checked and an
2093/// UNSAT verdict is faithful. `None` when no transposition breaks few enough clauses.
2094fn almost_symmetry_solve(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Solved> {
2095    if num_vars == 0 || num_vars > 20 || clauses.len() > 256 {
2096        return None;
2097    }
2098    let mut pairs = almost_symmetry_pairs(num_vars, clauses, 2);
2099    if pairs.is_empty() {
2100        return None;
2101    }
2102    // The fewest-broken almost-symmetry: most often active, and we break exactly one for soundness.
2103    pairs.sort_by_key(|(_, _, imgs)| imgs.len());
2104    let (a, b, images) = &pairs[0];
2105
2106    let mut aux = num_vars as u32;
2107    let mut extra: Vec<Vec<Lit>> = Vec::new();
2108    let mut guard_neg: Vec<Lit> = Vec::new();
2109    for img in images {
2110        let z = aux;
2111        aux += 1;
2112        // z ↔ (img is satisfied): (each literal → z) and (z → the clause).
2113        for &l in img {
2114            extra.push(vec![l.negated(), Lit::pos(z)]);
2115        }
2116        let mut zc = vec![Lit::neg(z)];
2117        zc.extend(img.iter().copied());
2118        extra.push(zc);
2119        guard_neg.push(Lit::neg(z));
2120    }
2121    // (⋀ images) → (a ≤ b)   ≡   [⋁ ¬z_c] ∨ ¬a ∨ b
2122    let mut guarded = guard_neg;
2123    guarded.push(Lit::neg(*a as u32));
2124    guarded.push(Lit::pos(*b as u32));
2125    extra.push(guarded);
2126
2127    let mut solver = Solver::new(aux as usize);
2128    for c in clauses {
2129        solver.add_clause(c.clone());
2130    }
2131    for c in &extra {
2132        solver.add_clause(c.clone());
2133    }
2134    match solver.solve() {
2135        SolveResult::Sat(model) => {
2136            let projected: Vec<bool> = model[..num_vars].to_vec();
2137            clauses
2138                .iter()
2139                .all(|c| {
2140                    c.iter()
2141                        .any(|l| projected[l.var() as usize] == l.is_positive())
2142                })
2143                .then_some(Solved {
2144                    answer: Answer::Sat(projected),
2145                    via: Route::AlmostSymmetry,
2146                    proof: Vec::new(),
2147                    conflicts: solver.conflicts(),
2148                })
2149        }
2150        SolveResult::Unsat => Some(Solved {
2151            answer: Answer::Unsat,
2152            via: Route::AlmostSymmetry,
2153            proof: Vec::new(),
2154            conflicts: solver.conflicts(),
2155        }),
2156    }
2157}
2158
2159/// A clause with its variables permuted by `g`.
2160fn apply_perm_to_clause(c: &[Lit], g: &[usize]) -> Vec<Lit> {
2161    c.iter()
2162        .map(|l| Lit::new(g[l.var() as usize] as u32, l.is_positive()))
2163        .collect()
2164}
2165
2166/// Whether the variable permutation `g` preserves the clause SET of `clauses` (`σ(F) = F`) — i.e. `g` is a
2167/// phase-free automorphism of the formula. `g` is a variable bijection, so it maps the (deduplicated)
2168/// clause set injectively into itself; if every image is present, it permutes the set.
2169fn perm_preserves_clause_set(clauses: &[Vec<Lit>], g: &[usize]) -> bool {
2170    let set: HashSet<Vec<(u32, bool)>> = clauses.iter().map(|c| canon_clause(c)).collect();
2171    clauses
2172        .iter()
2173        .all(|c| set.contains(&canon_clause(&apply_perm_to_clause(c, g))))
2174}
2175
2176/// The **common variable automorphisms** of two formulas — phase-free permutations `σ` with `σ(F)=F` AND
2177/// `σ(S)=S`, a generating set for a subgroup of `Aut(F) ∩ Aut(S)`. Detected from each formula's own
2178/// automorphisms and then VERIFIED against *both* clause sets, so every returned generator is a genuine
2179/// common automorphism (a wrong one can never slip through). This is the group under which a *disagreement*
2180/// between `F` and `S` is symmetric: if `σ` fixes both, then `F` and `S` disagree at `a` iff they disagree
2181/// at `σ(a)` — so equivalence checking can be reduced along its orbits.
2182pub fn common_automorphism_generators(
2183    num_vars: usize,
2184    f: &[Vec<Lit>],
2185    s: &[Vec<Lit>],
2186) -> Vec<crate::permgroup::Perm> {
2187    let mut candidates =
2188        crate::sym_break::variable_automorphism_generators(num_vars, f).unwrap_or_default();
2189    candidates.extend(
2190        crate::sym_break::variable_automorphism_generators(num_vars, s).unwrap_or_default(),
2191    );
2192    let mut out: Vec<Vec<usize>> = Vec::new();
2193    for g in candidates {
2194        let well_formed = g.len() == num_vars;
2195        let nontrivial = g.iter().enumerate().any(|(i, &x)| i != x);
2196        if well_formed
2197            && nontrivial
2198            && perm_preserves_clause_set(f, &g)
2199            && perm_preserves_clause_set(s, &g)
2200            && !out.contains(&g)
2201        {
2202            out.push(g);
2203        }
2204    }
2205    out
2206}
2207
2208/// The orbits (as index sets) of `clauses` under the group generated by `gens`, acting by
2209/// `σ(C) = {σ(l) : l ∈ C}`. A clause and its symmetric images share an orbit.
2210fn clause_orbits(clauses: &[Vec<Lit>], gens: &[crate::permgroup::Perm]) -> Vec<Vec<usize>> {
2211    let index: HashMap<Vec<(u32, bool)>, usize> = clauses
2212        .iter()
2213        .enumerate()
2214        .map(|(i, c)| (canon_clause(c), i))
2215        .collect();
2216    let n = clauses.len();
2217    let mut parent: Vec<usize> = (0..n).collect();
2218    fn find(parent: &mut [usize], mut x: usize) -> usize {
2219        while parent[x] != x {
2220            parent[x] = parent[parent[x]];
2221            x = parent[x];
2222        }
2223        x
2224    }
2225    for (i, c) in clauses.iter().enumerate() {
2226        for g in gens {
2227            if let Some(&j) = index.get(&canon_clause(&apply_perm_to_clause(c, g))) {
2228                let (a, b) = (find(&mut parent, i), find(&mut parent, j));
2229                parent[a] = b;
2230            }
2231        }
2232    }
2233    let mut groups: std::collections::BTreeMap<usize, Vec<usize>> =
2234        std::collections::BTreeMap::new();
2235    for i in 0..n {
2236        let r = find(&mut parent, i);
2237        groups.entry(r).or_default().push(i);
2238    }
2239    groups.into_values().collect()
2240}
2241
2242/// A model of `clauses ∧ ¬c` — a witness that `c` is NOT entailed by `clauses` — or `None` if `clauses ⊨ c`.
2243fn entailment_counterexample(
2244    num_vars: usize,
2245    clauses: &[Vec<Lit>],
2246    c: &[Lit],
2247) -> Option<Vec<bool>> {
2248    let mut s = Solver::new(num_vars);
2249    for cl in clauses {
2250        s.add_clause(cl.clone());
2251    }
2252    for &l in c {
2253        s.add_clause(vec![l.negated()]);
2254    }
2255    match s.solve() {
2256        SolveResult::Sat(m) => Some(m),
2257        SolveResult::Unsat => None,
2258    }
2259}
2260
2261/// The verdict of a symmetry-reduced equivalence check.
2262#[derive(Clone, Debug, PartialEq, Eq)]
2263pub enum EquivVerdict {
2264    /// `F` and `S` denote the same Boolean function (same models).
2265    Equivalent,
2266    /// They differ; the assignment satisfies exactly one of the two formulas (a distinguishing witness).
2267    Differ(Vec<bool>),
2268}
2269
2270/// **Logical equivalence `F ≡ S`, symmetry-reduced.** `F ≡ S` iff `F ⊨ S` and `S ⊨ F`, and `F ⊨ S` iff `F`
2271/// entails every clause of `S`. The key reduction: for a common automorphism `σ ∈ Aut(F) ∩ Aut(S)`,
2272/// `F ⊨ C ⟺ F ⊨ σ(C)` (a model of `F ∧ ¬C` maps under `σ` to a model of `F ∧ ¬σ(C)`), so it suffices to
2273/// check **one clause per orbit** of `S`'s clauses under the common symmetry (and dually for `F`). The
2274/// verdict is unchanged from the naive check — only the work shrinks — and a `Differ` witness is a concrete,
2275/// re-checkable disagreement (it satisfies one formula and violates a clause of the other). This is the
2276/// symmetry-aware companion to [`crate::sat::prove_equivalence`].
2277pub fn equivalent_modulo_symmetry(num_vars: usize, f: &[Vec<Lit>], s: &[Vec<Lit>]) -> EquivVerdict {
2278    let gens = common_automorphism_generators(num_vars, f, s);
2279    // F ⊨ S: one representative clause per orbit of S under the shared symmetry.
2280    for orbit in clause_orbits(s, &gens) {
2281        if let Some(m) = entailment_counterexample(num_vars, f, &s[orbit[0]]) {
2282            return EquivVerdict::Differ(m); // satisfies F, violates a clause of S ⇒ F true, S false
2283        }
2284    }
2285    // S ⊨ F: dually.
2286    for orbit in clause_orbits(f, &gens) {
2287        if let Some(m) = entailment_counterexample(num_vars, s, &f[orbit[0]]) {
2288            return EquivVerdict::Differ(m);
2289        }
2290    }
2291    EquivVerdict::Equivalent
2292}
2293
2294/// `(checks_with_symmetry, naive_checks)` — the number of entailment checks the symmetry reduction performs
2295/// (one per clause-orbit, both directions) versus the naive per-clause count. Equal when there is no usable
2296/// common symmetry; strictly smaller when the shared automorphism group fuses clauses into orbits.
2297pub fn equivalence_check_counts(num_vars: usize, f: &[Vec<Lit>], s: &[Vec<Lit>]) -> (usize, usize) {
2298    let gens = common_automorphism_generators(num_vars, f, s);
2299    (
2300        clause_orbits(s, &gens).len() + clause_orbits(f, &gens).len(),
2301        s.len() + f.len(),
2302    )
2303}
2304
2305/// The symmetries of an **optimization** problem `(F, weights)`: variable automorphisms of `F` that *also*
2306/// preserve the objective (`weights[g[v]] = weights[v]` for all `v`). Under such a `σ` the objective is
2307/// constant on orbits, so every optimal model's whole orbit is optimal — the group along which the optimum
2308/// may be symmetry-reduced. Verified against both `F` and the weights, so every generator is genuine.
2309pub fn optimization_symmetry_generators(
2310    num_vars: usize,
2311    clauses: &[Vec<Lit>],
2312    weights: &[i64],
2313) -> Vec<crate::permgroup::Perm> {
2314    crate::sym_break::variable_automorphism_generators(num_vars, clauses)
2315        .unwrap_or_default()
2316        .into_iter()
2317        .filter(|g| g.len() == num_vars && (0..num_vars).all(|v| weights[g[v]] == weights[v]))
2318        .collect()
2319}
2320
2321/// `F` augmented with sound single-bit lex-leader clauses for the optimization symmetry. Each generator `g`
2322/// contributes `x_v ≤ x_{g[v]}` at its least moved point `v`; the lex-minimum of any orbit satisfies all of
2323/// them, so — since the objective is constant on orbits — an *optimal* model always survives. The optimum is
2324/// therefore unchanged while the model space shrinks.
2325fn optimization_break(num_vars: usize, clauses: &[Vec<Lit>], weights: &[i64]) -> Vec<Vec<Lit>> {
2326    let mut broken = clauses.to_vec();
2327    for g in optimization_symmetry_generators(num_vars, clauses, weights) {
2328        if let Some(v) = (0..num_vars).find(|&v| g[v] != v) {
2329            broken.push(vec![Lit::new(v as u32, false), Lit::new(g[v] as u32, true)]);
2330            // ¬x_v ∨ x_{g[v]}
2331        }
2332    }
2333    broken
2334}
2335
2336/// Enumerate the models of `clauses` (CDCL + blocking) and return the minimum-weight one with the number of
2337/// models visited: `(optimum, witness, models_enumerated)`, or `None` if unsatisfiable. A FRESH solver is
2338/// built each round with the accumulated blocking clauses — our CDCL core is not incrementally re-solvable
2339/// (the same pattern the model-counting routines use), so reusing one solver across `solve()` calls would
2340/// loop.
2341fn min_weight_model(
2342    num_vars: usize,
2343    clauses: &[Vec<Lit>],
2344    weights: &[i64],
2345) -> Option<(i64, Vec<bool>, usize)> {
2346    let mut working = clauses.to_vec();
2347    let mut best: Option<(i64, Vec<bool>)> = None;
2348    let mut enumerated = 0usize;
2349    loop {
2350        let mut solver = Solver::new(num_vars);
2351        for c in &working {
2352            solver.add_clause(c.clone());
2353        }
2354        match solver.solve() {
2355            SolveResult::Unsat => break,
2356            SolveResult::Sat(model) => {
2357                enumerated += 1;
2358                let w: i64 = (0..num_vars)
2359                    .filter(|&i| model[i])
2360                    .map(|i| weights[i])
2361                    .sum();
2362                if best.as_ref().map_or(true, |(bw, _)| w < *bw) {
2363                    best = Some((w, model[..num_vars].to_vec()));
2364                }
2365                working.push(
2366                    (0..num_vars)
2367                        .map(|i| Lit::new(i as u32, !model[i]))
2368                        .collect(),
2369                );
2370            }
2371        }
2372    }
2373    best.map(|(w, m)| (w, m, enumerated))
2374}
2375
2376/// **Weighted minimization, symmetry-reduced.** Minimise `Σ weights[i]·x_i` over the models of `clauses`,
2377/// exploiting [`optimization_symmetry_generators`]: break the objective-preserving symmetry, then search the
2378/// reduced model space. SOUND — the optimum is identical to the unbroken problem (an optimal orbit's
2379/// lex-leader survives the break and has the same objective) and the witness is a genuine model of the
2380/// original `F`. `None` iff `F` is unsatisfiable. The symmetry-aware optimizer (a new problem class beyond
2381/// the decision/counting/equivalence faces).
2382pub fn optimize_modulo_symmetry(
2383    num_vars: usize,
2384    clauses: &[Vec<Lit>],
2385    weights: &[i64],
2386) -> Option<(i64, Vec<bool>)> {
2387    let broken = optimization_break(num_vars, clauses, weights);
2388    min_weight_model(num_vars, &broken, weights).map(|(w, m, _)| (w, m))
2389}
2390
2391/// `(models_with_symmetry, models_without_symmetry)` — how many candidate models the optimizer enumerates
2392/// with the symmetry break versus the naive enumeration. Equal with no usable symmetry, smaller when the
2393/// objective-preserving group fuses optimal (and non-optimal) models into orbits.
2394pub fn optimize_enumeration_counts(
2395    num_vars: usize,
2396    clauses: &[Vec<Lit>],
2397    weights: &[i64],
2398) -> (usize, usize) {
2399    let broken = optimization_break(num_vars, clauses, weights);
2400    let with = min_weight_model(num_vars, &broken, weights).map_or(0, |(_, _, c)| c);
2401    let without = min_weight_model(num_vars, clauses, weights).map_or(0, |(_, _, c)| c);
2402    (with, without)
2403}
2404
2405/// The full orbit of a Boolean assignment `m` under the group generated by `gens` (action `σ(m)[g[v]] =
2406/// m[v]`), as a set of complete assignments — no projection, so it is exact for counting.
2407fn full_assignment_orbit(
2408    num_vars: usize,
2409    m: &[bool],
2410    gens: &[crate::permgroup::Perm],
2411) -> Vec<Vec<bool>> {
2412    let mut seen: HashSet<Vec<bool>> = HashSet::from([m.to_vec()]);
2413    let mut out = vec![m.to_vec()];
2414    let mut i = 0;
2415    while i < out.len() {
2416        let cur = out[i].clone();
2417        i += 1;
2418        for g in gens {
2419            let mut pm = vec![false; num_vars];
2420            for v in 0..num_vars {
2421                pm[g[v]] = cur[v];
2422            }
2423            if seen.insert(pm.clone()) {
2424                out.push(pm);
2425            }
2426        }
2427    }
2428    out
2429}
2430
2431/// **Symmetry-accelerated weighted model counting** — the partition function `Z = Σ_{m ⊨ F} W(m)` with
2432/// literal weights `W(m) = Π_v weight[v].{1 if m[v] else 0}`. The formula's variable symmetry partitions the
2433/// models into orbits, so each `solve()` recovers one model, its whole orbit is enumerated and its members'
2434/// weights summed, then the entire orbit is blocked — **one solve per orbit** instead of per model. Exact for
2435/// ARBITRARY weights (every model's true weight is summed; the symmetry only groups the search), the
2436/// symmetry-aware analogue of weighted #SAT / lifted inference. Returns `Z`.
2437pub fn weighted_model_count(num_vars: usize, clauses: &[Vec<Lit>], weight: &[(i64, i64)]) -> i128 {
2438    let gens =
2439        crate::sym_break::variable_automorphism_generators(num_vars, clauses).unwrap_or_default();
2440    let weight_of = |m: &[bool]| -> i128 {
2441        (0..num_vars)
2442            .map(|v| {
2443                if m[v] {
2444                    weight[v].1 as i128
2445                } else {
2446                    weight[v].0 as i128
2447                }
2448            })
2449            .product()
2450    };
2451    let mut working = clauses.to_vec();
2452    let mut z = 0i128;
2453    loop {
2454        let mut solver = Solver::new(num_vars);
2455        for c in &working {
2456            solver.add_clause(c.clone());
2457        }
2458        match solver.solve() {
2459            SolveResult::Unsat => break,
2460            SolveResult::Sat(model) => {
2461                let orbit = full_assignment_orbit(num_vars, &model[..num_vars], &gens);
2462                z += orbit.iter().map(|m| weight_of(m)).sum::<i128>();
2463                for m in &orbit {
2464                    working.push((0..num_vars).map(|i| Lit::new(i as u32, !m[i])).collect());
2465                }
2466            }
2467        }
2468    }
2469    z
2470}
2471
2472/// `(orbit_solves, total_models)` — how many `solve()` calls the symmetry-accelerated weighted count makes
2473/// (one per model-orbit) versus the number of models. Equal with no usable symmetry, smaller when symmetry
2474/// fuses models into orbits.
2475pub fn weighted_model_count_solve_counts(num_vars: usize, clauses: &[Vec<Lit>]) -> (usize, usize) {
2476    let gens =
2477        crate::sym_break::variable_automorphism_generators(num_vars, clauses).unwrap_or_default();
2478    let mut working = clauses.to_vec();
2479    let (mut solves, mut models) = (0usize, 0usize);
2480    loop {
2481        let mut solver = Solver::new(num_vars);
2482        for c in &working {
2483            solver.add_clause(c.clone());
2484        }
2485        match solver.solve() {
2486            SolveResult::Unsat => break,
2487            SolveResult::Sat(model) => {
2488                solves += 1;
2489                let orbit = full_assignment_orbit(num_vars, &model[..num_vars], &gens);
2490                models += orbit.len();
2491                for m in &orbit {
2492                    working.push((0..num_vars).map(|i| Lit::new(i as u32, !m[i])).collect());
2493                }
2494            }
2495        }
2496    }
2497    (solves, models)
2498}
2499
2500/// Re-label a list of signatures to dense ranks `0..k` in sorted order — equal signatures get equal ranks.
2501/// The canonical relabelling that makes color refinement's fixpoint test stable.
2502fn rank_signatures<S: Ord + Clone>(sigs: &[S]) -> Vec<usize> {
2503    let mut distinct: Vec<S> = sigs.to_vec();
2504    distinct.sort();
2505    distinct.dedup();
2506    sigs.iter()
2507        .map(|s| distinct.binary_search(s).expect("present"))
2508        .collect()
2509}
2510
2511/// **Color refinement (1-dimensional Weisfeiler–Leman)** of a formula's variable–clause incidence graph —
2512/// the coarsest *equitable* partition of the variables, computed in polynomial time. Variables and clauses
2513/// are coloured (clauses initialised by width); each round recolours a clause by the sorted multiset of its
2514/// incident `(variable colour, sign)` pairs and a variable by the sorted multiset of its incident
2515/// `(clause colour, sign)` pairs, to a fixpoint. The result `cell[v]` is the variable's colour.
2516///
2517/// This is the polynomial *foundation* of symmetry detection (the pre-filter saucy/nauty run before the
2518/// exponential search) and a SOUND over-approximation of the orbit partition: every phase-free variable
2519/// automorphism preserves the colouring, so `orbit(v) ⊆ cell(v)` — variables of different colours are
2520/// provably in different orbits. Returns dense cell indices `0..k`.
2521pub fn color_refinement(num_vars: usize, clauses: &[Vec<Lit>]) -> Vec<usize> {
2522    equitable_refine(num_vars, clauses, &vec![0usize; num_vars])
2523}
2524
2525/// Color refinement to a stable (equitable) partition, starting from an arbitrary initial variable coloring
2526/// `var_init` (rather than the all-equal coloring [`color_refinement`] uses). This is the refinement step of
2527/// individualization–refinement: after individualizing a vertex, re-stabilize from the perturbed coloring.
2528fn equitable_refine(num_vars: usize, clauses: &[Vec<Lit>], var_init: &[usize]) -> Vec<usize> {
2529    let mut var_color = rank_signatures(var_init);
2530    let mut clause_color: Vec<usize> =
2531        rank_signatures(&clauses.iter().map(|c| c.len()).collect::<Vec<_>>());
2532    loop {
2533        // Recolour clauses by the multiset of incident (variable colour, sign).
2534        let clause_sig: Vec<(usize, Vec<(usize, bool)>)> = clauses
2535            .iter()
2536            .enumerate()
2537            .map(|(ci, c)| {
2538                let mut nbrs: Vec<(usize, bool)> = c
2539                    .iter()
2540                    .map(|l| (var_color[l.var() as usize], l.is_positive()))
2541                    .collect();
2542                nbrs.sort_unstable();
2543                (clause_color[ci], nbrs)
2544            })
2545            .collect();
2546        let new_clause_color = rank_signatures(&clause_sig);
2547        // Recolour variables by the multiset of incident (clause colour, sign).
2548        let mut var_nbrs: Vec<Vec<(usize, bool)>> = vec![Vec::new(); num_vars];
2549        for (ci, c) in clauses.iter().enumerate() {
2550            for l in c {
2551                var_nbrs[l.var() as usize].push((new_clause_color[ci], l.is_positive()));
2552            }
2553        }
2554        for nbrs in var_nbrs.iter_mut() {
2555            nbrs.sort_unstable();
2556        }
2557        let var_sig: Vec<(usize, Vec<(usize, bool)>)> = (0..num_vars)
2558            .map(|v| (var_color[v], std::mem::take(&mut var_nbrs[v])))
2559            .collect();
2560        let new_var_color = rank_signatures(&var_sig);
2561        if new_var_color == var_color && new_clause_color == clause_color {
2562            break; // the partition is stable (equitable)
2563        }
2564        var_color = new_var_color;
2565        clause_color = new_clause_color;
2566    }
2567    var_color
2568}
2569
2570/// The number of cells in the color-refinement (equitable) partition — a cheap polynomial symmetry
2571/// indicator. At most the number of variable orbits (`cells ≤ orbits`, since each cell is a union of orbits).
2572pub fn color_refinement_cells(num_vars: usize, clauses: &[Vec<Lit>]) -> usize {
2573    color_refinement(num_vars, clauses)
2574        .iter()
2575        .copied()
2576        .max()
2577        .map_or(0, |m| m + 1)
2578}
2579
2580/// The variables that color refinement places in a **singleton cell** — provably fixed by every (phase-free)
2581/// automorphism, since `orbit(v) ⊆ cell(v)` and `|cell(v)| = 1` forces `|orbit(v)| = 1`. A polynomial
2582/// certificate of asymmetry: these variables can be skipped entirely when detecting or breaking symmetry.
2583pub fn provably_asymmetric_variables(num_vars: usize, clauses: &[Vec<Lit>]) -> Vec<usize> {
2584    let cells = color_refinement(num_vars, clauses);
2585    let mut size = vec![0usize; num_vars];
2586    for &c in &cells {
2587        size[c] += 1;
2588    }
2589    (0..num_vars).filter(|&v| size[cells[v]] == 1).collect()
2590}
2591
2592/// The **variable co-occurrence matrix** `A[u][v]` = number of clauses containing both variables `u` and `v`
2593/// (`0` on the diagonal) — the natural weighted graph on the formula's variables.
2594fn cooccurrence_matrix(num_vars: usize, clauses: &[Vec<Lit>]) -> Vec<Vec<i64>> {
2595    let mut a = vec![vec![0i64; num_vars]; num_vars];
2596    for c in clauses {
2597        let vars: Vec<usize> = c.iter().map(|l| l.var() as usize).collect();
2598        for &u in &vars {
2599            for &v in &vars {
2600                if u != v {
2601                    a[u][v] += 1;
2602                }
2603            }
2604        }
2605    }
2606    a
2607}
2608
2609/// The coarsest **equitable partition** of the variable co-occurrence graph `A`: 1-WL on the weighted graph,
2610/// recolouring each vertex by the sorted multiset of `(neighbour colour, edge weight)` to a fixpoint.
2611fn equitable_partition_of(num_vars: usize, a: &[Vec<i64>]) -> Vec<usize> {
2612    let mut color = vec![0usize; num_vars];
2613    loop {
2614        let sig: Vec<(usize, Vec<(usize, i64)>)> = (0..num_vars)
2615            .map(|u| {
2616                let mut nbrs: Vec<(usize, i64)> = (0..num_vars)
2617                    .filter(|&v| a[u][v] != 0)
2618                    .map(|v| (color[v], a[u][v]))
2619                    .collect();
2620                nbrs.sort_unstable();
2621                (color[u], nbrs)
2622            })
2623            .collect();
2624        let next = rank_signatures(&sig);
2625        if next == color {
2626            return color;
2627        }
2628        color = next;
2629    }
2630}
2631
2632/// A **fractional automorphism** of a formula: a *doubly-stochastic* matrix `B` commuting with the variable
2633/// co-occurrence matrix `A` (`BA = AB`) — the LP relaxation of an automorphism (a *permutation* matrix
2634/// commuting with `A`). The canonical one is block-averaging over the coarsest equitable partition
2635/// (`equitable_partition_of`): `B[u][v] = 1/|cell(u)|` if `u,v` share a cell, else `0`. By Tinhofer's
2636/// theorem it commutes with `A` iff the partition is equitable, and it is **non-trivial** (not a permutation)
2637/// exactly when the partition is non-discrete — i.e. exactly when the formula has non-trivial 1-WL symmetry.
2638///
2639/// Returns the partition `cell[v]`. Its non-discreteness certifies a fractional automorphism; the commutation
2640/// `BA = AB` is checked exactly (over integers, by clearing the `1/|cell|` denominators) by
2641/// [`is_fractional_automorphism`].
2642pub fn fractional_automorphism(num_vars: usize, clauses: &[Vec<Lit>]) -> Vec<usize> {
2643    equitable_partition_of(num_vars, &cooccurrence_matrix(num_vars, clauses))
2644}
2645
2646/// Verify that block-averaging over `partition` gives a doubly-stochastic matrix `B` commuting with the
2647/// co-occurrence matrix `A`. `B` is doubly-stochastic by construction (each row/column sums to 1), so this
2648/// checks `BA = AB`, which holds iff `partition` is equitable — the exact (integer) certificate. The identity
2649/// `(1/|cell(u)|)·Σ_{x∈cell(u)} A[x][w] = (1/|cell(w)|)·Σ_{x∈cell(w)} A[u][x]` is verified cross-multiplied.
2650pub fn is_fractional_automorphism(
2651    num_vars: usize,
2652    clauses: &[Vec<Lit>],
2653    partition: &[usize],
2654) -> bool {
2655    let a = cooccurrence_matrix(num_vars, clauses);
2656    let d = partition.iter().copied().max().map_or(0, |m| m + 1);
2657    let mut cell: Vec<Vec<usize>> = vec![Vec::new(); d];
2658    for (v, &c) in partition.iter().enumerate() {
2659        cell[c].push(v);
2660    }
2661    let sum_over = |rows: &[usize], w: usize, by_row: bool| -> i64 {
2662        rows.iter()
2663            .map(|&x| if by_row { a[x][w] } else { a[w][x] })
2664            .sum()
2665    };
2666    for u in 0..num_vars {
2667        for w in 0..num_vars {
2668            let cu = &cell[partition[u]];
2669            let cw = &cell[partition[w]];
2670            // (1/|cu|)·Σ_{x∈cu} A[x][w] == (1/|cw|)·Σ_{x∈cw} A[u][x]  (cross-multiplied to integers).
2671            let lhs = cw.len() as i64 * sum_over(cu, w, true);
2672            let rhs = cu.len() as i64 * sum_over(cw, u, false);
2673            if lhs != rhs {
2674                return false;
2675            }
2676        }
2677    }
2678    true
2679}
2680
2681/// **2-dimensional Weisfeiler–Leman (2-WL)** of a formula's variables — color refinement lifted from
2682/// vertices to *ordered pairs*. Each pair `(i,j)` is colored: the diagonal by its 1-WL vertex color, an
2683/// off-diagonal pair by `(1-WL(i), 1-WL(j), co-occurrence signature)` where the signature is the sorted
2684/// multiset over clauses containing both of `(clause width, sign of i, sign of j)`. Each round recolors
2685/// `(i,j)` by `(old color, sorted multiset over all k of (color(i,k), color(k,j)))`, to a fixpoint.
2686///
2687/// Strictly stronger than 1-WL (its diagonal refines the 1-WL coloring, and it sees pair structure 1-WL is
2688/// blind to) and a SOUND over-approximation of the **orbitals** (orbits on ordered pairs): every variable
2689/// automorphism preserves the pair coloring, so `orbital(i,j) ⊆ paircell(i,j)`. Returns the `n×n` color
2690/// matrix. `O(rounds · n³)`, so intended for moderate `n`.
2691pub fn two_wl_pair_colors(num_vars: usize, clauses: &[Vec<Lit>]) -> Vec<Vec<usize>> {
2692    let wl1 = color_refinement(num_vars, clauses);
2693    // Co-occurrence signature per ordered pair: how i and j appear together across clauses.
2694    let mut cooc: Vec<Vec<Vec<(usize, bool, bool)>>> = vec![vec![Vec::new(); num_vars]; num_vars];
2695    for c in clauses {
2696        let lits: Vec<(usize, bool)> = c
2697            .iter()
2698            .map(|l| (l.var() as usize, l.is_positive()))
2699            .collect();
2700        for &(vi, si) in &lits {
2701            for &(vj, sj) in &lits {
2702                if vi != vj {
2703                    cooc[vi][vj].push((c.len(), si, sj));
2704                }
2705            }
2706        }
2707    }
2708    for row in cooc.iter_mut() {
2709        for s in row.iter_mut() {
2710            s.sort_unstable();
2711        }
2712    }
2713    // Initial pair signature: (diagonal?, 1-WL(i), 1-WL(j), co-occurrence).
2714    let mut flat: Vec<(bool, usize, usize, Vec<(usize, bool, bool)>)> =
2715        Vec::with_capacity(num_vars * num_vars);
2716    for i in 0..num_vars {
2717        for j in 0..num_vars {
2718            flat.push((i == j, wl1[i], wl1[j], cooc[i][j].clone()));
2719        }
2720    }
2721    let mut color: Vec<usize> = rank_signatures(&flat); // indexed i*num_vars + j
2722    let at = |i: usize, j: usize| i * num_vars + j;
2723    loop {
2724        let mut sig: Vec<(usize, Vec<(usize, usize)>)> = Vec::with_capacity(num_vars * num_vars);
2725        for i in 0..num_vars {
2726            for j in 0..num_vars {
2727                let mut tri: Vec<(usize, usize)> = (0..num_vars)
2728                    .map(|k| (color[at(i, k)], color[at(k, j)]))
2729                    .collect();
2730                tri.sort_unstable();
2731                sig.push((color[at(i, j)], tri));
2732            }
2733        }
2734        let next = rank_signatures(&sig);
2735        if next == color {
2736            break;
2737        }
2738        color = next;
2739    }
2740    (0..num_vars)
2741        .map(|i| (0..num_vars).map(|j| color[at(i, j)]).collect())
2742        .collect()
2743}
2744
2745/// The number of distinct 2-WL pair colors — at most the number of orbitals (`pair-cells ≤ orbitals`).
2746pub fn two_wl_pair_cells(num_vars: usize, clauses: &[Vec<Lit>]) -> usize {
2747    let c = two_wl_pair_colors(num_vars, clauses);
2748    c.iter().flatten().copied().max().map_or(0, |m| m + 1)
2749}
2750
2751/// The label-independent **2-WL fingerprint**: the sorted multiset of pair-color class sizes. Two formulas
2752/// with different fingerprints are provably non-isomorphic (as colored variable structures) — the
2753/// distinguishing power that separates, e.g., a 6-cycle from two triangles where 1-WL cannot.
2754pub fn two_wl_fingerprint(num_vars: usize, clauses: &[Vec<Lit>]) -> Vec<usize> {
2755    let c = two_wl_pair_colors(num_vars, clauses);
2756    let k = c.iter().flatten().copied().max().map_or(0, |m| m + 1);
2757    let mut sizes = vec![0usize; k];
2758    for &col in c.iter().flatten() {
2759        sizes[col] += 1;
2760    }
2761    sizes.sort_unstable();
2762    sizes
2763}
2764
2765/// The **coherent configuration** (association scheme) that 2-WL stabilizes into: its `d` basis relations
2766/// (the stable pair-color classes `R_0,…,R_{d-1}`) and their **intersection numbers**
2767/// `p[i][j][k] = |{z : (x,z) ∈ R_i and (z,y) ∈ R_j}|` for any `(x,y) ∈ R_k`. Returns `(d, p)`.
2768///
2769/// The intersection numbers are well-defined *because* the coloring is coherent (independent of which
2770/// `(x,y) ∈ R_k` is chosen) — and that well-definedness is checked over EVERY pair, FAIL-CLOSED: `None` if
2771/// the 2-WL coloring is somehow not coherent (it always is once stabilized, so this certifies it). These are
2772/// the structure constants of the coherent algebra — the combinatorial dual of the class-algebra structure
2773/// constants ([`crate::permgroup::class_multiplication_coefficients`]); for a group's orbital configuration
2774/// they are the orbital intersection numbers.
2775pub fn coherent_configuration_constants(
2776    num_vars: usize,
2777    clauses: &[Vec<Lit>],
2778) -> Option<(usize, Vec<Vec<Vec<u128>>>)> {
2779    let n = num_vars;
2780    let pc = two_wl_pair_colors(n, clauses);
2781    let d = pc.iter().flatten().copied().max().map_or(0, |m| m + 1);
2782    if d == 0 {
2783        return None;
2784    }
2785    // The d × d count matrix [(x,z)-color][(z,y)-color] for a fixed pair (x,y).
2786    let count_matrix = |x: usize, y: usize| -> Vec<Vec<u128>> {
2787        let mut m = vec![vec![0u128; d]; d];
2788        for z in 0..n {
2789            m[pc[x][z]][pc[z][y]] += 1;
2790        }
2791        m
2792    };
2793    // p[i][j][k] from one representative pair per relation k.
2794    let mut rep: Vec<Option<(usize, usize)>> = vec![None; d];
2795    for i in 0..n {
2796        for j in 0..n {
2797            rep[pc[i][j]].get_or_insert((i, j));
2798        }
2799    }
2800    let mut p = vec![vec![vec![0u128; d]; d]; d];
2801    for k in 0..d {
2802        let (x, y) = rep[k]?;
2803        let m = count_matrix(x, y);
2804        for i in 0..d {
2805            for j in 0..d {
2806                p[i][j][k] = m[i][j];
2807            }
2808        }
2809    }
2810    // COHERENCE (fail-closed): every pair in R_k must yield the same intersection numbers.
2811    for x in 0..n {
2812        for y in 0..n {
2813            let k = pc[x][y];
2814            let m = count_matrix(x, y);
2815            for i in 0..d {
2816                for j in 0..d {
2817                    if m[i][j] != p[i][j][k] {
2818                        return None;
2819                    }
2820                }
2821            }
2822        }
2823    }
2824    Some((d, p))
2825}
2826
2827/// The **rank** of the coherent configuration — the number of basis relations (`d`), the dimension of the
2828/// coherent algebra. Equal to [`two_wl_pair_cells`]; for a group's orbital configuration it is the orbital
2829/// rank. `None` when the configuration is out of range / not coherent.
2830pub fn coherent_rank(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<usize> {
2831    coherent_configuration_constants(num_vars, clauses).map(|(d, _)| d)
2832}
2833
2834/// Simultaneously diagonalize commuting `d×d` matrices over `GF(p)`: refine `GF(p)^d` into common 1-dim
2835/// eigenspaces by splitting on each matrix in turn, and return, per eigenspace, the vector of its eigenvalues
2836/// across the matrices. `None` if they do not fully diagonalize over this `GF(p)` (the caller retries with
2837/// another prime). The same construction the Burnside–Dixon character table uses, applied to the coherent
2838/// algebra's intersection matrices.
2839fn gf_simultaneous_eigenvalues(mmats: &[Vec<Vec<u64>>], d: usize, p: u64) -> Option<Vec<Vec<u64>>> {
2840    use crate::permgroup::{gf_mat_vec, gf_nullspace, mod_inv};
2841    let mut subspaces: Vec<Vec<Vec<u64>>> = vec![(0..d)
2842        .map(|i| {
2843            let mut e = vec![0u64; d];
2844            e[i] = 1;
2845            e
2846        })
2847        .collect()];
2848    for mi in mmats {
2849        if subspaces.iter().all(|s| s.len() == 1) {
2850            break;
2851        }
2852        let mut next: Vec<Vec<Vec<u64>>> = Vec::new();
2853        for s in &subspaces {
2854            if s.len() == 1 {
2855                next.push(s.clone());
2856                continue;
2857            }
2858            let bn = s.len();
2859            let mb: Vec<Vec<u64>> = s.iter().map(|b| gf_mat_vec(mi, b, p)).collect();
2860            let mut pieces: Vec<Vec<Vec<u64>>> = Vec::new();
2861            let mut covered = 0usize;
2862            for lam in 0..p {
2863                let mut rows = vec![vec![0u64; bn]; d];
2864                for k in 0..d {
2865                    for (jj, sj) in s.iter().enumerate() {
2866                        let shift = (lam as u128 * sj[k] as u128) % p as u128;
2867                        rows[k][jj] = ((mb[jj][k] as u128 + p as u128 - shift) % p as u128) as u64;
2868                    }
2869                }
2870                let ns = gf_nullspace(rows, bn, p);
2871                if ns.is_empty() {
2872                    continue;
2873                }
2874                let eig: Vec<Vec<u64>> = ns
2875                    .iter()
2876                    .map(|c| {
2877                        let mut x = vec![0u64; d];
2878                        for (jj, &cj) in c.iter().enumerate() {
2879                            if cj != 0 {
2880                                for k in 0..d {
2881                                    x[k] = ((x[k] as u128 + cj as u128 * s[jj][k] as u128)
2882                                        % p as u128)
2883                                        as u64;
2884                                }
2885                            }
2886                        }
2887                        x
2888                    })
2889                    .collect();
2890                covered += eig.len();
2891                pieces.push(eig);
2892                if covered == bn {
2893                    break;
2894                }
2895            }
2896            if covered == bn {
2897                next.extend(pieces);
2898            } else {
2899                next.push(s.clone());
2900            }
2901        }
2902        subspaces = next;
2903    }
2904    if subspaces.iter().any(|s| s.len() != 1) {
2905        return None; // not fully diagonalizable over this GF(p)
2906    }
2907    Some(
2908        subspaces
2909            .iter()
2910            .map(|s| {
2911                let v = &s[0];
2912                let t = v.iter().position(|&x| x != 0).unwrap();
2913                let inv = mod_inv(v[t], p);
2914                mmats
2915                    .iter()
2916                    .map(|mi| {
2917                        let mv = gf_mat_vec(mi, v, p);
2918                        (mv[t] as u128 * inv as u128 % p as u128) as u64
2919                    })
2920                    .collect()
2921            })
2922            .collect(),
2923    )
2924}
2925
2926/// The **eigenmatrix (P-matrix) of the association scheme** of a formula's variable symmetry — the scheme's
2927/// "character table". The coherent configuration ([`coherent_configuration_constants`]) yields a commutative
2928/// algebra spanned by the relation matrices `A_i` (`A_i A_j = Σ_k a_{ijk} A_k`); its intersection matrices
2929/// `B_i` (`B_i[k][j] = a_{ijk}`) commute and are simultaneously diagonalizable, and `P[m][i]` is the
2930/// eigenvalue of `A_i` on the `m`-th common eigenspace. Computed exactly over a `GF(p)` chosen (by search)
2931/// so the algebra splits — Dixon's method applied to the scheme. Returns `(prime, P)`.
2932///
2933/// The rows of `P` are exactly the 1-dimensional representations of the coherent algebra, so
2934/// `P[m][i]·P[m][j] = Σ_k a_{ijk}·P[m][k]`; one row is the valencies `n_i` (the all-ones eigenvector). `None`
2935/// when the scheme is not commutative, is out of range, or no small prime splits it. Mirrors
2936/// [`crate::permgroup::character_table`] for the group ↔ scheme analogy.
2937pub fn association_scheme_eigenmatrix(
2938    num_vars: usize,
2939    clauses: &[Vec<Lit>],
2940) -> Option<(u64, Vec<Vec<u64>>)> {
2941    let (d, a) = coherent_configuration_constants(num_vars, clauses)?;
2942    if d == 0 {
2943        return None;
2944    }
2945    // The algebra must be commutative for a P-matrix to exist.
2946    for i in 0..d {
2947        for j in 0..d {
2948            for k in 0..d {
2949                if a[i][j][k] != a[j][i][k] {
2950                    return None;
2951                }
2952            }
2953        }
2954    }
2955    // Valencies n_i = Σ_j a_{ij0} (independent of the third index — the all-ones eigenvalue).
2956    let valency: Vec<u128> = (0..d).map(|i| (0..d).map(|j| a[i][j][0]).sum()).collect();
2957    let mut tried = 0;
2958    let mut p = 2u64;
2959    while tried < 200 && p < 100_000 {
2960        if crate::permgroup::is_prime(p) {
2961            tried += 1;
2962            let mmats: Vec<Vec<Vec<u64>>> = (0..d)
2963                .map(|i| {
2964                    (0..d)
2965                        .map(|k| (0..d).map(|j| (a[i][j][k] % p as u128) as u64).collect())
2966                        .collect()
2967                })
2968                .collect();
2969            if let Some(rows) = gf_simultaneous_eigenvalues(&mmats, d, p) {
2970                // FAIL-CLOSED: each row is a 1-dim rep of the algebra, and some row is the valencies.
2971                let hom_ok = rows.iter().all(|row| {
2972                    (0..d).all(|i| {
2973                        (0..d).all(|j| {
2974                            let lhs = row[i] as u128 * row[j] as u128 % p as u128;
2975                            let rhs = (0..d)
2976                                .map(|k| (a[i][j][k] % p as u128) * row[k] as u128 % p as u128)
2977                                .sum::<u128>()
2978                                % p as u128;
2979                            lhs == rhs
2980                        })
2981                    })
2982                });
2983                let has_valency = rows
2984                    .iter()
2985                    .any(|row| (0..d).all(|i| row[i] as u128 == valency[i] % p as u128));
2986                if hom_ok && has_valency {
2987                    return Some((p, rows));
2988                }
2989            }
2990        }
2991        p += 1;
2992    }
2993    None
2994}
2995
2996/// The **multiplicities of the association scheme** — the dimensions `m_j` of the common eigenspaces of the
2997/// relation matrices in the full `|X|`-dimensional space; the "degrees" of the scheme, dual to the valencies.
2998/// From the eigenmatrix `P` (#eigenmatrix) and the scheme orthogonality relation
2999/// `m_j = |X| / Σ_i P[j][i]·P[j][ī]/k_i` (`k_i` = valency, `ī` = transpose relation). Computed exactly over a
3000/// `GF(p)` chosen to split the algebra AND exceed `|X|` (so the small positive integer `m_j ≤ |X|` decodes
3001/// uniquely). Returns the multiplicities sorted ascending.
3002///
3003/// FAIL-CLOSED: `None` unless every `m_j` is a positive integer `≤ |X|`, `Σ_j m_j = |X|` (the eigenspaces
3004/// partition the space), and the trivial eigenspace (the valency row of `P`) has multiplicity 1. For a
3005/// multiplicity-free group action these are exactly the degrees of the constituent irreducibles.
3006pub fn association_scheme_multiplicities(
3007    num_vars: usize,
3008    clauses: &[Vec<Lit>],
3009) -> Option<Vec<u128>> {
3010    let (d, a) = coherent_configuration_constants(num_vars, clauses)?;
3011    if d == 0 {
3012        return None;
3013    }
3014    for i in 0..d {
3015        for j in 0..d {
3016            for k in 0..d {
3017                if a[i][j][k] != a[j][i][k] {
3018                    return None; // commutative only
3019                }
3020            }
3021        }
3022    }
3023    let valency: Vec<u128> = (0..d).map(|i| (0..d).map(|j| a[i][j][0]).sum()).collect();
3024    // The transpose relation ī (the reverse of relation i) from the 2-WL pair coloring.
3025    let pc = two_wl_pair_colors(num_vars, clauses);
3026    let mut transpose = vec![usize::MAX; d];
3027    for x in 0..num_vars {
3028        for y in 0..num_vars {
3029            let i = pc[x][y];
3030            if transpose[i] == usize::MAX {
3031                transpose[i] = pc[y][x];
3032            }
3033        }
3034    }
3035    let n = num_vars as u128;
3036    let mut tried = 0;
3037    let mut p = 2u64;
3038    while tried < 300 && p < 1_000_000 {
3039        // The prime must split the algebra AND exceed |X| so multiplicities decode uniquely.
3040        if crate::permgroup::is_prime(p) && p as u128 > n {
3041            tried += 1;
3042            let mmats: Vec<Vec<Vec<u64>>> = (0..d)
3043                .map(|i| {
3044                    (0..d)
3045                        .map(|k| (0..d).map(|j| (a[i][j][k] % p as u128) as u64).collect())
3046                        .collect()
3047                })
3048                .collect();
3049            if let Some(rows) = gf_simultaneous_eigenvalues(&mmats, d, p) {
3050                let mut mult = Vec::with_capacity(d);
3051                let mut ok = true;
3052                for row in &rows {
3053                    let mut denom = 0u64;
3054                    for i in 0..d {
3055                        let ki = (valency[i] % p as u128) as u64;
3056                        let term = (row[i] as u128 * row[transpose[i]] as u128 % p as u128) as u64;
3057                        denom = ((denom as u128
3058                            + term as u128 * crate::permgroup::mod_inv(ki, p) as u128)
3059                            % p as u128) as u64;
3060                    }
3061                    if denom == 0 {
3062                        ok = false;
3063                        break;
3064                    }
3065                    let m =
3066                        (n % p as u128) * crate::permgroup::mod_inv(denom, p) as u128 % p as u128;
3067                    if m == 0 || m > n {
3068                        ok = false;
3069                        break;
3070                    }
3071                    mult.push(m);
3072                }
3073                let trivial_ok = ok
3074                    && rows.iter().zip(&mult).any(|(row, &m)| {
3075                        m == 1 && (0..d).all(|i| row[i] as u128 == valency[i] % p as u128)
3076                    });
3077                if ok && trivial_ok && mult.iter().sum::<u128>() == n {
3078                    mult.sort_unstable();
3079                    return Some(mult);
3080                }
3081            }
3082        }
3083        p += 1;
3084    }
3085    None
3086}
3087
3088/// **3-dimensional Weisfeiler–Leman (3-WL)** of a formula's variables — color refinement on *ordered
3089/// triples*. A triple `(i,j,k)` is initialized by the 2-WL colors of its three pairs
3090/// `(pc[i][j], pc[i][k], pc[j][k])`, then each round recolored by `(old color, sorted multiset over all w of
3091/// (color(w,j,k), color(i,w,k), color(i,j,w)))` to a fixpoint. Returns the `n×n×n` color tensor.
3092///
3093/// Strictly stronger than 2-WL (it distinguishes graphs with identical 2-WL colorings — e.g. the rook's
3094/// graph from the Shrikhande graph) and a SOUND over-approximation of the **3-orbits** (orbits on ordered
3095/// triples): every automorphism preserves the coloring, so `3-orbit(i,j,k) ⊆ triplecell(i,j,k)`.
3096/// `O(rounds · n⁴)`, so for small `n` only.
3097pub fn three_wl_colors(num_vars: usize, clauses: &[Vec<Lit>]) -> Vec<Vec<Vec<usize>>> {
3098    let n = num_vars;
3099    let pc = two_wl_pair_colors(n, clauses);
3100    let at = |i: usize, j: usize, k: usize| (i * n + j) * n + k;
3101    let init: Vec<(usize, usize, usize)> = (0..n)
3102        .flat_map(|i| (0..n).flat_map(move |j| (0..n).map(move |k| (i, j, k))))
3103        .map(|(i, j, k)| (pc[i][j], pc[i][k], pc[j][k]))
3104        .collect();
3105    let mut color = rank_signatures(&init);
3106    loop {
3107        let mut sig: Vec<(usize, Vec<(usize, usize, usize)>)> = Vec::with_capacity(n * n * n);
3108        for i in 0..n {
3109            for j in 0..n {
3110                for k in 0..n {
3111                    let mut nbr: Vec<(usize, usize, usize)> = (0..n)
3112                        .map(|w| (color[at(w, j, k)], color[at(i, w, k)], color[at(i, j, w)]))
3113                        .collect();
3114                    nbr.sort_unstable();
3115                    sig.push((color[at(i, j, k)], nbr));
3116                }
3117            }
3118        }
3119        let next = rank_signatures(&sig);
3120        if next == color {
3121            break;
3122        }
3123        color = next;
3124    }
3125    (0..n)
3126        .map(|i| {
3127            (0..n)
3128                .map(|j| (0..n).map(|k| color[at(i, j, k)]).collect())
3129                .collect()
3130        })
3131        .collect()
3132}
3133
3134/// The label-independent **3-WL fingerprint**: the sorted multiset of triple-color class sizes. Separates
3135/// strongly-regular graphs that share every 2-WL invariant (the rook's vs Shrikhande graph).
3136pub fn three_wl_fingerprint(num_vars: usize, clauses: &[Vec<Lit>]) -> Vec<usize> {
3137    let c = three_wl_colors(num_vars, clauses);
3138    let max = c
3139        .iter()
3140        .flatten()
3141        .flatten()
3142        .copied()
3143        .max()
3144        .map_or(0, |m| m + 1);
3145    let mut sizes = vec![0usize; max];
3146    for &col in c.iter().flatten().flatten() {
3147        sizes[col] += 1;
3148    }
3149    sizes.sort_unstable();
3150    sizes
3151}
3152
3153/// The canonical certificate of a formula under a *discrete* variable coloring (a labeling): the clause set
3154/// rewritten with each variable replaced by its dense label, every clause sorted, and the clauses sorted —
3155/// an exact representation of the formula as seen through that labeling.
3156fn formula_certificate(clauses: &[Vec<Lit>], coloring: &[usize]) -> Vec<Vec<(usize, bool)>> {
3157    let label = rank_signatures(coloring); // discrete coloring ⇒ a bijection onto 0..n-1
3158    let mut cls: Vec<Vec<(usize, bool)>> = clauses
3159        .iter()
3160        .map(|c| {
3161            let mut lits: Vec<(usize, bool)> = c
3162                .iter()
3163                .map(|l| (label[l.var() as usize], l.is_positive()))
3164                .collect();
3165            lits.sort_unstable();
3166            lits
3167        })
3168        .collect();
3169    cls.sort_unstable();
3170    cls
3171}
3172
3173/// The individualization–refinement search: refine the coloring; if discrete, return its certificate; else
3174/// individualize each vertex of the first non-singleton cell in turn, recurse, and keep the lexicographically
3175/// maximal leaf certificate. `None` if the node budget is exceeded (so the canonical form is not certified).
3176fn ir_canonical(
3177    num_vars: usize,
3178    clauses: &[Vec<Lit>],
3179    colors: &[usize],
3180    nodes: &mut usize,
3181    cap: usize,
3182) -> Option<Vec<Vec<(usize, bool)>>> {
3183    *nodes += 1;
3184    if *nodes > cap {
3185        return None;
3186    }
3187    let refined = equitable_refine(num_vars, clauses, colors);
3188    let d = refined.iter().copied().max().map_or(0, |m| m + 1);
3189    let mut members: Vec<Vec<usize>> = vec![Vec::new(); d];
3190    for (v, &c) in refined.iter().enumerate() {
3191        members[c].push(v);
3192    }
3193    match (0..d).find(|&c| members[c].len() > 1) {
3194        None => Some(formula_certificate(clauses, &refined)), // discrete ⇒ a leaf
3195        Some(c) => {
3196            let mut best: Option<Vec<Vec<(usize, bool)>>> = None;
3197            for &v in &members[c] {
3198                let mut nc = refined.clone();
3199                nc[v] = d; // individualize v: give it a fresh, unique color
3200                let leaf = ir_canonical(num_vars, clauses, &nc, nodes, cap)?;
3201                if best.as_ref().map_or(true, |b| leaf > *b) {
3202                    best = Some(leaf);
3203                }
3204            }
3205            best
3206        }
3207    }
3208}
3209
3210/// The **canonical form** of a formula's variable structure, computed by individualization–refinement (the
3211/// algorithm behind nauty/saucy/bliss). It is an *isomorphism invariant*: two formulas equal up to a
3212/// variable permutation that preserves the clause structure have the **same** canonical form, and — since
3213/// I-R is complete — two that are not get **different** canonical forms (so it decides isomorphism exactly,
3214/// unlike Weisfeiler–Leman). Built on [`color_refinement`] as its refinement step. `None` if the search
3215/// exceeds its node budget (gate to moderate `num_vars`).
3216pub fn canonical_form(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Vec<Vec<(usize, bool)>>> {
3217    let mut nodes = 0;
3218    ir_canonical(
3219        num_vars,
3220        clauses,
3221        &vec![0usize; num_vars],
3222        &mut nodes,
3223        200_000,
3224    )
3225}
3226
3227/// Whether two formulas over the same variables are **isomorphic** — equal up to a variable permutation
3228/// preserving the (signed) clause structure — by comparing their canonical forms. `None` if either canonical
3229/// form exceeds the search budget.
3230pub fn formulas_isomorphic(num_vars: usize, f: &[Vec<Lit>], g: &[Vec<Lit>]) -> Option<bool> {
3231    Some(canonical_form(num_vars, f)? == canonical_form(num_vars, g)?)
3232}
3233
3234/// Is `g` a genuine symmetry of `clauses` that may be trusted for breaking? A well-formed permutation that
3235/// either preserves the clause set (syntactic) or whose image is logically entailed, `F ⊨ g(F)` — which for
3236/// a finite-order permutation means `F ≡ g(F)` (semantic). A malformed or non-symmetric declaration is
3237/// rejected, so a wrong declaration can never corrupt the result.
3238fn is_declared_symmetry(num_vars: usize, clauses: &[Vec<Lit>], g: &[usize]) -> bool {
3239    if g.len() != num_vars {
3240        return false;
3241    }
3242    let mut seen = vec![false; num_vars];
3243    for &x in g {
3244        if x >= num_vars || seen[x] {
3245            return false; // not a permutation
3246        }
3247        seen[x] = true;
3248    }
3249    let clause_set: HashSet<Vec<(u32, bool)>> = clauses.iter().map(|c| canon_clause(c)).collect();
3250    let syntactic = clauses
3251        .iter()
3252        .all(|c| clause_set.contains(&canon_clause(&apply_perm_to_clause(c, g))));
3253    syntactic
3254        || clauses.iter().all(|c| {
3255            let gc = apply_perm_to_clause(c, g);
3256            clause_set.contains(&canon_clause(&gc)) || clause_is_implied(num_vars, clauses, &gc)
3257        })
3258}
3259
3260/// **The full arsenal with caller-DECLARED symmetry.** The modeler often knows symmetries the automatic
3261/// detector cannot afford to find (geometric, semantic, or simply large). This entry point accepts declared
3262/// variable-permutation generators, **verifies** each is a genuine symmetry (`is_declared_symmetry` —
3263/// never trusting a declaration blindly, so an incorrect one is silently dropped), unions the survivors with
3264/// the auto-detected symmetry, and breaks the combined group with the lex-leader (complete by enumeration
3265/// when the group is small, partial over the generators otherwise). Sound: only verified, model-set-
3266/// preserving permutations enter the break; a SAT model is re-checked, and on any anomaly it falls back to
3267/// the authoritative [`solve_comprehensive`]. With no declared and no detected symmetry it simply *is*
3268/// [`solve_comprehensive`].
3269pub fn solve_with_declared_symmetry(
3270    num_vars: usize,
3271    clauses: &[Vec<Lit>],
3272    declared: &[crate::permgroup::Perm],
3273) -> Solved {
3274    let mut gens =
3275        crate::sym_break::variable_automorphism_generators(num_vars, clauses).unwrap_or_default();
3276    for g in declared {
3277        if is_declared_symmetry(num_vars, clauses, g) {
3278            gens.push(g.clone());
3279        }
3280    }
3281    if gens.is_empty() {
3282        return solve_comprehensive(num_vars, clauses);
3283    }
3284    let bsgs = crate::permgroup::schreier_sims(num_vars, &gens);
3285    let to_litsym =
3286        |p: &[usize]| -> Vec<Lit> { (0..num_vars).map(|v| Lit::pos(p[v] as u32)).collect() };
3287    let group: Vec<Vec<Lit>> = match bsgs.elements(50_000) {
3288        Some(elts) => elts.iter().map(|p| to_litsym(p)).collect(),
3289        None => gens.iter().map(|p| to_litsym(p)).collect(),
3290    };
3291    let (sbp, total) = crate::sym_break::lex_leader_sbp_lit(num_vars, &group);
3292    let mut solver = Solver::new(total);
3293    for c in clauses {
3294        solver.add_clause(c.clone());
3295    }
3296    for c in &sbp {
3297        solver.add_clause(c.clone());
3298    }
3299    match solver.solve() {
3300        SolveResult::Sat(model) => {
3301            let projected: Vec<bool> = model[..num_vars].to_vec();
3302            if clauses.iter().all(|c| {
3303                c.iter()
3304                    .any(|l| projected[l.var() as usize] == l.is_positive())
3305            }) {
3306                Solved {
3307                    answer: Answer::Sat(projected),
3308                    via: Route::DeclaredSymmetry,
3309                    proof: Vec::new(),
3310                    conflicts: solver.conflicts(),
3311                }
3312            } else {
3313                solve_comprehensive(num_vars, clauses) // re-check failed ⟹ authoritative fallback
3314            }
3315        }
3316        SolveResult::Unsat => Solved {
3317            answer: Answer::Unsat,
3318            via: Route::DeclaredSymmetry,
3319            proof: Vec::new(),
3320            conflicts: solver.conflicts(),
3321        },
3322    }
3323}
3324
3325/// The solution set described **up to symmetry**: one representative per orbit, plus the exact total.
3326#[derive(Clone, Debug, PartialEq, Eq)]
3327pub struct SymmetricCount {
3328    /// One satisfying assignment per orbit of the model set under the variable-symmetry group — the
3329    /// essentially-distinct solutions.
3330    pub representatives: Vec<Vec<bool>>,
3331    /// The EXACT number of models (over the variables that occur), recovered as the sum of orbit sizes —
3332    /// so a `2^Θ(n)` model count is obtained by enumerating only the orbits.
3333    pub total_models: u128,
3334    /// `false` if the representative cap was reached before the model set was exhausted.
3335    pub exhaustive: bool,
3336}
3337
3338/// The orbit of an assignment under the variable-symmetry generators, as the distinct assignments reached
3339/// by the group (deduplicated on the occurring variables — free variables are immaterial to a model).
3340fn assignment_orbit(
3341    num_vars: usize,
3342    m: &[bool],
3343    gens: &[crate::permgroup::Perm],
3344    occurs: &[usize],
3345) -> Vec<Vec<bool>> {
3346    let proj = |a: &[bool]| -> Vec<bool> { occurs.iter().map(|&v| a[v]).collect() };
3347    let mut seen: HashSet<Vec<bool>> = HashSet::from([proj(m)]);
3348    let mut out = vec![m.to_vec()];
3349    let mut i = 0;
3350    while i < out.len() {
3351        let cur = out[i].clone();
3352        i += 1;
3353        for g in gens {
3354            let mut pm = vec![false; num_vars];
3355            for v in 0..num_vars {
3356                pm[g[v]] = cur[v];
3357            }
3358            if seen.insert(proj(&pm)) {
3359                out.push(pm);
3360            }
3361        }
3362    }
3363    out
3364}
3365
3366/// **Enumerate the solution set up to symmetry, and count it exactly.** Find a model (via the full
3367/// arsenal), record it as an orbit representative, then BLOCK its entire symmetry orbit and repeat until
3368/// unsatisfiable. Because every orbit is removed in one step, the representatives are the essentially-
3369/// distinct solutions and the exact model count is the sum of the orbit sizes — so an instance with
3370/// `2^Θ(n)` models is counted by enumerating only its (far fewer) orbits. Sound: each representative is a
3371/// re-checked model, each orbit a genuine set of models (the generators are automorphisms), so the orbits
3372/// partition the model set. The representative count agrees with Burnside
3373/// ([`crate::sym_break::count_models_modulo_symmetry`]) — two independent routes to the orbit count.
3374pub fn models_up_to_symmetry(num_vars: usize, clauses: &[Vec<Lit>], cap: usize) -> SymmetricCount {
3375    let mut appears = vec![false; num_vars];
3376    for c in clauses {
3377        for l in c {
3378            appears[l.var() as usize] = true;
3379        }
3380    }
3381    let occurs: Vec<usize> = (0..num_vars).filter(|&v| appears[v]).collect();
3382    let gens =
3383        crate::sym_break::variable_automorphism_generators(num_vars, clauses).unwrap_or_default();
3384
3385    let mut working = clauses.to_vec();
3386    let mut representatives: Vec<Vec<bool>> = Vec::new();
3387    let mut total_models: u128 = 0;
3388    let mut exhaustive = true;
3389    loop {
3390        if representatives.len() >= cap {
3391            exhaustive = false;
3392            break;
3393        }
3394        match solve_comprehensive(num_vars, &working).answer {
3395            Answer::Unsat => break,
3396            Answer::Sat(m) => {
3397                let orbit = assignment_orbit(num_vars, &m, &gens, &occurs);
3398                total_models = total_models.saturating_add(orbit.len() as u128);
3399                representatives.push(m);
3400                for a in &orbit {
3401                    // Block this assignment on the occurring variables (free variables are immaterial).
3402                    working.push(occurs.iter().map(|&v| Lit::new(v as u32, !a[v])).collect());
3403                }
3404            }
3405        }
3406    }
3407    SymmetricCount {
3408        representatives,
3409        total_models,
3410        exhaustive,
3411    }
3412}
3413
3414/// The structural profile of a formula's **variable-symmetry group** — `|Aut|`, the orbit/rank/transitivity
3415/// ladder, primitivity, and block structure. The data a surfacing layer (e.g. a Studio panel) needs to
3416/// explain *why* an instance is symmetric.
3417#[derive(Clone, Debug, PartialEq, Eq)]
3418pub struct SymmetryProfile {
3419    /// `|Aut|` of the phase-free variable-symmetry group (`1` when there is no symmetry).
3420    pub order: u128,
3421    /// Number of detected generators.
3422    pub generators: usize,
3423    /// Variable orbits (points moved together).
3424    pub num_orbits: usize,
3425    /// Rank — orbits on ordered pairs (`2` iff 2-transitive); `0` when not computed (group too large).
3426    pub rank: usize,
3427    /// Transitivity degree, capped (`1` = transitive, `2` = 2-transitive, …).
3428    pub transitivity: usize,
3429    /// Whether the (transitive) group is primitive.
3430    pub primitive: bool,
3431    /// The number of minimal blocks when the group is transitive and imprimitive, else `None`.
3432    pub blocks: Option<usize>,
3433    /// Whether the group is abelian.
3434    pub abelian: bool,
3435    /// Whether the group is solvable (its derived series reaches the trivial group); `None` when not
3436    /// computed (group too large for the derived-series walk).
3437    pub solvable: Option<bool>,
3438    /// Whether the group is nilpotent (its lower central series reaches the trivial group); strictly
3439    /// stronger than solvable. `None` when not computed.
3440    pub nilpotent: Option<bool>,
3441    /// Derived length (solvability class) — the depth of the derived series; `None` if unsolvable / not
3442    /// computed.
3443    pub derived_length: Option<usize>,
3444    /// Nilpotency class — the depth of the lower central series; `None` if not nilpotent / not computed.
3445    pub nilpotency_class: Option<usize>,
3446    /// Order of the derived (commutator) subgroup `[G, G]`; `0` when not computed.
3447    pub derived_order: u128,
3448    /// Number of conjugacy classes (= number of irreducible representations); `None` when the group is too
3449    /// large to enumerate.
3450    pub conjugacy_classes: Option<usize>,
3451    /// Order of the centre `Z(G)`; `None` when too large to enumerate.
3452    pub center_order: Option<u128>,
3453    /// The exponent — lcm of element orders (smallest `e` with `gᵉ = id` for all `g`); `None` when too
3454    /// large to enumerate.
3455    pub exponent: Option<u128>,
3456    /// The number of distinct `{0,1}` assignments to the variables up to symmetry (Pólya with 2 colours) —
3457    /// the symmetry-reduced size of the search space; `None` when too large to enumerate.
3458    pub assignment_orbits: Option<u128>,
3459    /// The abelianisation `G/[G,G]` as `(order, exponent)` — the largest abelian quotient; `None` when too
3460    /// large to enumerate.
3461    pub abelianization: Option<(u128, u128)>,
3462    /// The number of subgroups (size of the subgroup lattice); `None` for larger groups (the lattice walk
3463    /// is gated more tightly than the other invariants).
3464    pub subgroups: Option<usize>,
3465    /// Whether the group is simple (non-trivial, no normal subgroup but itself and `{id}`); `None` when too
3466    /// large to enumerate.
3467    pub simple: Option<bool>,
3468    /// The composition factors (Jordan–Hölder) as the sorted multiset of their orders; their product is
3469    /// `|G|`. `None` when the lattice walk is out of range.
3470    pub composition_factors: Option<Vec<u128>>,
3471    /// The Sylow structure as `(p, n_p)` pairs — the number of Sylow `p`-subgroups per prime; `None` when
3472    /// the lattice walk is out of range.
3473    pub sylow: Option<Vec<(u128, usize)>>,
3474    /// The number of real conjugacy classes (= number of real irreducible characters); `None` when too
3475    /// large to enumerate.
3476    pub real_classes: Option<usize>,
3477    /// The number of **rational** conjugacy classes (= number of rational-valued irreducible characters) —
3478    /// the singleton Galois orbits. Strictly refines [`Self::real_classes`] (`rational ≤ real`); they differ
3479    /// exactly when a character is real but irrational. `None` when too large to enumerate.
3480    pub rational_classes: Option<usize>,
3481    /// The irreducible-representation degrees `χ_s(1)` (sorted, `Σ dᵢ² = |G|`) from the Burnside–Dixon
3482    /// character table — the complete representation-theoretic fingerprint of the symmetry; `None` when the
3483    /// character table is out of range.
3484    pub irreducible_degrees: Option<Vec<u128>>,
3485    /// The Frobenius–Schur indicators (one per irreducible, aligned with the character table): `+1` real,
3486    /// `0` complex, `−1` quaternionic. Refines [`Self::real_classes`] and separates groups with identical
3487    /// character tables (`D₄` vs `Q₈`). `None` when the character table is out of range.
3488    pub frobenius_schur: Option<Vec<i8>>,
3489    /// The isotypic decomposition of the variable-permutation representation: the multiplicity `m_s` of each
3490    /// irreducible in `π = Σ_s m_s χ_s` (aligned with the character table). Bridges the action and the linear
3491    /// theory — `m_trivial = num_orbits`, `Σ m_s² = rank`, `Σ m_s·d_s = num_vars`. `None` when out of range.
3492    pub isotypic_multiplicities: Option<Vec<u128>>,
3493    /// The order of `Aut(G)` — the automorphism group of the symmetry group itself. The intrinsic symmetry of
3494    /// `G` as an abstract group. `None` when out of range. Separates groups indistinguishable by character
3495    /// table / Frobenius–Schur / rationality (e.g. `|Aut(D₄)|=8` vs `|Aut(Q₈)|=24`).
3496    pub automorphism_order: Option<u128>,
3497    /// The order of `Out(G) = Aut(G)/Inn(G)` — the outer automorphisms (those not realised by conjugation).
3498    /// `None` when out of range.
3499    pub outer_automorphism_order: Option<u128>,
3500    /// The **coherent (association-scheme) rank** — the number of relations in the coherent configuration
3501    /// that 2-WL stabilizes to (`= two_wl_pair_cells`), the combinatorial analog of the orbital `rank`. It is
3502    /// `≤ rank` (2-WL can only be coarser than the true orbitals), so a value below `rank` witnesses that the
3503    /// polynomial pre-filter cannot resolve the full pair structure. Clause-derived: `Some` only from
3504    /// [`symmetry_structure`] (`None` for the pseudo-Boolean coefficient profile, which has no clauses).
3505    pub coherent_rank: Option<usize>,
3506}
3507
3508/// Compute the [`SymmetryProfile`] of `clauses` — detect the variable-symmetry generators and read off the
3509/// whole structural ladder (order via Schreier–Sims, orbits, orbitals/rank, transitivity, primitivity,
3510/// blocks). The rank and transitivity rungs are gated to moderate sizes (their tuple spaces grow with the
3511/// degree); `0` signals "not computed" there.
3512pub fn symmetry_structure(num_vars: usize, clauses: &[Vec<Lit>]) -> SymmetryProfile {
3513    let gens =
3514        crate::sym_break::variable_automorphism_generators(num_vars, clauses).unwrap_or_default();
3515    let mut profile = profile_of_generators(num_vars, &gens);
3516    // The coherent (association-scheme) rank is clause-derived — wire it in here (the group profile alone
3517    // cannot see it). It refines the orbital rank: coherent_rank ≤ rank.
3518    profile.coherent_rank = Some(
3519        coherent_rank(num_vars, clauses).unwrap_or_else(|| two_wl_pair_cells(num_vars, clauses)),
3520    );
3521    profile
3522}
3523
3524/// The structural profile of the group generated by `gens` over `num_vars` points — the shared core behind
3525/// [`symmetry_structure`] (CNF variable symmetry) and [`pb_symmetry_profile`] (pseudo-Boolean coefficient
3526/// symmetry).
3527fn profile_of_generators(num_vars: usize, gens: &[crate::permgroup::Perm]) -> SymmetryProfile {
3528    if gens.is_empty() {
3529        return SymmetryProfile {
3530            order: 1,
3531            generators: 0,
3532            num_orbits: num_vars,
3533            rank: 0,
3534            transitivity: 0,
3535            primitive: false,
3536            blocks: None,
3537            abelian: true, // the trivial group is abelian
3538            solvable: Some(true),
3539            nilpotent: Some(true),
3540            derived_length: Some(0),
3541            nilpotency_class: Some(0),
3542            derived_order: 1,
3543            conjugacy_classes: Some(1),
3544            center_order: Some(1),
3545            exponent: Some(1),
3546            assignment_orbits: Some(1u128 << num_vars.min(127)),
3547            abelianization: Some((1, 1)),
3548            subgroups: Some(1),
3549            simple: Some(false), // the trivial group is not simple
3550            composition_factors: Some(Vec::new()),
3551            sylow: Some(Vec::new()),
3552            irreducible_degrees: Some(vec![1]), // the trivial group has one trivial irreducible
3553            frobenius_schur: Some(vec![1]),     // its trivial character is real
3554            // The permutation rep of the trivial group is `num_vars` copies of the trivial irreducible.
3555            isotypic_multiplicities: Some(vec![num_vars as u128]),
3556            real_classes: Some(1),
3557            rational_classes: Some(1), // the trivial character is rational
3558            automorphism_order: Some(1), // the trivial group has only the identity automorphism
3559            outer_automorphism_order: Some(1),
3560            coherent_rank: None, // scheme rank is clause-derived; set by symmetry_structure
3561        };
3562    }
3563    let gens = gens.to_vec();
3564    let order = crate::permgroup::schreier_sims(num_vars, &gens).order();
3565    let num_orbits = crate::permgroup::orbits(num_vars, &gens).len();
3566    let rank = if num_vars <= 48 {
3567        crate::permgroup::rank(num_vars, &gens)
3568    } else {
3569        0
3570    };
3571    let transitivity = if num_vars <= 24 {
3572        crate::permgroup::transitivity_degree(num_vars, &gens, 3)
3573    } else {
3574        0
3575    };
3576    let primitive = crate::permgroup::is_primitive(num_vars, &gens);
3577    let blocks = crate::permgroup::minimal_block_system(num_vars, &gens).map(|b| b.len());
3578    let abelian = crate::permgroup::is_abelian(num_vars, &gens);
3579    // The series walks are heavier (repeated Schreier–Sims); gate them to moderate sizes. Compute the
3580    // depths once and read the booleans off them.
3581    let (solvable, nilpotent, derived_length, nilpotency_class, derived_order) = if num_vars <= 24 {
3582        let dl = crate::permgroup::derived_length(num_vars, &gens);
3583        let nc = crate::permgroup::nilpotency_class(num_vars, &gens);
3584        let d = crate::permgroup::derived_subgroup(num_vars, &gens);
3585        (
3586            Some(dl.is_some()),
3587            Some(nc.is_some()),
3588            dl,
3589            nc,
3590            crate::permgroup::schreier_sims(num_vars, &d).order(),
3591        )
3592    } else {
3593        (None, None, None, None, 0)
3594    };
3595    // Conjugacy classes (⇒ #irreps) and the centre need the group enumerated; cap the order.
3596    const ENUM_CAP: usize = 4096;
3597    let classes = crate::permgroup::conjugacy_classes(num_vars, &gens, ENUM_CAP);
3598    let conjugacy_classes = classes.as_ref().map(|c| c.len());
3599    let center_order = classes.map(|c| c.iter().filter(|cls| cls.len() == 1).count() as u128);
3600    let exponent = crate::permgroup::exponent(num_vars, &gens, ENUM_CAP);
3601    let assignment_orbits = crate::permgroup::polya_count(num_vars, &gens, 2, ENUM_CAP);
3602    let abelianization = crate::permgroup::abelianization(num_vars, &gens, ENUM_CAP);
3603    // The subgroup-lattice walk is heavier (exponential worst case) — gate it to small groups.
3604    let subgroups = crate::permgroup::subgroup_count(num_vars, &gens, 256);
3605    let simple = crate::permgroup::is_simple(num_vars, &gens, ENUM_CAP);
3606    // Composition factors share the subgroup-lattice walk — gate to small groups.
3607    let composition_factors = crate::permgroup::composition_factor_orders(num_vars, &gens, 256);
3608    let sylow = crate::permgroup::sylow_counts(num_vars, &gens, 256);
3609    let real_classes = crate::permgroup::real_class_count(num_vars, &gens, ENUM_CAP);
3610    let rational_classes = crate::permgroup::rational_class_count(num_vars, &gens, ENUM_CAP);
3611    // The Burnside–Dixon character table is computed once and both the degrees and the Frobenius–Schur
3612    // indicators are read off it.
3613    let ctable = crate::permgroup::character_table(num_vars, &gens, ENUM_CAP);
3614    let irreducible_degrees = ctable.as_ref().map(|t| t.degrees.clone());
3615    let frobenius_schur = ctable
3616        .as_ref()
3617        .and_then(crate::permgroup::frobenius_schur_from_table);
3618    let isotypic_multiplicities = ctable
3619        .as_ref()
3620        .and_then(|t| crate::permgroup::isotypic_from_table(num_vars, &gens, t));
3621    // The automorphism group of the symmetry group itself (gated tighter — the search is heavier).
3622    let automorphism_order = crate::permgroup::automorphism_group_order(num_vars, &gens, 256);
3623    let outer_automorphism_order = match (automorphism_order, center_order) {
3624        (Some(a), Some(c)) if c > 0 => Some(a / (order / c)), // |Out| = |Aut| / |Inn|, |Inn| = |G|/|Z|
3625        _ => None,
3626    };
3627    SymmetryProfile {
3628        order,
3629        generators: gens.len(),
3630        num_orbits,
3631        rank,
3632        transitivity,
3633        primitive,
3634        blocks,
3635        abelian,
3636        solvable,
3637        nilpotent,
3638        derived_length,
3639        nilpotency_class,
3640        derived_order,
3641        conjugacy_classes,
3642        center_order,
3643        exponent,
3644        assignment_orbits,
3645        abelianization,
3646        subgroups,
3647        simple,
3648        composition_factors,
3649        sylow,
3650        real_classes,
3651        rational_classes,
3652        irreducible_degrees,
3653        frobenius_schur,
3654        isotypic_multiplicities,
3655        automorphism_order,
3656        outer_automorphism_order,
3657        coherent_rank: None, // clause-derived; filled in by symmetry_structure
3658    }
3659}
3660
3661/// The [`SymmetryProfile`] of a pseudo-Boolean system's **coefficient-symmetry** group — variables that
3662/// share a coefficient profile across all constraints ([`crate::pseudo_boolean::coeff_symmetry_generators`])
3663/// — read through the same structural ladder as [`symmetry_structure`]. The symmetry of *weighted*
3664/// constraints, surfaced exactly like the clause-structure symmetry.
3665pub fn pb_symmetry_profile(
3666    num_vars: usize,
3667    constraints: &[crate::pseudo_boolean::PbConstraint],
3668) -> SymmetryProfile {
3669    let gens = crate::pseudo_boolean::coeff_symmetry_generators(num_vars, constraints);
3670    profile_of_generators(num_vars, &gens)
3671}
3672
3673/// The **class-algebra structure constants** of a formula's variable-symmetry group — `a[i][j][k]`, the
3674/// multiplication coefficients of the conjugacy classes (`Cᵢ·Cⱼ = Σₖ a[i][j][k]·Cₖ`), the foundation of the
3675/// character table. `None` when the group is too large to enumerate.
3676pub fn class_algebra_constants(
3677    num_vars: usize,
3678    clauses: &[Vec<Lit>],
3679) -> Option<Vec<Vec<Vec<u128>>>> {
3680    let gens =
3681        crate::sym_break::variable_automorphism_generators(num_vars, clauses).unwrap_or_default();
3682    crate::permgroup::class_multiplication_coefficients(num_vars, &gens, 4096)
3683}
3684
3685/// The **character table** of a formula's variable-symmetry group, computed exactly over a finite field by
3686/// the Burnside–Dixon algorithm (degrees + `GF(p)`-valued irreducible characters). The deepest structural
3687/// view of the symmetry — `None` when the group is too large for the finite-field diagonalisation.
3688pub fn character_table(
3689    num_vars: usize,
3690    clauses: &[Vec<Lit>],
3691) -> Option<crate::permgroup::CharacterTable> {
3692    let gens =
3693        crate::sym_break::variable_automorphism_generators(num_vars, clauses).unwrap_or_default();
3694    crate::permgroup::character_table(num_vars, &gens, 4096)
3695}
3696
3697/// The **Frobenius–Schur indicators** of a formula's variable-symmetry group — `+1`/`0`/`−1` per
3698/// irreducible (real/complex/quaternionic), the finest representation-theoretic refinement of the symmetry
3699/// (it separates groups even when the character table cannot). `None` when out of range.
3700pub fn frobenius_schur_indicators(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Vec<i8>> {
3701    let gens =
3702        crate::sym_break::variable_automorphism_generators(num_vars, clauses).unwrap_or_default();
3703    crate::permgroup::frobenius_schur_indicators(num_vars, &gens, 4096)
3704}
3705
3706/// The **permutation character** `π(g) = #fixed variables of g` of a formula's variable-symmetry action,
3707/// valued per conjugacy class. The character of the representation the symmetry group carries on the
3708/// variables themselves. `None` when the group is too large to enumerate.
3709pub fn permutation_character(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Vec<u128>> {
3710    let gens =
3711        crate::sym_break::variable_automorphism_generators(num_vars, clauses).unwrap_or_default();
3712    crate::permgroup::permutation_character(num_vars, &gens, 4096)
3713}
3714
3715/// The **isotypic decomposition** of a formula's variable-permutation representation — the multiplicity of
3716/// each irreducible in `π = Σ_s m_s χ_s`. The representation-theoretic spectrum of the symmetry, tying the
3717/// character table back to the orbit/orbital structure of the action. `None` when out of range.
3718pub fn isotypic_multiplicities(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Vec<u128>> {
3719    let gens =
3720        crate::sym_break::variable_automorphism_generators(num_vars, clauses).unwrap_or_default();
3721    crate::permgroup::isotypic_multiplicities(num_vars, &gens, 4096)
3722}
3723
3724/// The **tensor (fusion) decomposition** of a formula's variable-symmetry irreducibles — `N[i][j][k]`, the
3725/// multiplicity of `χ_k` in `χ_i ⊗ χ_j`, the multiplication table of the representation ring `R(G)`. `None`
3726/// when the character table is out of range.
3727pub fn tensor_decomposition(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Vec<Vec<Vec<u128>>>> {
3728    let gens =
3729        crate::sym_break::variable_automorphism_generators(num_vars, clauses).unwrap_or_default();
3730    crate::permgroup::tensor_decomposition(num_vars, &gens, 4096)
3731}
3732
3733/// The **Galois orbits on conjugacy classes** of a formula's variable symmetry — classes fused by the
3734/// `(ℤ/e)*` action `C ↦ C^t` (algebraic conjugacy). The singletons are the rational classes. `None` when
3735/// out of range.
3736pub fn galois_class_orbits(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Vec<Vec<usize>>> {
3737    let gens =
3738        crate::sym_break::variable_automorphism_generators(num_vars, clauses).unwrap_or_default();
3739    crate::permgroup::galois_class_orbits(num_vars, &gens, 4096)
3740}
3741
3742/// The **table of marks** of a formula's variable-symmetry group — the Burnside-ring classification of its
3743/// `G`-sets (the permutation-representation analogue of [`character_table`]). Returns
3744/// `(subgroup_class_orders, marks)`. `None` when the subgroup lattice is out of range.
3745pub fn table_of_marks(
3746    num_vars: usize,
3747    clauses: &[Vec<Lit>],
3748) -> Option<(Vec<u128>, Vec<Vec<u128>>)> {
3749    let gens =
3750        crate::sym_break::variable_automorphism_generators(num_vars, clauses).unwrap_or_default();
3751    crate::permgroup::table_of_marks(num_vars, &gens, 256)
3752}
3753
3754/// The **Burnside ring** multiplication of a formula's variable-symmetry group — `N[a][b][l]`, the
3755/// decomposition of the product G-set `(G/H_a)×(G/H_b)` into transitive G-sets (the G-set analogue of the
3756/// character table's fusion ring). `None` when the subgroup lattice is out of range.
3757pub fn burnside_ring_product(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Vec<Vec<Vec<i128>>>> {
3758    let gens =
3759        crate::sym_break::variable_automorphism_generators(num_vars, clauses).unwrap_or_default();
3760    crate::permgroup::burnside_ring_product(num_vars, &gens, 256)
3761}
3762
3763/// The **Möbius number** `μ(1, G)` of the subgroup lattice of a formula's variable-symmetry group. `None`
3764/// when the subgroup lattice is out of range.
3765pub fn mobius_number(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<i128> {
3766    let gens =
3767        crate::sym_break::variable_automorphism_generators(num_vars, clauses).unwrap_or_default();
3768    crate::permgroup::mobius_number(num_vars, &gens, 256)
3769}
3770
3771/// The number of ordered `k`-tuples of symmetries that **generate** the whole variable-symmetry group `G`
3772/// (Hall's Eulerian function `e_k(G)`); `e_k(G)/|G|^k` is the probability `k` random symmetries generate it.
3773/// `None` when out of range.
3774pub fn generating_tuple_count(num_vars: usize, clauses: &[Vec<Lit>], k: u32) -> Option<i128> {
3775    let gens =
3776        crate::sym_break::variable_automorphism_generators(num_vars, clauses).unwrap_or_default();
3777    crate::permgroup::generating_tuple_count(num_vars, &gens, 256, k)
3778}
3779
3780/// The **permutation-character decomposition** of a formula's variable-symmetry group — the bridge between
3781/// its table of marks and its character table. `M[i][s]` is the multiplicity of irreducible `χ_s` in the
3782/// permutation representation on the cosets `G/H_i` (Frobenius reciprocity). Returns
3783/// `(subgroup_orders, irreducible_degrees, M)`. `None` when out of range.
3784pub fn permutation_character_decomposition(
3785    num_vars: usize,
3786    clauses: &[Vec<Lit>],
3787) -> Option<(Vec<u128>, Vec<u128>, Vec<Vec<u128>>)> {
3788    let gens =
3789        crate::sym_break::variable_automorphism_generators(num_vars, clauses).unwrap_or_default();
3790    crate::permgroup::permutation_character_decomposition(num_vars, &gens, 256)
3791}
3792
3793/// The order of `Aut(G)` for a formula's variable-symmetry group `G` — the automorphism group of the
3794/// symmetry itself. `None` when out of range.
3795pub fn automorphism_group_order(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<u128> {
3796    let gens =
3797        crate::sym_break::variable_automorphism_generators(num_vars, clauses).unwrap_or_default();
3798    crate::permgroup::automorphism_group_order(num_vars, &gens, 256)
3799}
3800
3801/// The **weight inventory** of a formula's variable symmetry: entry `w` is the number of essentially-
3802/// distinct (modulo symmetry) `{0,1}` assignments to the variables with exactly `w` ones — the weighted
3803/// Pólya refinement of [`SymmetryProfile::assignment_orbits`] (which is the sum). `None` when the group is
3804/// too large to enumerate.
3805pub fn assignment_weight_inventory(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Vec<u128>> {
3806    let gens =
3807        crate::sym_break::variable_automorphism_generators(num_vars, clauses).unwrap_or_default();
3808    crate::permgroup::pattern_inventory(num_vars, &gens, 4096)
3809}
3810
3811/// **Iterated symmetry breaking to a fixpoint** — the automated breaker. Repeatedly detect the formula's
3812/// variable symmetry and break each generator with one sound lex constraint — `x_v ≤ x_{g[v]}` at `g`'s
3813/// least moved point `v` (`v < g[v]`, and the lex-minimum of `g`'s orbit satisfies it, so it keeps ≥ 1
3814/// model per orbit, no auxiliary variables) — then **re-detect on the strengthened formula**, so symmetry
3815/// that earlier breaks expose is broken in its turn. It runs until a round adds no new constraint: the
3816/// symmetry "broken to conclusion." Sound: every clause breaks a genuine symmetry of the *current* formula,
3817/// so each round is equisatisfiability-preserving and the whole is equisatisfiable with the input. Returns
3818/// the original clauses plus the accumulated breaks; the residual variable-symmetry group has shrunk (to
3819/// trivial when single-bit breaks suffice). Solve the result with [`solve_comprehensive`].
3820pub fn break_all_symmetry(num_vars: usize, clauses: &[Vec<Lit>]) -> Vec<Vec<Lit>> {
3821    let key = |a: Lit, b: Lit| -> (u32, bool, u32, bool) {
3822        let (x, y) = ((a.var(), a.is_positive()), (b.var(), b.is_positive()));
3823        if x <= y {
3824            (x.0, x.1, y.0, y.1)
3825        } else {
3826            (y.0, y.1, x.0, x.1)
3827        }
3828    };
3829    let mut combined = clauses.to_vec();
3830    let mut seen: HashSet<(u32, bool, u32, bool)> = combined
3831        .iter()
3832        .filter(|c| c.len() == 2)
3833        .map(|c| key(c[0], c[1]))
3834        .collect();
3835    loop {
3836        let gens = crate::sym_break::variable_automorphism_generators(num_vars, &combined)
3837            .unwrap_or_default();
3838        if gens.is_empty() {
3839            break; // fixpoint: no symmetry remains
3840        }
3841        let bsgs = crate::permgroup::schreier_sims(num_vars, &gens);
3842        let mut added = false;
3843        // Phase 1 — COMPLETE break of fully-symmetric, independent orbits via sortedness. An orbit whose
3844        // every pure adjacent transposition lies in the group carries an independent Sₙ action, for which
3845        // `x_{o₀} ≤ x_{o₁} ≤ …` is the complete (one-per-orbit), aux-free, sound symmetry break.
3846        for orbit in crate::permgroup::orbits(num_vars, &gens) {
3847            if orbit.len() < 2 {
3848                continue;
3849            }
3850            let full = orbit.windows(2).all(|w| {
3851                let mut t: Vec<usize> = (0..num_vars).collect();
3852                t.swap(w[0], w[1]);
3853                bsgs.contains(&t)
3854            });
3855            if full {
3856                for w in orbit.windows(2) {
3857                    let (a, b) = (Lit::neg(w[0] as u32), Lit::pos(w[1] as u32)); // x_{o_i} ≤ x_{o_{i+1}}
3858                    if seen.insert(key(a, b)) {
3859                        combined.push(vec![a, b]);
3860                        added = true;
3861                    }
3862                }
3863            }
3864        }
3865        // Phase 2 — fallback single-bit break per generator, only when no full orbit was sorted this round.
3866        if !added {
3867            for g in &gens {
3868                let Some(v) = (0..num_vars).find(|&i| g[i] != i) else {
3869                    continue;
3870                };
3871                let (a, b) = (Lit::neg(v as u32), Lit::pos(g[v] as u32)); // x_v ≤ x_{g[v]}
3872                if seen.insert(key(a, b)) {
3873                    combined.push(vec![a, b]);
3874                    added = true;
3875                }
3876            }
3877        }
3878        if !added {
3879            break; // no new ordering ⇒ fixpoint (any residual symmetry is single-bit-irreducible)
3880        }
3881    }
3882    combined
3883}
3884
3885/// **Complete symmetry breaking** — the breaker driven all the way to a single representative per orbit.
3886/// Detect the full variable-symmetry group and add the COMPLETE lex-leader (one `a ≤_lex a∘g` per group
3887/// element, via the standard lex-chain auxiliaries), which admits **exactly one model per symmetry orbit**
3888/// when the group is enumerable. Returns the strengthened clauses and the new variable count (originals +
3889/// auxiliaries). Sound (equisatisfiable with the input); complete for groups up to the enumeration cap, and
3890/// a sound partial break (generators ∪ coset representatives) for larger ones. Unlike [`break_all_symmetry`]
3891/// (aux-free, complete only for fully-symmetric orbits), this leaves *no* residual orbit symmetry.
3892pub fn break_all_symmetry_complete(
3893    num_vars: usize,
3894    clauses: &[Vec<Lit>],
3895) -> (Vec<Vec<Lit>>, usize) {
3896    let gens =
3897        crate::sym_break::variable_automorphism_generators(num_vars, clauses).unwrap_or_default();
3898    if gens.is_empty() {
3899        return (clauses.to_vec(), num_vars);
3900    }
3901    let bsgs = crate::permgroup::schreier_sims(num_vars, &gens);
3902    let to_litsym =
3903        |p: &[usize]| -> Vec<Lit> { (0..num_vars).map(|v| Lit::pos(p[v] as u32)).collect() };
3904    let group: Vec<Vec<Lit>> = match bsgs.elements(50_000) {
3905        Some(elts) => elts.iter().map(|p| to_litsym(p)).collect(), // complete: one constraint per element
3906        None => {
3907            // Too large to enumerate — sound partial break over generators ∪ coset representatives.
3908            let mut g: Vec<Vec<Lit>> = gens.iter().map(|p| to_litsym(p)).collect();
3909            g.extend(bsgs.transversal_elements().iter().map(|p| to_litsym(p)));
3910            g
3911        }
3912    };
3913    let (sbp, total) = crate::sym_break::lex_leader_sbp_lit(num_vars, &group);
3914    let mut combined = clauses.to_vec();
3915    combined.extend(sbp);
3916    (combined, total)
3917}
3918
3919/// **Solve by breaking all symmetry first** — the breaker as a front-end. Run the aux-free recursive
3920/// breaker ([`break_all_symmetry`]) to collapse the symmetry to its fixpoint, then decide the reduced
3921/// formula with the full arsenal ([`solve_comprehensive`]). Equisatisfiable, so the verdict is the
3922/// original's, and any returned model satisfies the original clauses (a subset of the broken set) —
3923/// re-checked fail-closed. (Uses the aux-free reducer, not [`break_all_symmetry_complete`]: CDCL handles the
3924/// residual cheaply, and the complete lex-leader of a large group would be far more expensive than the
3925/// search it saves.)
3926pub fn solve_by_symmetry_breaking(num_vars: usize, clauses: &[Vec<Lit>]) -> Solved {
3927    let broken = break_all_symmetry(num_vars, clauses);
3928    let inner = solve_comprehensive(num_vars, &broken);
3929    match inner.answer {
3930        Answer::Sat(model) => {
3931            if clauses
3932                .iter()
3933                .all(|c| c.iter().any(|l| model[l.var() as usize] == l.is_positive()))
3934            {
3935                Solved {
3936                    answer: Answer::Sat(model),
3937                    via: inner.via,
3938                    proof: inner.proof,
3939                    conflicts: inner.conflicts,
3940                }
3941            } else {
3942                solve_comprehensive(num_vars, clauses) // re-check failed ⇒ authoritative fallback
3943            }
3944        }
3945        Answer::Unsat => Solved {
3946            answer: Answer::Unsat,
3947            via: inner.via,
3948            proof: inner.proof,
3949            conflicts: inner.conflicts,
3950        },
3951    }
3952}
3953
3954/// Decide an instance by lifting it onto `GF(p)`: recover the mod-`p` one-hot system from the clauses
3955/// ([`crate::modp::recover_from_cnf`]) and run the certified Gaussian engine. Returns `None` when the
3956/// formula is not a clean mod-`p` encoding, so the dispatcher falls through to its other routes. UNSAT is
3957/// sound by the equisatisfiable recovery (the linear refutation re-checks); a SAT model is translated
3958/// back to the Boolean variables and accepted only if it satisfies every original clause (fail-closed).
3959fn modp_route(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Solved> {
3960    use crate::modp::{self, ModpOutcome};
3961    let rec = modp::recover_from_cnf(num_vars, clauses)?;
3962
3963    // Translate a recovered ℤ/modulus assignment (value per one-hot group) back to the Boolean variables,
3964    // accepting it only if it satisfies every original clause (fail-closed — never trust the lift blindly).
3965    let build_model = |assign: &[u64]| -> Option<Vec<bool>> {
3966        let mut model = vec![false; num_vars];
3967        for (g, group) in rec.groups.iter().enumerate() {
3968            if let Some(&bit) = group.get(*assign.get(g).unwrap_or(&0) as usize) {
3969                if (bit as usize) < model.len() {
3970                    model[bit as usize] = true;
3971                }
3972            }
3973        }
3974        clauses
3975            .iter()
3976            .all(|c| {
3977                c.iter().any(|l| {
3978                    model.get(l.var() as usize).copied().unwrap_or(false) == l.is_positive()
3979                })
3980            })
3981            .then_some(model)
3982    };
3983
3984    if modp::is_prime(rec.modulus) {
3985        // Prime modulus: the proven field engine.
3986        match modp::solve(&rec.equations, rec.num_vars, rec.modulus) {
3987            ModpOutcome::Unsat(combo) => {
3988                debug_assert!(
3989                    modp::is_refutation(&rec.equations, rec.num_vars, rec.modulus, &combo),
3990                    "the recovered GF(p) refutation must re-check"
3991                );
3992                Some(Solved::unsat(Route::ModP))
3993            }
3994            ModpOutcome::Sat(assign) => Some(Solved {
3995                answer: Answer::Sat(build_model(&assign)?),
3996                via: Route::ModP,
3997                proof: Vec::new(),
3998                conflicts: 0,
3999            }),
4000        }
4001    } else {
4002        // Composite modulus: CRT over the prime-power components, the ℤ/m ring engine.
4003        use crate::modm::{self, ModmOutcome};
4004        match modm::solve(&rec.equations, rec.num_vars, rec.modulus)? {
4005            ModmOutcome::Unsat { modulus, combo } => {
4006                debug_assert!(
4007                    modm::is_refutation(&rec.equations, rec.num_vars, modulus, &combo),
4008                    "the recovered ℤ/m refutation must re-check"
4009                );
4010                Some(Solved::unsat(Route::ModM))
4011            }
4012            ModmOutcome::Sat(assign) => Some(Solved {
4013                answer: Answer::Sat(build_model(&assign)?),
4014                via: Route::ModM,
4015                proof: Vec::new(),
4016                conflicts: 0,
4017            }),
4018        }
4019    }
4020}
4021
4022/// **The clause-bundle pass.** Run every structure-mining contributor and union the *implied* clauses
4023/// (no-goods) they discover. Each contributor's soundness contract: every returned clause is implied
4024/// by the formula, so the union preserves the solution set — a sound, never-worse enrichment that lets
4025/// one method's discovered structure accelerate the others (and CDCL). Contributors that find nothing
4026/// are cheap, so this is safe to run before the fallback on any instance.
4027pub fn mine_clauses(num_vars: usize, clauses: &[Vec<Lit>]) -> Vec<Vec<Lit>> {
4028    let mut seen: HashSet<Vec<i64>> = clauses.iter().map(|c| canon(c)).collect();
4029    let mut pool = Vec::new();
4030    let mut add =
4031        |bundle: Vec<Vec<Lit>>, pool: &mut Vec<Vec<Lit>>, seen: &mut HashSet<Vec<i64>>| {
4032            for c in bundle {
4033                if seen.insert(canon(&c)) {
4034                    pool.push(c);
4035                }
4036            }
4037        };
4038    add(xor_gaussian_bundle(num_vars, clauses), &mut pool, &mut seen);
4039    add(
4040        failed_literal_bundle(num_vars, clauses),
4041        &mut pool,
4042        &mut seen,
4043    );
4044    pool
4045}
4046
4047/// Canonical clause key (sorted signed-var ids) for deduping against the formula and each other.
4048fn canon(c: &[Lit]) -> Vec<i64> {
4049    let mut k: Vec<i64> = c
4050        .iter()
4051        .map(|l| {
4052            if l.is_positive() {
4053                l.var() as i64 + 1
4054            } else {
4055                -(l.var() as i64 + 1)
4056            }
4057        })
4058        .collect();
4059    k.sort_unstable();
4060    k.dedup();
4061    k
4062}
4063
4064/// Max width of clauses the Gaussian bundle emits (tunable for experiments via `LOGOS_XOR_WIDTH`).
4065fn xor_width() -> usize {
4066    std::env::var("LOGOS_XOR_WIDTH")
4067        .ok()
4068        .and_then(|s| s.parse().ok())
4069        .unwrap_or(3)
4070}
4071
4072/// Contributor: the short clauses the GF(2) Gaussian reduction implies (units, binaries, …).
4073fn xor_gaussian_bundle(num_vars: usize, clauses: &[Vec<Lit>]) -> Vec<Vec<Lit>> {
4074    let eqs = extract_xor(num_vars, clauses);
4075    if eqs.len() < 2 {
4076        return Vec::new();
4077    }
4078    IncXor::new(num_vars, &eqs).derived_clauses(xor_width())
4079}
4080
4081/// Contributor: failed-literal probing — `v` whose assertion unit-propagates to a root conflict gives
4082/// the implied unit `¬v`. Catches RUP-implied units the gadget clauses hide. Budgeted: skipped on
4083/// very large instances where the O(vars·clauses) probe sweep would not pay off.
4084fn failed_literal_bundle(num_vars: usize, clauses: &[Vec<Lit>]) -> Vec<Vec<Lit>> {
4085    if num_vars > 5000 || clauses.len() > 50_000 {
4086        return Vec::new();
4087    }
4088    let mut out = Vec::new();
4089    for v in 0..num_vars {
4090        let neg = Lit::new(v as u32, false);
4091        let pos = Lit::new(v as u32, true);
4092        if crate::rup::is_rup(num_vars, clauses, std::slice::from_ref(&neg)) {
4093            out.push(vec![neg]);
4094        } else if crate::rup::is_rup(num_vars, clauses, std::slice::from_ref(&pos)) {
4095            out.push(vec![pos]);
4096        }
4097    }
4098    out
4099}
4100
4101/// View the CNF as 2-SAT — `Some` iff every clause has 1 or 2 literals (a unit `l` becomes `l ∨ l`).
4102fn as_two_sat(clauses: &[Vec<Lit>]) -> Option<Vec<(crate::twosat::Lit, crate::twosat::Lit)>> {
4103    let cvt = |l: &Lit| {
4104        if l.is_positive() {
4105            crate::twosat::Lit::pos(l.var() as usize)
4106        } else {
4107            crate::twosat::Lit::neg(l.var() as usize)
4108        }
4109    };
4110    let mut out = Vec::with_capacity(clauses.len());
4111    for c in clauses {
4112        match c.as_slice() {
4113            [a] => out.push((cvt(a), cvt(a))),
4114            [a, b] => out.push((cvt(a), cvt(b))),
4115            _ => return None,
4116        }
4117    }
4118    Some(out)
4119}
4120
4121/// View the CNF as Horn — `Some` iff every clause has at most one positive literal.
4122fn as_horn(clauses: &[Vec<Lit>]) -> Option<Vec<crate::hornsat::HornClause>> {
4123    let mut out = Vec::with_capacity(clauses.len());
4124    for c in clauses {
4125        if c.is_empty() {
4126            return None;
4127        }
4128        let pos: Vec<usize> = c
4129            .iter()
4130            .filter(|l| l.is_positive())
4131            .map(|l| l.var() as usize)
4132            .collect();
4133        let neg: Vec<usize> = c
4134            .iter()
4135            .filter(|l| !l.is_positive())
4136            .map(|l| l.var() as usize)
4137            .collect();
4138        match pos.len() {
4139            0 => out.push(crate::hornsat::HornClause::goal(neg)),
4140            1 if neg.is_empty() => out.push(crate::hornsat::HornClause::fact(pos[0])),
4141            1 => out.push(crate::hornsat::HornClause::rule(neg, pos[0])),
4142            _ => return None,
4143        }
4144    }
4145    Some(out)
4146}
4147
4148/// Build the conjunction-of-disjunctions [`ProofExpr`] the pigeonhole/cutting-plane/parity detectors
4149/// read (atoms named `v{index}`). `None` if any clause is empty (handled by the CDCL fallback).
4150fn cnf_to_expr(clauses: &[Vec<Lit>]) -> Option<ProofExpr> {
4151    let atom = |l: &Lit| {
4152        let a = ProofExpr::Atom(format!("v{}", l.var()));
4153        if l.is_positive() {
4154            a
4155        } else {
4156            ProofExpr::Not(Box::new(a))
4157        }
4158    };
4159    let mut clause_exprs = Vec::with_capacity(clauses.len());
4160    for c in clauses {
4161        if c.is_empty() {
4162            return None;
4163        }
4164        let atoms: Vec<ProofExpr> = c.iter().map(&atom).collect();
4165        clause_exprs.push(balanced(atoms, &|a, b| {
4166            ProofExpr::Or(Box::new(a), Box::new(b))
4167        })?);
4168    }
4169    // Balanced trees keep the And/Or spine depth ~log(n), so the recursive detector traversals do
4170    // not overflow the stack on competition-scale formulas (tens of thousands of clauses).
4171    balanced(clause_exprs, &|a, b| {
4172        ProofExpr::And(Box::new(a), Box::new(b))
4173    })
4174}
4175
4176/// Fold `items` into one expression with a balanced (log-depth) tree under `combine`.
4177fn balanced(
4178    mut items: Vec<ProofExpr>,
4179    combine: &dyn Fn(ProofExpr, ProofExpr) -> ProofExpr,
4180) -> Option<ProofExpr> {
4181    if items.is_empty() {
4182        return None;
4183    }
4184    while items.len() > 1 {
4185        let mut next = Vec::with_capacity(items.len().div_ceil(2));
4186        let mut it = items.into_iter();
4187        while let Some(a) = it.next() {
4188            match it.next() {
4189                Some(b) => next.push(combine(a, b)),
4190                None => next.push(a),
4191            }
4192        }
4193        items = next;
4194    }
4195    items.into_iter().next()
4196}
4197
4198/// Hybrid XOR-SAT: mine the GF(2) linear system for structure, hand it to CDCL.
4199///
4200/// Three contributions, all sound (the recovered equations are logical consequences of the formula):
4201/// (1) decide the linear system — an inconsistent subsystem refutes the whole formula; (2) inject the
4202/// short clauses Gaussian *implies* ([`IncXor::derived_clauses`] — units, binaries, …) that resolution
4203/// would not find, so CDCL inherits the strategy's discovered no-goods; (3) seed CDCL's phases with a
4204/// GF(2) witness so search starts on the solution manifold. CDCL remains the authoritative decider, so
4205/// adding implied clauses + a phase hint can only help. `None` when not XOR-heavy.
4206///
4207/// (The full incremental DPLL(XOR) engine — live Gaussian during search, [`crate::xor_engine::IncXor`]
4208/// — is built and proven correct against a brute-force + differential oracle, and is the decisive
4209/// lever for *UNSAT* parity. On *satisfiable* parity-learning it needs a watch-based bit-packed matrix
4210/// to beat this clause-mining path; that is the remaining perf work for par32-scale.)
4211fn hybrid_xor(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Solved> {
4212    if num_vars == 0 {
4213        return None;
4214    }
4215    let eqs = extract_xor(num_vars, clauses);
4216    let mut xor_vars = HashSet::new();
4217    for e in &eqs {
4218        xor_vars.extend(e.vars.iter().copied());
4219    }
4220    // Gate: a real linear system (≥2 equations) covering at least half the variables.
4221    if eqs.len() < 2 || xor_vars.len() * 2 < num_vars {
4222        return None;
4223    }
4224    let engine = IncXor::new(num_vars, &eqs);
4225    if !engine.is_active() {
4226        return None;
4227    }
4228    // Decide the linear system once: an inconsistent subsystem refutes the whole formula.
4229    let witness = match crate::xorsat::solve(&eqs, num_vars) {
4230        XorOutcome::Unsat(_) => return Some(Solved::unsat(Route::HybridXor)),
4231        XorOutcome::Sat(w) => w,
4232    };
4233    // Collect the strategy's discovered structure: the short clauses Gaussian implies (units,
4234    // binaries, …) that resolution misses. Inject them so CDCL inherits the ruled-out no-goods, and
4235    // seed phases with the GF(2) witness so search starts on the solution manifold. Both only help.
4236    let derived = engine.derived_clauses(xor_width());
4237    let mut solver = Solver::new(num_vars);
4238    for c in clauses {
4239        solver.add_clause(c.clone());
4240    }
4241    for c in derived {
4242        solver.add_clause(c);
4243    }
4244    if xor_seed() {
4245        solver.set_initial_phase(&witness);
4246    }
4247    let result = if xor_live() {
4248        // DPLL(XOR): run the live incremental Gaussian engine as a theory. Optionally restrict CDCL's
4249        // decisions to the kernel — the free variables the linear system leaves undetermined — so the
4250        // pivots are forced by Gaussian propagation rather than branched on (the search then ranges
4251        // only over the true degrees of freedom).
4252        let live = IncXor::new(num_vars, &eqs);
4253        if xor_kernel() {
4254            let decisions = live.decision_vars();
4255            solver.set_decision_vars(&decisions);
4256        }
4257        let mut theories: Vec<Box<dyn crate::cdcl::Theory>> = vec![Box::new(live)];
4258        solver.solve_with(&mut theories)
4259    } else {
4260        solver.solve()
4261    };
4262    match result {
4263        SolveResult::Sat(model) => Some(Solved {
4264            answer: Answer::Sat(model),
4265            via: Route::HybridXor,
4266            proof: Vec::new(),
4267            conflicts: solver.conflicts(),
4268        }),
4269        SolveResult::Unsat => {
4270            let proof = solver
4271                .learned()
4272                .iter()
4273                .map(|lc| ProofStep::Rup(lc.lits.clone()))
4274                .collect();
4275            Some(Solved {
4276                answer: Answer::Unsat,
4277                via: Route::HybridXor,
4278                proof,
4279                conflicts: solver.conflicts(),
4280            })
4281        }
4282    }
4283}
4284
4285/// **Fused parity + cardinality.** When a formula carries BOTH a recovered GF(2) parity substructure
4286/// ([`extract_xor`]) AND an at-most-one cardinality substructure ([`crate::lyapunov::recover_at_most_one`]),
4287/// decide it with the two live theories reasoning TOGETHER on one trail under a single
4288/// [`Solver::solve_with`] — Gaussian elimination for the parity, cardinality propagation for the counting,
4289/// the structural attack on minimal-disagreement parity that neither alone cracks. `None` unless both
4290/// substructures are genuinely present, so pure-parity ([`hybrid_xor`]) and pure-cardinality (the covering
4291/// cut) instances keep their own routes. Sound: the original clauses are solved (Boolean-complete), both
4292/// theories return only formula-entailed clauses, and a SAT model is re-checked (fail-closed). Uses the
4293/// stateless [`crate::xor_engine::XorEngine`], whose trail-sync is always correct.
4294fn fused_modular_solve(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Solved> {
4295    if num_vars == 0 {
4296        return None;
4297    }
4298    let eqs = extract_xor(num_vars, clauses);
4299    let amo = crate::lyapunov::recover_cardinality_substructure(num_vars, clauses);
4300    if eqs.is_empty() || amo.is_empty() {
4301        return None;
4302    }
4303    // Break the FULL affine × cardinality symmetry — the wreath-tower permutation break (class + family) AND
4304    // the affine parity shears. Sound (equisatisfiable); the aux variables extend the var count (they appear
4305    // in no equation, so the theories ignore them), and the answer projects back onto the original variables.
4306    // Break the ENTIRE symmetry group — permutations AND affine maps AND cross-compositions — COMPLETELY and
4307    // DYNAMICALLY via the aux-free SymmetryTheory, fused on the shared trail with parity + cardinality. No
4308    // static clauses, no aux variables.
4309    let mut solver = Solver::new(num_vars);
4310    for c in clauses {
4311        solver.add_clause(c.clone());
4312    }
4313    let mut theories: Vec<Box<dyn crate::cdcl::Theory>> = vec![
4314        Box::new(crate::xor_engine::XorEngine::new(num_vars, &eqs)),
4315        Box::new(crate::pseudo_boolean::CardinalityTheory::new(
4316            num_vars, &amo,
4317        )),
4318        Box::new(crate::lyapunov::SymmetryTheory::new(
4319            num_vars,
4320            crate::lyapunov::fused_symmetry_group(num_vars, clauses),
4321        )),
4322    ];
4323    match solver.solve_with(&mut theories) {
4324        SolveResult::Sat(model) => clauses
4325            .iter()
4326            .all(|c| c.iter().any(|l| model[l.var() as usize] == l.is_positive()))
4327            .then_some(Solved {
4328                answer: Answer::Sat(model),
4329                via: Route::HybridXor,
4330                proof: Vec::new(),
4331                conflicts: solver.conflicts(),
4332            }),
4333        SolveResult::Unsat => Some(Solved {
4334            answer: Answer::Unsat,
4335            via: Route::HybridXor,
4336            proof: Vec::new(),
4337            conflicts: solver.conflicts(),
4338        }),
4339    }
4340}
4341
4342/// Whether to run the live incremental DPLL(XOR) engine during search (vs. clause-mining + phase
4343/// seeding only). Gated by `LOGOS_XOR_LIVE` while we A/B it against the mining path at par-scale.
4344fn xor_live() -> bool {
4345    std::env::var("LOGOS_XOR_LIVE")
4346        .map(|s| s != "0" && !s.is_empty())
4347        .unwrap_or(false)
4348}
4349
4350/// Whether to restrict CDCL's decisions to the kernel (non-pivot) variables under the live engine.
4351/// Default on; `LOGOS_XOR_KERNEL=0` lets VSIDS branch on every variable (Gaussian as pure propagator).
4352fn xor_kernel() -> bool {
4353    std::env::var("LOGOS_XOR_KERNEL")
4354        .map(|s| s != "0" && !s.is_empty())
4355        .unwrap_or(true)
4356}
4357
4358/// Whether to seed CDCL's phases with the GF(2) witness. Default on; `LOGOS_XOR_SEED=0` disables it.
4359fn xor_seed() -> bool {
4360    std::env::var("LOGOS_XOR_SEED")
4361        .map(|s| s != "0" && !s.is_empty())
4362        .unwrap_or(true)
4363}
4364
4365#[cfg(test)]
4366#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/solve/tests.rs"]
4367mod tests;