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;