Skip to main content

logicaffeine_proof/
hypercube.rs

1//! The Boolean hypercube `{0,1}ⁿ` and its subcube cover — the geometric substrate beneath SAT,
2//! and the executable form of the Lean formalization's `HypercubeSAT`.
3//!
4//! Every clause of a CNF is a **blocker**: the set of corners (vertices) of the hypercube that
5//! *falsify* it. A clause of width `w` forbids exactly the `2^{n-w}` corners that set each of its
6//! literals false — a subcube (a face) of codimension `w`. The whole formula is UNSAT precisely
7//! when its blockers **cover** the hypercube: every one of the `2ⁿ` corners is forbidden by some
8//! clause, so no satisfying assignment escapes. SAT ⟺ some corner has *energy zero* — covered by
9//! no blocker. This is `Pnp.lean`'s `Blocker` / `vertexEnergy` / `CoverUNSAT`, made concrete.
10//!
11//! The point of the representation: the **problem** (solutions = uncovered corners) and the
12//! **rules** (clauses = blockers) live in the *same* world `{0,1}ⁿ`. A clause is not a separate
13//! syntactic object; it is a region of the very space the solutions inhabit. So one group action —
14//! a [`CubeSym`], `Pnp.lean`'s `CubeSymmetry` of coordinate permutations and per-coordinate flips —
15//! moves *both*: it permutes blockers among themselves and permutes corners among themselves, in
16//! lockstep. That is what lets us symmetry-break the rules and the solutions with a single move, and
17//! it is why the cover-totality question (UNSAT) collapses by the order of the symmetry group: a
18//! cover is total iff it covers **one representative per orbit**, not all `2ⁿ` corners.
19//!
20//! Pigeonhole is the canonical instance because we can always build one ([`php_cover`]): `n` pigeons
21//! into `n-1` holes, with the full row×column symmetry group `Sₙ × Sₙ₋₁` acting on the grid of
22//! variables. Here we build the stage, answer the first question — *which corners are we blocking?* —
23//! and then **measure** how far each stacked symmetry collapses the cover-check.
24
25use crate::cdcl::Lit;
26use crate::dimacs::DimacsCnf;
27use crate::proof::Perm;
28use std::collections::{BTreeSet, HashMap};
29
30/// A corner (vertex) of the hypercube `{0,1}ⁿ`: bit `v` holds the value of variable `v`.
31/// Enumeration routines assume `n ≤ 63`; the algebra itself is width-agnostic.
32pub type Corner = u64;
33
34/// A subcube of `{0,1}ⁿ`: the coordinates set in `care` are fixed to the matching bits of `value`;
35/// the rest are free. As a **blocker** it is the footprint of one clause — the corners that falsify
36/// it. (`Pnp.lean`'s `Blocker`, generalized from clean 3-bit faces to any width.)
37#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
38pub struct Subcube {
39    pub n: usize,
40    /// Bitmask of the fixed ("cared-about") coordinates — the blocker's support.
41    pub care: u64,
42    /// Required values on the fixed coordinates; bits outside `care` are held at 0.
43    pub value: u64,
44}
45
46impl Subcube {
47    /// The blocker of a clause: the subcube of corners that set *every* literal false. A positive
48    /// literal `xᵥ` is false at `c[v]=0`; a negative literal `¬xᵥ` is false at `c[v]=1`. So `care`
49    /// is the clause's variable set and `value`'s bit `v` is set exactly for the negative literals.
50    pub fn blocker(clause: &[Lit], n: usize) -> Subcube {
51        let mut care = 0u64;
52        let mut value = 0u64;
53        for &lit in clause {
54            let v = lit.var() as u64;
55            care |= 1u64 << v;
56            if !lit.is_positive() {
57                value |= 1u64 << v;
58            }
59        }
60        Subcube { n, care, value }
61    }
62
63    /// Does this subcube contain `corner`? (`Pnp.lean`'s `Blocker.Covers` — is the clause falsified
64    /// at this corner?)
65    #[inline]
66    pub fn covers(&self, corner: Corner) -> bool {
67        (corner & self.care) == self.value
68    }
69
70    /// The number of free coordinates — the subcube's dimension as a face (`n - |support|`).
71    pub fn dimension(&self) -> usize {
72        self.n - self.care.count_ones() as usize
73    }
74
75    /// How many corners this blocker forbids: `2^dimension` (the footprint cardinality).
76    pub fn footprint_card(&self) -> u64 {
77        1u64 << self.dimension()
78    }
79
80    /// Recover the clause this blocker is the footprint of — the inverse of [`Subcube::blocker`].
81    /// A fixed coordinate `v` appears *positively* when `value`'s bit is 0 (the clause is falsified
82    /// at `v=0`) and *negatively* when it is 1. Round-tripping a clause through `blocker` and back is
83    /// the proof that the geometric representation loses nothing.
84    pub fn clause_literals(&self) -> Vec<(usize, bool)> {
85        (0..self.n)
86            .filter(|&v| self.care & (1u64 << v) != 0)
87            .map(|v| (v, self.value & (1u64 << v) == 0))
88            .collect()
89    }
90
91    /// The LP value of this blocker's clause at a fractional point of `[0,1]ⁿ`: `Σ` over literals of
92    /// `x` (positive) or `1−x` (negative). The clause's relaxation is satisfied iff the value is `≥ 1`.
93    /// At the ½-center every literal contributes ½, so the value is `width/2` — satisfied iff width ≥ 2.
94    pub fn clause_lp_value(&self, point: &[f64]) -> f64 {
95        self.clause_literals()
96            .iter()
97            .map(|&(v, positive)| if positive { point[v] } else { 1.0 - point[v] })
98            .sum()
99    }
100
101    /// **Resolve two blockers — the geometry of clause resolution, the engine of "rules beget rules."**
102    /// Two blockers resolve when their fixed coordinates agree everywhere except a single *pivot* where
103    /// they take opposite values (one clause carries the pivot literal, the other its negation, with no
104    /// other clashing literal). The resolvent is the merged blocker with the pivot freed — a *new rule*
105    /// derived from the two neighbors, exactly the Quine–McCluskey adjacency of two implicants. Returns
106    /// `(pivot, resolvent)`, or `None` when there is no single clean pivot (no opposite literal, or a
107    /// second clash making the resolvent a tautology).
108    pub fn resolve(&self, other: &Subcube) -> Option<(usize, Subcube)> {
109        let shared = self.care & other.care;
110        let disagree = shared & (self.value ^ other.value);
111        if disagree.count_ones() != 1 {
112            return None;
113        }
114        let pivot = disagree.trailing_zeros() as usize;
115        let care = (self.care | other.care) & !(1u64 << pivot);
116        let value = (self.value | other.value) & care;
117        Some((
118            pivot,
119            Subcube {
120                n: self.n,
121                care,
122                value,
123            },
124        ))
125    }
126
127    /// Enumerate the blocked corners — the full footprint. Only sensible for small dimension.
128    pub fn footprint(&self) -> Vec<Corner> {
129        let free: Vec<u64> = (0..self.n as u64)
130            .filter(|i| self.care & (1u64 << i) == 0)
131            .collect();
132        let mut out = Vec::with_capacity(1usize << free.len());
133        for mask in 0..(1u64 << free.len()) {
134            let mut c = self.value;
135            for (j, &i) in free.iter().enumerate() {
136                if mask & (1u64 << j) != 0 {
137                    c |= 1u64 << i;
138                }
139            }
140            out.push(c);
141        }
142        out
143    }
144}
145
146/// A cover of the hypercube by clause-blockers — the geometric form of a CNF. UNSAT ⟺ the blockers
147/// leave no corner uncovered.
148#[derive(Clone, Debug)]
149pub struct Cover {
150    pub n: usize,
151    pub blockers: Vec<Subcube>,
152}
153
154impl Cover {
155    /// The blocker cover of a CNF: one subcube per clause.
156    pub fn of_cnf(cnf: &DimacsCnf) -> Cover {
157        let n = cnf.num_vars;
158        let blockers = cnf.clauses.iter().map(|c| Subcube::blocker(c, n)).collect();
159        Cover { n, blockers }
160    }
161
162    /// The **energy** of a corner: how many blockers cover it (`Pnp.lean`'s `vertexEnergy`).
163    /// Energy zero ⟺ the corner is a satisfying assignment.
164    pub fn vertex_energy(&self, corner: Corner) -> usize {
165        self.blockers.iter().filter(|b| b.covers(corner)).count()
166    }
167
168    /// Is `corner` forbidden by some clause? (Does it falsify the formula?)
169    pub fn blocks(&self, corner: Corner) -> bool {
170        self.blockers.iter().any(|b| b.covers(corner))
171    }
172
173    /// `Pnp.lean`'s vertex energy classes. **Tight**: covered by exactly one blocker — that blocker is
174    /// *essential* there, deleting it exposes the corner. **Redundant**: two or more cover it, robust
175    /// to dropping one. (Uncovered, energy 0, is a model — [`escaping_corner`](Self::escaping_corner).)
176    pub fn is_tight(&self, corner: Corner) -> bool {
177        self.vertex_energy(corner) == 1
178    }
179
180    /// `Pnp.lean`'s `VertexOverlappedBy`: two or more blockers cover this corner.
181    pub fn is_redundant(&self, corner: Corner) -> bool {
182        self.vertex_energy(corner) >= 2
183    }
184
185    /// The **essential blockers** — the irreducible core of the cover. A blocker is essential when it
186    /// *privately* covers some corner (a tight vertex no other blocker reaches); deleting it would
187    /// break totality. The essential set is the geometric analog of a minimal resolution refutation:
188    /// the rules you cannot drop. (Enumerates footprints — for small covers.)
189    pub fn essential_blockers(&self) -> Vec<usize> {
190        (0..self.blockers.len())
191            .filter(|&i| {
192                self.blockers[i]
193                    .footprint()
194                    .iter()
195                    .any(|&c| self.vertex_energy(c) == 1)
196            })
197            .collect()
198    }
199
200    /// The first corner no blocker reaches — a satisfying assignment of energy zero — or `None`
201    /// when the cover is total. `None` ⟺ the formula is UNSAT. Brute over all `2ⁿ` corners.
202    pub fn escaping_corner(&self) -> Option<Corner> {
203        (0u64..(1u64 << self.n)).find(|&c| !self.blocks(c))
204    }
205
206    /// UNSAT ⟺ the blockers cover **every** corner of the hypercube (`Pnp.lean`'s `HasNoHole`).
207    pub fn is_total(&self) -> bool {
208        self.escaping_corner().is_none()
209    }
210
211    /// The number of satisfying assignments — uncovered corners of energy zero (`solutionCount`).
212    pub fn solution_count(&self) -> u64 {
213        (0u64..(1u64 << self.n))
214            .filter(|&c| !self.blocks(c))
215            .count() as u64
216    }
217
218    /// `Pnp.lean`'s `HasNoHole` (refutation side): the cover is total — no corner escapes.
219    pub fn has_no_hole(&self) -> bool {
220        self.is_total()
221    }
222
223    /// **The ½ key — is the LP relaxation feasible at the symmetric center?** The all-½ point satisfies
224    /// a clause's relaxation (`Σ lits ≥ 1`) iff the clause has width ≥ 2 (each literal contributes ½).
225    /// When *every* blocker has width ≥ 2, the center `½ⁿ` is a feasible fractional point — so the cover
226    /// can be integer-UNSAT while its LP relaxation is satisfiable. That integrality gap, sitting exactly
227    /// at the symmetry-fixed center, is what resolution (which lives at the corners) cannot see and what
228    /// the counting/cutting-planes shadows close.
229    pub fn relaxation_feasible_at_center(&self) -> bool {
230        self.blockers.iter().all(|b| b.care.count_ones() >= 2)
231    }
232
233    /// Generalized counting crush: derive the `O(1)` Hall certificate (`items > slots`) from *any*
234    /// matching-shaped cover — pigeonhole, clique-coloring, anything that symmetry-breaks to the same
235    /// two rule-types — by recovering the bipartite structure. The pigeonhole crush, no longer
236    /// hard-coded to pigeonhole.
237    pub fn counting_refutation(&self) -> Option<crate::pigeonhole::CountingCert> {
238        crate::pigeonhole::counting_certificate(&self.to_expr()?)
239    }
240
241    /// The **full Hall refutation** — the matching invariant in its complete (subset) form. Catches a
242    /// bipartite cover whose totals balance but where some subset of items competes for too few slots,
243    /// returning the violating subset. Strictly stronger than `counting_refutation`.
244    pub fn hall_refutation(&self) -> Option<crate::matching::HallWitness> {
245        crate::pigeonhole::hall_refutation(&self.to_expr()?)
246    }
247
248    /// `Pnp.lean`'s `HasUniqueHole`: exactly one corner is uncovered (search-critical SAT).
249    pub fn has_unique_hole(&self) -> bool {
250        self.solution_count() == 1
251    }
252
253    /// `Pnp.lean`'s `HasAtLeastHoles k`: at least `k` corners remain uncovered (search-easy SAT).
254    pub fn has_at_least_holes(&self, k: u64) -> bool {
255        self.solution_count() >= k
256    }
257
258    /// `Pnp.lean`'s `BlockerFamily.SeparatedBy`: no blocker crosses the coordinate cut `cut` — each
259    /// blocker's support lies entirely inside it or entirely outside. The hypercube version of a
260    /// decomposition separator.
261    pub fn separated_by(&self, cut: u64) -> bool {
262        self.blockers
263            .iter()
264            .all(|b| (b.care & cut) == b.care || (b.care & cut) == 0)
265    }
266
267    /// `Pnp.lean`'s `BlockerFamily.VariableInteraction`: some blocker mentions both `i` and `j` —
268    /// the primal-graph edge of the cover.
269    pub fn variable_interaction(&self, i: usize, j: usize) -> bool {
270        i != j
271            && self
272                .blockers
273                .iter()
274                .any(|b| b.care & (1u64 << i) != 0 && b.care & (1u64 << j) != 0)
275    }
276
277    /// Recover the CNF this cover is the geometry of, as a `ProofExpr` over atoms `x{var}` — the
278    /// door back into the certified prover. `None` when a blocker is the empty clause (an immediate
279    /// contradiction with no propositional form) or the cover has no blockers.
280    pub fn to_expr(&self) -> Option<crate::ProofExpr> {
281        use crate::ProofExpr;
282        let lit = |v: usize, positive: bool| {
283            let a = ProofExpr::Atom(format!("x{v}"));
284            if positive {
285                a
286            } else {
287                ProofExpr::Not(Box::new(a))
288            }
289        };
290        let mut clauses = Vec::with_capacity(self.blockers.len());
291        for b in &self.blockers {
292            let lits = b.clause_literals();
293            if lits.is_empty() {
294                return None;
295            }
296            let mut it = lits.into_iter();
297            let (v0, p0) = it.next().unwrap();
298            clauses.push(it.fold(lit(v0, p0), |acc, (v, p)| {
299                ProofExpr::Or(Box::new(acc), Box::new(lit(v, p)))
300            }));
301        }
302        let mut it = clauses.into_iter();
303        let first = it.next()?;
304        Some(it.fold(first, |acc, c| ProofExpr::And(Box::new(acc), Box::new(c))))
305    }
306
307    /// Decide cover-totality through the **certified prover**, not brute force: route the cover's CNF
308    /// into [`crate::sat::prove_unsat`], which returns a RUP/PR-checked `Refuted` when the cover is
309    /// total (fail-closed — never a false `Refuted`) or a witnessing model when a corner escapes.
310    /// This is what makes the geometry *provable*: pigeonhole covers certify via the counting shadow
311    /// in polynomial time, where resolution would blow up.
312    pub fn prove_total_certified(&self) -> crate::sat::UnsatOutcome {
313        match self.to_expr() {
314            Some(e) => crate::sat::prove_unsat(&e),
315            None => crate::sat::UnsatOutcome::Unsupported,
316        }
317    }
318
319    /// **Reference one rule, get the rules it nets us.** All blockers that resolve with blocker `i`,
320    /// each paired with its pivot and the resolvent it produces — the neighbors of rule `i` in the
321    /// resolution graph, and the new rules they beget.
322    pub fn neighbors(&self, i: usize) -> Vec<(usize, usize, Subcube)> {
323        (0..self.blockers.len())
324            .filter(|&j| j != i)
325            .filter_map(|j| {
326                self.blockers[i]
327                    .resolve(&self.blockers[j])
328                    .map(|(pivot, r)| (j, pivot, r))
329            })
330            .collect()
331    }
332
333    /// Recover the clauses this cover is the geometry of, as packed [`Lit`]s — the door into the
334    /// automorphism detector and the certified prover's `Lit`-level core.
335    pub fn clauses(&self) -> Vec<Vec<Lit>> {
336        self.blockers
337            .iter()
338            .map(|b| {
339                b.clause_literals()
340                    .into_iter()
341                    .map(|(v, p)| Lit::new(v as u32, p))
342                    .collect()
343            })
344            .collect()
345    }
346
347    /// **Symmetry-break the rules, not the corners.** Partition the blocker indices into orbits under
348    /// the automorphism group generated by `generators`. Each generator must map the blocker *set*
349    /// into itself (it is verified by the image landing back among the blockers); if one ever maps a
350    /// blocker off the set it is not a rule-automorphism and we return `None`, fail-closed.
351    ///
352    /// This is the cheap, powerful move the corner-orbit walk is not: there are only *polynomially*
353    /// many blockers (one per clause), so quotienting the rule set costs `O(generators · blockers ·
354    /// n)` — no `2ⁿ` anywhere. The number of orbits is the count of *essentially distinct rules*: a
355    /// complexity signature of the family computed without ever touching the exponential cube.
356    /// (Assumes distinct blockers, as ordinary CNF families have.)
357    pub fn blocker_orbits(&self, generators: &[CubeSym]) -> Option<Vec<Vec<usize>>> {
358        let mut index: HashMap<Subcube, usize> = HashMap::new();
359        for (i, b) in self.blockers.iter().enumerate() {
360            index.entry(*b).or_insert(i);
361        }
362        let m = self.blockers.len();
363        let mut seen = vec![false; m];
364        let mut orbits = Vec::new();
365        for start in 0..m {
366            if seen[start] {
367                continue;
368            }
369            let mut orbit = Vec::new();
370            let mut stack = vec![start];
371            seen[start] = true;
372            while let Some(i) = stack.pop() {
373                orbit.push(i);
374                for g in generators {
375                    let image = g.map_subcube(&self.blockers[i]);
376                    let &j = index.get(&image)?; // off the blocker set ⟹ not a rule-automorphism
377                    if !seen[j] {
378                        seen[j] = true;
379                        stack.push(j);
380                    }
381                }
382            }
383            orbit.sort_unstable();
384            orbits.push(orbit);
385        }
386        Some(orbits)
387    }
388
389    /// **Discover** this cover's own symmetries and read off its rule-orbit signature — the fully
390    /// self-driving complexity classifier. The detector ([`crate::symmetry_detect::find_generators`])
391    /// returns a generating set of automorphisms as [`Perm`]s, and we quotient the rules by them with
392    /// [`clause_orbits`] (clause-level, so it scales past the geometric cube's 63-variable ceiling).
393    /// A maximally symmetric family (pigeonhole) collapses to a handful of orbits at every scale; a
394    /// random instance, with a trivial automorphism group, collapses to nothing — every rule its own.
395    pub fn discovered_rule_symmetry(&self) -> RuleSymmetry {
396        let clauses = self.clauses();
397        let generators = crate::symmetry_detect::find_generators(self.n, &clauses);
398        let rule_orbits = clause_orbits(&clauses, &generators).len();
399        RuleSymmetry {
400            n: self.n,
401            blockers: clauses.len(),
402            generators: generators.len(),
403            rule_orbits,
404        }
405    }
406}
407
408/// The rule-symmetry signature of a cover: how the polynomially-many blockers collapse under the
409/// family's automorphism group. `rule_orbits` is the count of essentially-distinct rules — a measure
410/// of structural complexity read off *without* enumerating the `2ⁿ` corners. A small, scale-invariant
411/// `rule_orbits` is the geometric fingerprint of a family that admits a short symmetry-broken proof.
412#[derive(Clone, Copy, Debug, PartialEq, Eq)]
413pub struct RuleSymmetry {
414    pub n: usize,
415    pub blockers: usize,
416    pub generators: usize,
417    pub rule_orbits: usize,
418}
419
420/// **Symmetry-break the rules at the clause level** — the lift-and-shift-left form that scales to any
421/// number of variables. Partition the clause indices (the blockers) into orbits under a generating
422/// set of automorphisms, applying each [`Perm`] to clause literals directly via the canonical
423/// `clause_key`. A blocker *is* a clause, so this is the same
424/// rule-quotient as [`Cover::blocker_orbits`] — but with no `2ⁿ` corner geometry and no 63-variable
425/// ceiling, so it runs at scales where the cube is astronomically large. The orbit count is the
426/// number of essentially-distinct rules. (Generators that move a clause off the set are simply not
427/// followed — only genuine rule-automorphisms close orbits.)
428pub fn clause_orbits(clauses: &[Vec<Lit>], generators: &[Perm]) -> Vec<Vec<usize>> {
429    let index: HashMap<Vec<u32>, usize> = clauses
430        .iter()
431        .enumerate()
432        .map(|(i, c)| (crate::symmetry_detect::clause_key(c), i))
433        .collect();
434    let m = clauses.len();
435    let mut seen = vec![false; m];
436    let mut orbits = Vec::new();
437    for start in 0..m {
438        if seen[start] {
439            continue;
440        }
441        let mut orbit = Vec::new();
442        let mut stack = vec![start];
443        seen[start] = true;
444        while let Some(i) = stack.pop() {
445            orbit.push(i);
446            for g in generators {
447                let key = crate::symmetry_detect::clause_key(&g.apply_clause(&clauses[i]));
448                if let Some(&j) = index.get(&key) {
449                    if !seen[j] {
450                        seen[j] = true;
451                        stack.push(j);
452                    }
453                }
454            }
455        }
456        orbit.sort_unstable();
457        orbits.push(orbit);
458    }
459    orbits
460}
461
462/// The pigeonhole grid symmetry group `Sₙ × Sₙ₋₁` as scalable [`Perm`]s — adjacent pigeon (row) and
463/// hole (column) transpositions over the `n*(n-1)` grid variables. No `u64` cap.
464pub fn php_perm_symmetries(n: usize) -> Vec<Perm> {
465    let holes = n.saturating_sub(1);
466    let num_vars = n * holes;
467    let var = |p: usize, h: usize| p * holes + h;
468    let mut gens = Vec::new();
469    for p in 0..n.saturating_sub(1) {
470        let mut images: Vec<Lit> = (0..num_vars as u32).map(Lit::pos).collect();
471        for h in 0..holes {
472            images.swap(var(p, h), var(p + 1, h));
473        }
474        gens.push(Perm::from_images(images));
475    }
476    for h in 0..holes.saturating_sub(1) {
477        let mut images: Vec<Lit> = (0..num_vars as u32).map(Lit::pos).collect();
478        for p in 0..n {
479            images.swap(var(p, h), var(p, h + 1));
480        }
481        gens.push(Perm::from_images(images));
482    }
483    gens
484}
485
486/// The rule-symmetry signature of pigeonhole at scale `n`, computed at the clause level with the full
487/// grid group `Sₙ × Sₙ₋₁`. The blocker set grows superlinearly and the cube has `2^{n(n-1)}` corners,
488/// yet the rules always collapse to exactly **two** orbits — the complexity limit symmetry exposes,
489/// computable at any `n` because it never touches the cube.
490pub fn pigeonhole_rule_symmetry(n: usize) -> RuleSymmetry {
491    let (cnf, _) = crate::families::php(n);
492    let generators = php_perm_symmetries(n);
493    let rule_orbits = clause_orbits(&cnf.clauses, &generators).len();
494    RuleSymmetry {
495        n,
496        blockers: cnf.clauses.len(),
497        generators: generators.len(),
498        rule_orbits,
499    }
500}
501
502/// An **abstract, scale-invariant refutation**: the family's rules symmetry-broken to their orbit
503/// *types*, plus the abstract invariant those types violate, plus the constant-size witness. For
504/// pigeonhole this is two rule-types (every pigeon takes a hole; no two share one) and the counting
505/// fact pigeons > holes — identical at every scale. This is the lift-and-shift-left: the proof's true
506/// size is `O(1)` in the rule-types, reached by *symmetry breaking the rules to their types*, never by
507/// enumerating resolvents (the concrete and even the symmetric resolution closure both explode).
508#[derive(Clone, Debug, PartialEq, Eq)]
509pub struct AbstractRefutation {
510    pub rule_types: usize,
511    pub invariant: &'static str,
512    pub witness: crate::pigeonhole::CountingCert,
513}
514
515/// Symmetry-break pigeonhole to its abstract certificate. The rules collapse (via [`clause_orbits`]) to
516/// exactly **two** types regardless of `n`; the abstract invariant on those types is Hall's condition,
517/// witnessed by the `O(1)` counting certificate pigeons > holes. The whole certificate is constant in
518/// size and identical in shape at every scale — the auto-collapse of pigeonhole, lifted to the type
519/// level where it actually scales. `None` only in the degenerate hole-free case.
520pub fn pigeonhole_abstract_refutation(n: usize) -> Option<AbstractRefutation> {
521    let (cnf, _) = crate::families::php(n);
522    let rule_types = clause_orbits(&cnf.clauses, &php_perm_symmetries(n)).len();
523    let witness =
524        crate::pigeonhole::certify_pigeonhole_unsat(n as u128, n.saturating_sub(1) as u128)?;
525    Some(AbstractRefutation {
526        rule_types,
527        invariant: "Hall/matching: pigeons > holes",
528        witness,
529    })
530}
531
532/// Apply a **flip-renaming** `x_v → ¬x_v` for every `v` with `flips[v]` — a phase-flip symmetry of the
533/// cube. It permutes models bijectively (negate the flipped coordinates), so it preserves satisfiability.
534pub fn apply_renaming(clauses: &[Vec<Lit>], flips: &[bool]) -> Vec<Vec<Lit>> {
535    clauses
536        .iter()
537        .map(|c| {
538            c.iter()
539                .map(|l| {
540                    if flips[l.var() as usize] {
541                        l.negated()
542                    } else {
543                        *l
544                    }
545                })
546                .collect()
547        })
548        .collect()
549}
550
551/// **Recognize a new symmetry: renamable-Horn.** Is there a flip-renaming under which every clause has
552/// at most one positive literal (Horn)? Horn-SAT is polynomial (unit propagation finds the least model),
553/// so a renamable-Horn formula is in a poly class our field cuts cannot see. Crucially, *finding the
554/// renaming is itself a 2-SAT*: a clause is Horn-after-flip iff no two of its literals are both positive,
555/// and "literal `l` is positive after flip" is the single `f`-literal `(l.var, l.is_positive)`. Returns
556/// the flip-set, or `None` if no renaming makes it Horn.
557pub fn renaming_to_horn(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Vec<bool>> {
558    use crate::twosat::{self, Lit as TLit, TwoSatOutcome};
559    let flit = |l: &Lit| {
560        if l.is_positive() {
561            TLit::pos(l.var() as usize)
562        } else {
563            TLit::neg(l.var() as usize)
564        }
565    };
566    let mut two_sat: Vec<(TLit, TLit)> = Vec::new();
567    for c in clauses {
568        for i in 0..c.len() {
569            for j in (i + 1)..c.len() {
570                two_sat.push((flit(&c[i]), flit(&c[j]))); // ¬(both positive after flip)
571            }
572        }
573    }
574    match twosat::solve(&two_sat, num_vars) {
575        TwoSatOutcome::Sat(flips) => Some(flips),
576        TwoSatOutcome::Unsat(_) => None,
577    }
578}
579
580/// The order of a formula's **automorphism group** — `1` means *rigid* (only the identity preserves it),
581/// the maximally asymmetric extreme. Discovers the generators and closes them under composition.
582pub fn automorphism_group_size(num_vars: usize, clauses: &[Vec<Lit>]) -> usize {
583    let generators = crate::symmetry_detect::find_generators(num_vars, clauses);
584    let key = |p: &Perm| -> Vec<(u32, bool)> {
585        (0..num_vars)
586            .map(|v| {
587                let l = p.apply(Lit::pos(v as u32));
588                (l.var(), l.is_positive())
589            })
590            .collect()
591    };
592    let id = Perm::identity(num_vars);
593    let mut seen: BTreeSet<Vec<(u32, bool)>> = [key(&id)].into_iter().collect();
594    let mut group = vec![id];
595    let mut i = 0;
596    while i < group.len() {
597        let g = group[i].clone();
598        i += 1;
599        for s in &generators {
600            let h = s.compose(&g);
601            if seen.insert(key(&h)) {
602                group.push(h);
603            }
604        }
605        if group.len() > 5_000_000 {
606            break;
607        }
608    }
609    group.len()
610}
611
612/// **Information theory — the bits of symmetry.** `log₂|Aut|` is the symmetry-entropy: the number of
613/// bits the automorphism group compresses out of the formula's description (knowing one orbit
614/// representative plus the group recovers the rest). High for symmetric structure, exactly `0` for a
615/// rigid one — and that zero is the maximal-information, incompressible extreme.
616pub fn symmetry_entropy_bits(num_vars: usize, clauses: &[Vec<Lit>]) -> f64 {
617    (automorphism_group_size(num_vars, clauses) as f64).log2()
618}
619
620/// **Find the randomness.** Strip every structural lever — a certified cut decides it (so there was no
621/// irreducible randomness), carve (unit/pure/subsumption) and bounded variable elimination peel structure
622/// away — and return what survives: the irreducible core. `None` means the instance was fully structured
623/// and got decided. `Some(core)` is the kernel where carving can do no more; check it with [`diagnose`] —
624/// if it also has no cut and ~zero symmetry-bits, *that* is the randomness, isolated.
625pub fn find_random_core(
626    num_vars: usize,
627    clauses: &[Vec<Lit>],
628    max_steps: usize,
629) -> Option<Vec<Vec<Lit>>> {
630    let mut current = clauses.to_vec();
631    for _ in 0..max_steps {
632        let cut = clauses_to_expr(&current).is_some_and(|e| {
633            crate::pigeonhole::decide_pigeonhole_unsat(&e)
634                || crate::xorsat::refute_via_parity(&e)
635                || crate::pseudo_boolean::refute_clausal(&e)
636        });
637        if cut {
638            return None; // structured — decided by a cut, no randomness to isolate
639        }
640        match carve(num_vars, &current) {
641            CarveOutcome::Sat | CarveOutcome::Unsat => return None,
642            CarveOutcome::Core { clauses: core, .. } if core.len() < current.len() => {
643                current = core;
644            }
645            CarveOutcome::Core { clauses: core, .. } => {
646                let eliminated = bounded_variable_elimination(num_vars, &core);
647                if eliminated.len() < core.len() {
648                    current = eliminated;
649                } else {
650                    return Some(core); // nothing reduces it further — the irreducible core
651                }
652            }
653        }
654    }
655    Some(current)
656}
657
658/// Where `auto_advance` ended: a decided verdict, or the structureless residue (the irreducible core no
659/// structural lever could touch — where you'd branch).
660#[derive(Clone, Debug, PartialEq, Eq)]
661pub enum AdvanceStatus {
662    Decided(bool),
663    StructurelessResidue { core: usize },
664}
665
666/// One step of the self-driving reduction: the lever applied, and the structure remaining after it.
667#[derive(Clone, Debug, PartialEq)]
668pub struct AdvanceStep {
669    pub lever: &'static str,
670    pub clauses: usize,
671    pub symmetry_bits: f64,
672}
673
674/// **Auto-diagnose, auto-break, auto-advance — to the fixpoint.** Repeatedly diagnose the instance and
675/// apply the most decisive lever it offers: a certified cut decides it outright; otherwise carve (unit /
676/// pure-literal / subsumption) and bounded variable elimination peel it down; the loop advances until a
677/// verdict drops out or no structural lever reduces it further — the structureless residue, where the
678/// only remaining move is to branch. The returned trace shows the structure draining away step by step.
679pub fn auto_advance(
680    num_vars: usize,
681    clauses: &[Vec<Lit>],
682    max_steps: usize,
683) -> (AdvanceStatus, Vec<AdvanceStep>) {
684    let mut current = clauses.to_vec();
685    let mut trace = Vec::new();
686    for _ in 0..max_steps {
687        let bits = symmetry_entropy_bits(num_vars, &current);
688        // A certified cut decides it.
689        let cut = clauses_to_expr(&current).is_some_and(|e| {
690            crate::pigeonhole::decide_pigeonhole_unsat(&e)
691                || crate::xorsat::refute_via_parity(&e)
692                || crate::pseudo_boolean::refute_clausal(&e)
693        });
694        if cut {
695            trace.push(AdvanceStep {
696                lever: "certified cut → UNSAT",
697                clauses: current.len(),
698                symmetry_bits: bits,
699            });
700            return (AdvanceStatus::Decided(false), trace);
701        }
702        // Carve.
703        match carve(num_vars, &current) {
704            CarveOutcome::Sat => {
705                trace.push(AdvanceStep {
706                    lever: "carve → SAT",
707                    clauses: 0,
708                    symmetry_bits: bits,
709                });
710                return (AdvanceStatus::Decided(true), trace);
711            }
712            CarveOutcome::Unsat => {
713                trace.push(AdvanceStep {
714                    lever: "carve → UNSAT",
715                    clauses: 0,
716                    symmetry_bits: bits,
717                });
718                return (AdvanceStatus::Decided(false), trace);
719            }
720            CarveOutcome::Core { clauses: core, .. } if core.len() < current.len() => {
721                trace.push(AdvanceStep {
722                    lever: "carve (unit/pure/subsume)",
723                    clauses: core.len(),
724                    symmetry_bits: bits,
725                });
726                current = core;
727                continue;
728            }
729            CarveOutcome::Core { clauses: core, .. } => {
730                // No carve reduction — try projecting out a dimension.
731                let eliminated = bounded_variable_elimination(num_vars, &core);
732                if eliminated.len() < core.len() {
733                    trace.push(AdvanceStep {
734                        lever: "variable elimination (project a dimension)",
735                        clauses: eliminated.len(),
736                        symmetry_bits: bits,
737                    });
738                    current = eliminated;
739                    continue;
740                }
741                // Nothing reduces it — the structureless residue.
742                trace.push(AdvanceStep {
743                    lever: "irreducible core — no structure left (branch)",
744                    clauses: core.len(),
745                    symmetry_bits: bits,
746                });
747                return (
748                    AdvanceStatus::StructurelessResidue { core: core.len() },
749                    trace,
750                );
751            }
752        }
753    }
754    (
755        AdvanceStatus::StructurelessResidue {
756            core: current.len(),
757        },
758        trace,
759    )
760}
761
762/// A complete auto-diagnosis of an instance: every structure-detector run at once, so you can read off
763/// the full menu of applicable symmetry-breaks and cuts — *what you can still do to it.*
764#[derive(Clone, Debug, PartialEq)]
765pub struct Diagnosis {
766    pub clauses: usize,
767    pub symmetry_bits: f64,
768    pub rule_quotient: usize,
769    pub cut: Option<Shadow>,
770    pub antipodal: bool,
771    pub renamable_horn: bool,
772    pub components: usize,
773    pub autark_section: bool,
774    pub core_clauses: usize,
775}
776
777/// Run every lever's detector and report what applies. The automated "what can we still do" — one call,
778/// the whole portfolio probed.
779pub fn diagnose(num_vars: usize, clauses: &[Vec<Lit>]) -> Diagnosis {
780    let generators = crate::symmetry_detect::find_generators(num_vars, clauses);
781    let rule_quotient = clause_orbits(clauses, &generators).len();
782    let symmetry_bits = symmetry_entropy_bits(num_vars, clauses);
783    let cut = clauses_to_expr(clauses).and_then(|e| {
784        if crate::pigeonhole::decide_pigeonhole_unsat(&e) {
785            Some(Shadow::Counting)
786        } else if crate::xorsat::refute_via_parity(&e) {
787            Some(Shadow::Parity)
788        } else if crate::pseudo_boolean::refute_clausal(&e) {
789            Some(Shadow::CuttingPlanes)
790        } else {
791            None
792        }
793    });
794    let (_, assigned) = pure_literal_reduce(num_vars, clauses);
795    let core_clauses = match carve(num_vars, clauses) {
796        CarveOutcome::Core { clauses: c, .. } => c.len(),
797        _ => 0,
798    };
799    Diagnosis {
800        clauses: clauses.len(),
801        symmetry_bits,
802        rule_quotient,
803        cut,
804        antipodal: is_antipodally_symmetric(clauses),
805        renamable_horn: renaming_to_horn(num_vars, clauses).is_some(),
806        components: components(num_vars, clauses).len(),
807        autark_section: !assigned.is_empty(),
808        core_clauses,
809    }
810}
811
812/// From a [`Diagnosis`], the list of symmetry-breaks and cuts that apply — the menu of moves, in order
813/// of decisiveness. Empty global structure ⟹ the honest fallback: backdoor + branch on the residue.
814pub fn applicable_levers(d: &Diagnosis) -> Vec<&'static str> {
815    let mut levers = Vec::new();
816    if let Some(s) = d.cut {
817        levers.push(match s {
818            Shadow::Counting => "counting/Hall cut (one-punch)",
819            Shadow::Parity => "GF(2) parity cut (one-punch)",
820            Shadow::CuttingPlanes => "cutting-planes cut (one-punch)",
821        });
822    }
823    if d.symmetry_bits > 0.0 {
824        levers.push("symmetry breaking (lex-leader prune)");
825    }
826    if d.antipodal {
827        levers.push("antipodal / center-inversion (recursive)");
828    }
829    if d.renamable_horn {
830        levers.push("renamable-Horn (poly via 2-SAT renaming)");
831    }
832    if d.components > 1 {
833        levers.push("component decomposition");
834    }
835    if d.autark_section || d.core_clauses < d.clauses {
836        levers.push("autarky / carving (unit, pure-literal, subsumption)");
837    }
838    if levers.is_empty() {
839        levers.push("no global structure — backdoor + branch the residue (the honest wall)");
840    }
841    levers
842}
843
844/// The structural profile of an instance — what every lever reveals about *where its difficulty lives*.
845/// `quotient` is the number of rule orbit-types under its discovered symmetry (how far the cube
846/// collapses); `cut` is the certified shadow that decides it, if any; `core_clauses` is what survives
847/// carving + bounded variable elimination (the irreducible residue). Together they place the instance
848/// on the spectrum from "all symmetry, O(1) quotient, instantly cut" to "no symmetry, full quotient,
849/// nothing reduces — the genuinely interesting core."
850#[derive(Clone, Debug, PartialEq, Eq)]
851pub struct StructuralProfile {
852    pub clauses: usize,
853    pub quotient: usize,
854    pub cut: Option<Shadow>,
855    pub core_clauses: usize,
856}
857
858/// Profile an instance: collapse its rules to orbit-types, probe which cut decides it, and carve it to
859/// its irreducible core. The reading that emerges — quotient size tracks cut-decidability tracks core
860/// reducibility — is the single axis underneath every lever: *difficulty is quotient size.*
861pub fn structural_profile(num_vars: usize, clauses: &[Vec<Lit>]) -> StructuralProfile {
862    let generators = crate::symmetry_detect::find_generators(num_vars, clauses);
863    let quotient = clause_orbits(clauses, &generators).len();
864    let cut = clauses_to_expr(clauses).and_then(|e| {
865        if crate::pigeonhole::decide_pigeonhole_unsat(&e) {
866            Some(Shadow::Counting)
867        } else if crate::xorsat::refute_via_parity(&e) {
868            Some(Shadow::Parity)
869        } else if crate::pseudo_boolean::refute_clausal(&e) {
870            Some(Shadow::CuttingPlanes)
871        } else {
872            None
873        }
874    });
875    let core_clauses = match carve(num_vars, clauses) {
876        CarveOutcome::Sat | CarveOutcome::Unsat => 0,
877        CarveOutcome::Core { clauses: c, .. } => bounded_variable_elimination(num_vars, &c).len(),
878    };
879    StructuralProfile {
880        clauses: clauses.len(),
881        quotient,
882        cut,
883        core_clauses,
884    }
885}
886
887/// Which certified shadow refutes a cover — the abstract class of its hardness.
888#[derive(Clone, Copy, Debug, PartialEq, Eq)]
889pub enum Shadow {
890    /// Counting / matching (pigeonhole, Hall) — resolution-hard, polynomial here.
891    Counting,
892    /// Parity / Gaussian over GF(2) (Tseitin, XOR) — resolution-hard, polynomial here.
893    Parity,
894    /// Cutting planes / cardinality (Farkas hyperplane) — resolution-hard, polynomial here.
895    CuttingPlanes,
896}
897
898/// Push a model through an automorphism: if `σ` preserves the clause set and `m` satisfies it, so does
899/// `σ(m)`. Variable `v`'s value lands on `σ(+v)`'s variable, negated when `σ(+v)` is the negative literal
900/// — chosen so `m ⊨ C ⟹ σ(m) ⊨ σ(C)`.
901pub fn apply_perm_to_model(perm: &Perm, model: &[bool]) -> Vec<bool> {
902    let mut out = model.to_vec();
903    for v in 0..model.len() {
904        let image = perm.apply(Lit::pos(v as u32));
905        out[image.var() as usize] = if image.is_positive() {
906            model[v]
907        } else {
908            !model[v]
909        };
910    }
911    out
912}
913
914/// **Symmetry generates solutions.** From one model, the entire orbit under a generating set of
915/// automorphisms — every member a model too, produced with no search. The generative dual of resolution
916/// (which begets *rules* from symmetry); here symmetry begets *solutions*.
917pub fn model_orbit(model: &[bool], generators: &[Perm]) -> Vec<Vec<bool>> {
918    let mut seen = BTreeSet::new();
919    seen.insert(model.to_vec());
920    let mut stack = vec![model.to_vec()];
921    while let Some(m) = stack.pop() {
922        for g in generators {
923            let image = apply_perm_to_model(g, &m);
924            if seen.insert(image.clone()) {
925                stack.push(image);
926            }
927        }
928    }
929    seen.into_iter().collect()
930}
931
932/// **Symmetry-break the witness.** The canonical (lexicographically least) model in a witness's orbit
933/// under the automorphisms — the symmetry-broken representative. All witnesses in one orbit reduce to the
934/// same canonical witness, so the *essential* content of the solution set is one canonical witness per
935/// orbit; the symmetry regenerates the rest via [`model_orbit`].
936pub fn canonical_model(model: &[bool], generators: &[Perm]) -> Vec<bool> {
937    model_orbit(model, generators).into_iter().min().unwrap()
938}
939
940/// The full symmetry group: every distinct `Perm` reachable by composing the generators (closure under
941/// composition). Small-group only — the orbit-stabilizer accounting below needs the *whole* group, not a
942/// generating set. Includes the identity.
943pub fn perm_group_closure(generators: &[Perm], num_vars: usize) -> Vec<Perm> {
944    let mut seen = std::collections::HashSet::new();
945    let id = Perm::identity(num_vars);
946    let mut frontier = vec![id.clone()];
947    seen.insert(id);
948    while let Some(g) = frontier.pop() {
949        for h in generators {
950            let gh = h.compose(&g);
951            if seen.insert(gh.clone()) {
952                frontier.push(gh);
953            }
954        }
955    }
956    seen.into_iter().collect()
957}
958
959/// **The stabilizer of a witness** — the subgroup of symmetries that fix it (`σ·m = m`). These are the
960/// transformations under which the witness sees *itself*; they are exactly the redundancy in its
961/// perspective of the others.
962pub fn stabilizer(model: &[bool], group: &[Perm]) -> Vec<Perm> {
963    group
964        .iter()
965        .filter(|g| apply_perm_to_model(g, model) == model)
966        .cloned()
967        .collect()
968}
969
970/// **Symmetry-break across the witness's perspective of the other witnesses.** From witness `m`, every
971/// other witness in its orbit is reached by *some* symmetry — but many symmetries land on the same one
972/// (they differ by a stabilizer element of `m`). The symmetry-broken perspective quotients that
973/// redundancy out: exactly **one** representative transformation per distinct witness `m` can see — a
974/// transversal of the coset space `G / Stab(m)`. The returned `(witness, σ)` pairs satisfy `σ·m =
975/// witness`, and their count is `|G| / |Stab(m)| = |orbit(m)|` (orbit–stabilizer). The first entry is
976/// `(m, identity)`: the witness's view of itself.
977pub fn witness_perspective(
978    model: &[bool],
979    generators: &[Perm],
980    num_vars: usize,
981) -> Vec<(Vec<bool>, Perm)> {
982    let group = perm_group_closure(generators, num_vars);
983    let mut seen = BTreeSet::new();
984    let mut out = Vec::new();
985    let mut by_dest: Vec<(Vec<bool>, Perm)> = Vec::new();
986    for g in &group {
987        let dest = apply_perm_to_model(g, model);
988        if seen.insert(dest.clone()) {
989            by_dest.push((dest, g.clone()));
990        }
991    }
992    by_dest.sort_by(|a, b| a.0.cmp(&b.0));
993    let here = by_dest.iter().position(|(d, _)| d == model).unwrap();
994    out.push((model.to_vec(), Perm::identity(num_vars)));
995    for (i, pair) in by_dest.into_iter().enumerate() {
996        if i != here {
997            out.push(pair);
998        }
999    }
1000    out
1001}
1002
1003/// **Burnside orbit count — the number of essentially-distinct witnesses.** By Burnside's lemma the
1004/// number of orbits of a group action equals the *average* number of fixed points:
1005/// `#orbits = (1/|G|) · Σ_{g∈G} |Fix(g)|`, where `Fix(g) = { m : g·m = m }`. Applied to the solution
1006/// set (closed under the automorphisms, since every `g` is an automorphism), this counts the witnesses
1007/// **up to symmetry** — the essential solutions — as a fixed-point average, never enumerating an orbit.
1008/// The sum is exactly divisible by `|G|` (the lemma guarantees it); `group` must be the *whole* group
1009/// (use [`perm_group_closure`]).
1010pub fn burnside_orbit_count(models: &[Vec<bool>], group: &[Perm]) -> usize {
1011    let total_fixed: usize = group
1012        .iter()
1013        .map(|g| {
1014            models
1015                .iter()
1016                .filter(|m| apply_perm_to_model(g, m.as_slice()) == **m)
1017                .count()
1018        })
1019        .sum();
1020    total_fixed / group.len()
1021}
1022
1023/// **Where an UNSAT instance sits in the proof-complexity landscape**, as our certified cuts see it.
1024/// This is a *ladder of proof systems* (Cook–Reckhow): each rung crushes families the cheaper ones are
1025/// blind to. `Counting` and `Parity` are **incomparable narrow detectors** — pigeonhole needs counting
1026/// and is invisible to GF(2); Tseitin needs GF(2) and is invisible to counting — while
1027/// `Nullstellensatz{min_degree}` is the *universal algebraic height* over GF(2), complete at degree `n`.
1028/// The honest face of the wall: an instance whose narrow cuts are silent and whose minimum NS degree is
1029/// large sits at the top of this ladder, and the cost *at* that height is exponential. We can *locate* an
1030/// instance on the ladder; we cannot prove the top rung is unavoidable for a family — that lower bound is
1031/// exactly P vs NP, and it stays open.
1032#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1033pub enum ProofRung {
1034    /// Closed by unit propagation / carving alone — no real refutation needed.
1035    Trivial,
1036    /// A counting / Hall (pigeonhole) cut crushes it. Resolution-exponential families like PHP live here;
1037    /// incomparable to `Parity`.
1038    Counting,
1039    /// A GF(2) parity (Gaussian-elimination) cut crushes it. Tseitin / XOR families live here;
1040    /// incomparable to `Counting`.
1041    Parity,
1042    /// A certified mod-`p` Gaussian cut crushes it — `Parity` carried to the odd prime `p`: the CNF is a
1043    /// recognized one-hot encoding of a `GF(p)` linear system whose refutation re-checks. One rung per
1044    /// characteristic, each incomparable to the others and to `Counting`/`Parity` (the prime
1045    /// incomparability of `polycalc_gfp`). Reported only by the extended cascade
1046    /// ([`weakest_crushing_rung_with_char`]); the legacy cascade predates the characteristic axis.
1047    ModCount { p: u64 },
1048    /// No narrow cut fires; refuted only by Nullstellensatz / Polynomial Calculus over GF(2) at this
1049    /// minimum degree — the universal algebraic height. The rigid residue lives here.
1050    Nullstellensatz { min_degree: usize },
1051    /// No cut and no NS refutation within the degree budget — the wall as our detectors perceive it.
1052    BeyondBudget,
1053}
1054
1055/// Locate an instance on the [`ProofRung`] ladder: the *weakest* certified cut that crushes it, probed
1056/// cheapest-first (carve ≺ counting ≺ parity ≺ Nullstellensatz-by-degree). The narrow rungs (`Counting`,
1057/// `Parity`) are incomparable; probe order only decides the label when more than one happens to fire.
1058///
1059/// **This has no satisfiability oracle.** `BeyondBudget` means *no certified cut fired* — which covers
1060/// **both** a satisfiable instance **and** a hard-UNSAT one beyond the degree budget. Our detectors
1061/// cannot tell those two apart cheaply; that very indistinguishability is the wall, and resolving it for
1062/// a family (proving the budget *must* be exceeded) is P vs NP.
1063pub fn weakest_crushing_rung(num_vars: usize, clauses: &[Vec<Lit>], ns_budget: usize) -> ProofRung {
1064    weakest_crushing_rung_with_char(num_vars, clauses, ns_budget, &[])
1065}
1066
1067/// [`weakest_crushing_rung`] with the **characteristic rungs enabled** — the same cascade, plus, between
1068/// the parity probe and the algebraic ascent, a certified mod-`p` cut per prime in `primes`: when the
1069/// CNF is a recognized one-hot encoding of a `GF(p)` linear system ([`crate::modp::recover_from_cnf`],
1070/// which declines rather than guesses) and the `GF(p)` Gaussian refutation re-checks
1071/// ([`crate::modp::is_refutation`]), the instance lands on [`ProofRung::ModCount`]. This is the ladder
1072/// rung the census's `router_beats_ladder` audit flagged as missing: the structured router's
1073/// `Route::ModP` specialist finally has a certified proof system the ladder can name. With
1074/// `primes = &[]` the cascade is exactly the legacy one.
1075pub fn weakest_crushing_rung_with_char(
1076    num_vars: usize,
1077    clauses: &[Vec<Lit>],
1078    ns_budget: usize,
1079    primes: &[u64],
1080) -> ProofRung {
1081    if let CarveOutcome::Unsat = carve(num_vars, clauses) {
1082        return ProofRung::Trivial;
1083    }
1084    let Some(e) = clauses_to_expr(clauses) else {
1085        return ProofRung::BeyondBudget;
1086    };
1087    if crate::pigeonhole::counting_certificate(&e).is_some()
1088        || crate::pigeonhole::hall_refutation(&e).is_some()
1089    {
1090        return ProofRung::Counting;
1091    }
1092    if crate::xorsat::refute_via_parity(&e) {
1093        return ProofRung::Parity;
1094    }
1095    if !primes.is_empty() {
1096        if let Some(rec) = crate::modp::recover_from_cnf(num_vars, clauses) {
1097            if primes.contains(&rec.modulus) {
1098                if let crate::modp::ModpOutcome::Unsat(combo) =
1099                    crate::modp::solve(&rec.equations, rec.num_vars, rec.modulus)
1100                {
1101                    if crate::modp::is_refutation(&rec.equations, rec.num_vars, rec.modulus, &combo)
1102                    {
1103                        return ProofRung::ModCount { p: rec.modulus };
1104                    }
1105                }
1106            }
1107        }
1108    }
1109    let cap = ns_budget.min(num_vars);
1110    if let Some(d) =
1111        (1..=cap).find(|&d| crate::polycalc::nullstellensatz_refutes(num_vars, clauses, d))
1112    {
1113        return ProofRung::Nullstellensatz { min_degree: d };
1114    }
1115    ProofRung::BeyondBudget
1116}
1117
1118/// **Symmetry-aware solution counting.** Partition a set of models into orbits under a generating set
1119/// of automorphisms; each orbit is the full `model_orbit` of any of its members. The solution count is
1120/// the sum of the orbit sizes, so a symmetric instance collapses to *one representative per orbit* — far
1121/// fewer than the solutions themselves. (`models` should be closed under the symmetry, e.g. all models.)
1122pub fn partition_into_orbits(models: &[Vec<bool>], generators: &[Perm]) -> Vec<Vec<Vec<bool>>> {
1123    let model_set: BTreeSet<Vec<bool>> = models.iter().cloned().collect();
1124    let mut assigned: BTreeSet<Vec<bool>> = BTreeSet::new();
1125    let mut orbits = Vec::new();
1126    for m in models {
1127        if assigned.contains(m) {
1128            continue;
1129        }
1130        let orbit: Vec<Vec<bool>> = model_orbit(m, generators)
1131            .into_iter()
1132            .filter(|x| model_set.contains(x))
1133            .collect();
1134        for x in &orbit {
1135            assigned.insert(x.clone());
1136        }
1137        orbits.push(orbit);
1138    }
1139    orbits
1140}
1141
1142/// **Autocarve — recursive carving that lets the rules fall out.** Carve the formula to its core,
1143/// decompose into independent components, and for each: if a certified cut recognizes it, the rule
1144/// *falls out* and the component closes; otherwise branch one variable and **carve again** on each
1145/// branch. Every decision cascades fresh unit propagations and pure literals, exposing structure the
1146/// previous level hid — so a buried, masked, or nested invariant surfaces on its own at the depth it
1147/// becomes visible. UNSAT iff any component is, SAT iff all are; `None` past the budget.
1148/// What an autocarve run did: how many recursion nodes it visited, how many times a certified cut
1149/// *fired* (a "punch"), and how deep the carving recursed.
1150#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
1151pub struct CarveStats {
1152    pub nodes: usize,
1153    pub punches: usize,
1154    pub max_depth: usize,
1155}
1156
1157pub fn autocarve(num_vars: usize, clauses: &[Vec<Lit>], budget: usize) -> Option<bool> {
1158    autocarve_measured(num_vars, clauses, budget).0
1159}
1160
1161/// Like [`autocarve`], but also returns the [`CarveStats`] — node count, punch count, recursion depth.
1162pub fn autocarve_measured(
1163    num_vars: usize,
1164    clauses: &[Vec<Lit>],
1165    budget: usize,
1166) -> (Option<bool>, CarveStats) {
1167    let mut stats = CarveStats::default();
1168    let verdict = autocarve_rec(num_vars, clauses, budget, 0, &mut stats);
1169    (verdict, stats)
1170}
1171
1172fn autocarve_rec(
1173    num_vars: usize,
1174    clauses: &[Vec<Lit>],
1175    budget: usize,
1176    depth: usize,
1177    stats: &mut CarveStats,
1178) -> Option<bool> {
1179    stats.nodes += 1;
1180    stats.max_depth = stats.max_depth.max(depth);
1181    if stats.nodes > budget {
1182        return None;
1183    }
1184    let core = match carve(num_vars, clauses) {
1185        CarveOutcome::Sat => return Some(true),
1186        CarveOutcome::Unsat => return Some(false),
1187        CarveOutcome::Core { clauses, .. } => clauses,
1188    };
1189    for component in components(num_vars, &core) {
1190        // The rule falls out: a certified cut recognizes the carved component — a punch. The full-set
1191        // counting bound (`items > slots`) is the *symmetric* special case — O(1) after extraction, no
1192        // matching — so try it first; only fall back to the general Hall matching when it doesn't fire.
1193        let cut = clauses_to_expr(&component).is_some_and(|e| {
1194            crate::pigeonhole::counting_certificate(&e).is_some()
1195                || crate::pigeonhole::decide_pigeonhole_unsat(&e)
1196                || crate::xorsat::refute_via_parity(&e)
1197                || crate::pseudo_boolean::refute_clausal(&e)
1198        });
1199        if cut {
1200            stats.punches += 1;
1201            return Some(false); // a UNSAT component refutes the whole formula
1202        }
1203        // Otherwise branch and carve again — the structure surfaces one decision deeper.
1204        let pivot = component[0][0].var();
1205        let mut component_sat = false;
1206        for value in [false, true] {
1207            let mut branch = component.clone();
1208            branch.push(vec![Lit::new(pivot, value)]);
1209            match autocarve_rec(num_vars, &branch, budget, depth + 1, stats) {
1210                Some(true) => {
1211                    component_sat = true;
1212                    break;
1213                }
1214                Some(false) => {}
1215                None => return None,
1216            }
1217        }
1218        if !component_sat {
1219            return Some(false); // both branches UNSAT ⟹ this component, and the whole formula, is UNSAT
1220        }
1221    }
1222    Some(true)
1223}
1224
1225/// **The unified crush.** Compose every lever into one decision procedure: carve the autark sections
1226/// (pure literals), split into independent components, and decide each by the cut-enabled
1227/// symmetry-aware search — a component refuted by a certified cut at the root closes in one node, the
1228/// rest fall to bounded branch-and-cut. The formula is UNSAT iff any component is, SAT iff all are.
1229/// Returns `None` only when a component blows past the budget — the genuinely hard residue, honestly
1230/// surfaced rather than hidden.
1231pub fn crush(num_vars: usize, clauses: &[Vec<Lit>], budget: usize) -> Option<bool> {
1232    let (core, _) = pure_literal_reduce(num_vars, clauses);
1233    if core.is_empty() {
1234        return Some(true); // every section carved away — satisfiable
1235    }
1236    for component in components(num_vars, &core) {
1237        match search_cost(num_vars, &component, true, budget) {
1238            SearchCost::Decided { sat: false, .. } => return Some(false), // a UNSAT component refutes all
1239            SearchCost::Decided { sat: true, .. } => {}                   // satisfiable, keep going
1240            SearchCost::Exceeded { .. } => return None,                   // the hard residue
1241        }
1242    }
1243    Some(true) // every component satisfiable
1244}
1245
1246fn resolve_on_var(cp: &[Lit], cn: &[Lit], v: usize) -> Option<Vec<Lit>> {
1247    let mut lits: Vec<Lit> = Vec::new();
1248    for &l in cp.iter().chain(cn.iter()) {
1249        if l.var() as usize != v && !lits.contains(&l) {
1250            lits.push(l);
1251        }
1252    }
1253    if lits.iter().any(|l| lits.contains(&l.negated())) {
1254        return None; // tautological resolvent — discard
1255    }
1256    Some(lits)
1257}
1258
1259/// **Carve out a dimension.** Eliminate variable `v` by resolution (Davis–Putnam): drop every clause
1260/// mentioning `v`, and add the non-tautological resolvents of each `v`-clause against each `¬v`-clause.
1261/// Geometrically this *projects the cube's `v`-axis away* — the formula over `n` dimensions becomes an
1262/// equisatisfiable one over `n-1`. Sound: a model of the projection lifts to a model of the original.
1263pub fn eliminate_variable(v: usize, clauses: &[Vec<Lit>]) -> Vec<Vec<Lit>> {
1264    let (pv, nv) = (Lit::new(v as u32, true), Lit::new(v as u32, false));
1265    let mut result: Vec<Vec<Lit>> = clauses
1266        .iter()
1267        .filter(|c| !c.contains(&pv) && !c.contains(&nv))
1268        .cloned()
1269        .collect();
1270    let pos: Vec<&Vec<Lit>> = clauses.iter().filter(|c| c.contains(&pv)).collect();
1271    let neg: Vec<&Vec<Lit>> = clauses.iter().filter(|c| c.contains(&nv)).collect();
1272    for cp in &pos {
1273        for cn in &neg {
1274            if let Some(resolvent) = resolve_on_var(cp, cn, v) {
1275                result.push(resolvent);
1276            }
1277        }
1278    }
1279    result
1280}
1281
1282/// **Bounded variable elimination** — carve away every dimension whose projection doesn't grow the
1283/// formula (resolvents ≤ clauses removed). Iterated to a fixpoint, it peels the cube down dimension by
1284/// dimension wherever it's free to do so; the variables that *would* explode (pigeonhole's, by Haken)
1285/// are left for the cuts. Satisfiability-preserving.
1286pub fn bounded_variable_elimination(num_vars: usize, clauses: &[Vec<Lit>]) -> Vec<Vec<Lit>> {
1287    let mut current = clauses.to_vec();
1288    loop {
1289        let mut eliminated = false;
1290        for v in 0..num_vars {
1291            let pos = current
1292                .iter()
1293                .filter(|c| c.contains(&Lit::new(v as u32, true)))
1294                .count();
1295            let neg = current
1296                .iter()
1297                .filter(|c| c.contains(&Lit::new(v as u32, false)))
1298                .count();
1299            if pos == 0 || neg == 0 {
1300                continue;
1301            }
1302            let candidate = eliminate_variable(v, &current);
1303            if candidate.len() <= current.len() {
1304                current = candidate;
1305                eliminated = true;
1306            }
1307        }
1308        if !eliminated {
1309            break;
1310        }
1311    }
1312    current
1313}
1314
1315/// What carving the hypercube reduced a formula to.
1316#[derive(Clone, Debug, PartialEq, Eq)]
1317pub enum CarveOutcome {
1318    /// Carved to nothing — satisfiable.
1319    Sat,
1320    /// Carved to an empty clause — unsatisfiable.
1321    Unsat,
1322    /// Carved to an irreducible core, plus the literals forced along the way.
1323    Core {
1324        clauses: Vec<Vec<Lit>>,
1325        forced: Vec<Lit>,
1326    },
1327}
1328
1329fn find_pure_literal(num_vars: usize, clauses: &[Vec<Lit>]) -> Option<Lit> {
1330    let mut pos = vec![false; num_vars];
1331    let mut neg = vec![false; num_vars];
1332    for c in clauses {
1333        for l in c {
1334            if l.is_positive() {
1335                pos[l.var() as usize] = true;
1336            } else {
1337                neg[l.var() as usize] = true;
1338            }
1339        }
1340    }
1341    (0..num_vars).find_map(|v| match (pos[v], neg[v]) {
1342        (true, false) => Some(Lit::new(v as u32, true)),
1343        (false, true) => Some(Lit::new(v as u32, false)),
1344        _ => None,
1345    })
1346}
1347
1348fn subsume_once(clauses: &mut Vec<Vec<Lit>>) -> bool {
1349    for i in 0..clauses.len() {
1350        for j in 0..clauses.len() {
1351            if i != j
1352                && clauses[i].len() < clauses[j].len()
1353                && clauses[i].iter().all(|l| clauses[j].contains(l))
1354            {
1355                clauses.remove(j);
1356                return true;
1357            }
1358        }
1359    }
1360    false
1361}
1362
1363/// **Carve away the hypercube.** Peel the formula down by the three classic simplifications, iterated to
1364/// a fixpoint: *unit propagation* (a unit clause carves the cube in half by forcing a variable),
1365/// *pure-literal* assignment (carves an autark section), and *subsumption* (drops a blocker contained in
1366/// a stronger one). All three preserve satisfiability, so the result is either a verdict or the
1367/// irreducible core that genuine hardness leaves behind. Pigeonhole carves to itself.
1368pub fn carve(num_vars: usize, clauses: &[Vec<Lit>]) -> CarveOutcome {
1369    let mut current: Vec<Vec<Lit>> = clauses.to_vec();
1370    let mut forced: Vec<Lit> = Vec::new();
1371    loop {
1372        if current.iter().any(|c| c.is_empty()) {
1373            return CarveOutcome::Unsat;
1374        }
1375        if current.is_empty() {
1376            return CarveOutcome::Sat;
1377        }
1378        let mut changed = false;
1379        if let Some(unit) = current.iter().find(|c| c.len() == 1).map(|c| c[0]) {
1380            forced.push(unit);
1381            let neg = unit.negated();
1382            current.retain(|c| !c.contains(&unit));
1383            for c in &mut current {
1384                c.retain(|&l| l != neg);
1385            }
1386            changed = true;
1387        } else if let Some(pure) = find_pure_literal(num_vars, &current) {
1388            forced.push(pure);
1389            current.retain(|c| !c.contains(&pure));
1390            changed = true;
1391        } else if subsume_once(&mut current) {
1392            changed = true;
1393        }
1394        if !changed {
1395            return CarveOutcome::Core {
1396                clauses: current,
1397                forced,
1398            };
1399        }
1400    }
1401}
1402
1403/// **Cut out the autark sections.** A *pure literal* (a variable appearing in only one polarity) is the
1404/// simplest autarky: assigning it satisfies every clause it touches, so that whole section of the cube is
1405/// removed without affecting satisfiability. Iterate to a fixpoint and what remains is the hard core —
1406/// the part with no free section to cut. Returns `(core clauses, assigned pure literals)`. Sound: pure-
1407/// literal elimination preserves satisfiability (Davis–Putnam).
1408pub fn pure_literal_reduce(num_vars: usize, clauses: &[Vec<Lit>]) -> (Vec<Vec<Lit>>, Vec<Lit>) {
1409    let mut current: Vec<Vec<Lit>> = clauses.to_vec();
1410    let mut assigned = Vec::new();
1411    loop {
1412        let mut pos = vec![false; num_vars];
1413        let mut neg = vec![false; num_vars];
1414        for c in &current {
1415            for l in c {
1416                if l.is_positive() {
1417                    pos[l.var() as usize] = true;
1418                } else {
1419                    neg[l.var() as usize] = true;
1420                }
1421            }
1422        }
1423        let pure = (0..num_vars).find_map(|v| match (pos[v], neg[v]) {
1424            (true, false) => Some(Lit::new(v as u32, true)),
1425            (false, true) => Some(Lit::new(v as u32, false)),
1426            _ => None,
1427        });
1428        let Some(l) = pure else { break };
1429        assigned.push(l);
1430        current.retain(|c| !c.iter().any(|&x| x == l));
1431    }
1432    (current, assigned)
1433}
1434
1435/// Partition a formula into its **independent components** — maximal clause groups sharing no variable
1436/// (the connected components of the variable-interaction graph). The formula is the conjunction of its
1437/// components, so it is UNSAT iff *any* component is, and each can be attacked on its own. A structured
1438/// UNSAT component buried in a big mixed formula — invisible to the monolithic cut — is laid bare here.
1439pub fn components(num_vars: usize, clauses: &[Vec<Lit>]) -> Vec<Vec<Vec<Lit>>> {
1440    fn find(parent: &mut [usize], mut x: usize) -> usize {
1441        while parent[x] != x {
1442            parent[x] = parent[parent[x]];
1443            x = parent[x];
1444        }
1445        x
1446    }
1447    let mut parent: Vec<usize> = (0..num_vars.max(1)).collect();
1448    for clause in clauses {
1449        let vars: Vec<usize> = clause.iter().map(|l| l.var() as usize).collect();
1450        for pair in vars.windows(2) {
1451            let (a, b) = (find(&mut parent, pair[0]), find(&mut parent, pair[1]));
1452            parent[a] = b;
1453        }
1454    }
1455    let mut groups: HashMap<usize, Vec<Vec<Lit>>> = HashMap::new();
1456    for clause in clauses {
1457        let root = clause
1458            .first()
1459            .map(|l| find(&mut parent, l.var() as usize))
1460            .unwrap_or(0);
1461        groups.entry(root).or_default().push(clause.clone());
1462    }
1463    groups.into_values().collect()
1464}
1465
1466/// Decompose into independent components and crush: return `true` (UNSAT) the moment any component is
1467/// refuted by a certified cut, never having examined the rest. Isolating a structured UNSAT component
1468/// unlocks a cut the monolithic formula hides.
1469pub fn decompose_and_crush(num_vars: usize, clauses: &[Vec<Lit>]) -> bool {
1470    components(num_vars, clauses).iter().any(|comp| {
1471        clauses_to_expr(comp).is_some_and(|e| {
1472            crate::pigeonhole::decide_pigeonhole_unsat(&e)
1473                || crate::xorsat::refute_via_parity(&e)
1474                || crate::pseudo_boolean::refute_clausal(&e)
1475        })
1476    })
1477}
1478
1479/// Is the cover invariant under the **antipodal map** — global negation `x → ¬x`, the center-inversion
1480/// of the cube? True iff flipping every literal of every clause maps the clause set onto itself. This is
1481/// a symmetry axis *distinct* from coordinate permutation: it is the involution whose unique fixed point
1482/// is the ½-center ([`CubeSym::map_fractional`] with all flips and no permutation fixes `½ⁿ`). When it
1483/// holds, satisfying assignments come in antipodal pairs `{a, ¬a}`, so one variable's value is free WLOG.
1484pub fn is_antipodally_symmetric(clauses: &[Vec<Lit>]) -> bool {
1485    let key = |c: &[Lit]| -> Vec<u32> {
1486        let mut k: Vec<u32> = c
1487            .iter()
1488            .map(|l| l.var() * 2 + u32::from(!l.is_positive()))
1489            .collect();
1490        k.sort_unstable();
1491        k.dedup();
1492        k
1493    };
1494    let original: BTreeSet<Vec<u32>> = clauses.iter().map(|c| key(c)).collect();
1495    let flipped: BTreeSet<Vec<u32>> = clauses
1496        .iter()
1497        .map(|c| key(&c.iter().map(|l| l.negated()).collect::<Vec<_>>()))
1498        .collect();
1499    original == flipped
1500}
1501
1502/// What a laddered branch-and-cut search did: how many subcubes (nodes) it visited, how deep it
1503/// laddered, and how many subtrees a certified cut closed outright.
1504#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1505pub struct LadderStats {
1506    pub nodes: usize,
1507    pub max_depth: usize,
1508    pub cut_closures: usize,
1509    pub pruned: usize,
1510}
1511
1512/// **Ladder up the hypercube: crush what we can, brute-force the rest.** Branch-and-cut over `{0,1}ⁿ`,
1513/// one variable at a time — exactly DPLL with our certified cuts as the theory:
1514/// 1. **base** — a residual empty clause means this subcube is fully covered (UNSAT branch); no
1515///    residual clauses means a corner escapes here (SAT).
1516/// 2. **unit propagation** — a residual unit clause forces its variable (free dimension reduction).
1517/// 3. **cut** — try the certified shadows (counting / parity / cutting-planes) on the residual; if one
1518///    fires, the whole subcube is crushed without descending — the learned invariant doing its work.
1519/// 4. **branch** — otherwise split on a residual variable and ladder down.
1520///
1521/// Structured families (pigeonhole, Tseitin, clique) are crushed by a cut at or near the root in a
1522/// handful of nodes *at any `n`*, because the cut is scale-free; the genuinely unstructured residual is
1523/// brute-forced by the branching. Works on raw clauses, so it ladders past the cube's 63-variable
1524/// geometric ceiling.
1525pub fn decide_laddered(num_vars: usize, clauses: &[Vec<Lit>]) -> (bool, LadderStats) {
1526    let mut stats = LadderStats {
1527        nodes: 0,
1528        max_depth: 0,
1529        cut_closures: 0,
1530        pruned: 0,
1531    };
1532    let sat = ladder(clauses, vec![None; num_vars], 0, &mut stats);
1533    (sat, stats)
1534}
1535
1536/// **Symmetry-break the search itself.** The same branch-and-cut ladder, but it branches variables in
1537/// index order and *prunes* a node whenever a root automorphism maps its decided prefix to a
1538/// lexicographically smaller decided assignment — classic lex-leader symmetry breaking during search.
1539/// Sound by construction: every orbit of assignments keeps exactly one lex-leader, and only strict
1540/// non-leaders are pruned, so the verdict never changes; symmetric subtrees are simply skipped. The
1541/// automorphisms are discovered once at the root.
1542pub fn decide_laddered_sym(
1543    num_vars: usize,
1544    clauses: &[Vec<Lit>],
1545    use_cut: bool,
1546) -> (bool, LadderStats) {
1547    let generators = crate::symmetry_detect::find_generators(num_vars, clauses);
1548    let mut stats = LadderStats {
1549        nodes: 0,
1550        max_depth: 0,
1551        cut_closures: 0,
1552        pruned: 0,
1553    };
1554    let sat = ladder_sym(
1555        clauses,
1556        vec![None; num_vars],
1557        0,
1558        &generators,
1559        use_cut,
1560        &mut stats,
1561    );
1562    (sat, stats)
1563}
1564
1565/// The baseline the symmetry-pruned search is measured against: the *same* branch engine with no cut
1566/// and no generators (so `violates_lex_leader` never fires). Isolates the effect of symmetry pruning.
1567pub fn decide_laddered_nocut(num_vars: usize, clauses: &[Vec<Lit>]) -> (bool, LadderStats) {
1568    let mut stats = LadderStats {
1569        nodes: 0,
1570        max_depth: 0,
1571        cut_closures: 0,
1572        pruned: 0,
1573    };
1574    let sat = ladder_sym(clauses, vec![None; num_vars], 0, &[], false, &mut stats);
1575    (sat, stats)
1576}
1577
1578/// The measured cost of a branch search: either it decided within the node budget, or the search blew
1579/// past it (the exponential explosion, captured rather than hung).
1580#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1581pub enum SearchCost {
1582    Decided { sat: bool, nodes: usize },
1583    Exceeded { budget: usize },
1584}
1585
1586/// Run the branch engine purely to **measure** its size, with `use_cut` selecting whether the certified
1587/// cuts fire, and a hard `budget` on visited nodes so a resolution-class explosion is recorded as
1588/// `Exceeded` instead of running forever. With the cut off this is raw DPLL (resolution-strength); with
1589/// it on, the certified cut closes whole subtrees. The apples-to-apples gap between the two is the
1590/// campaign's thesis, quantified.
1591pub fn search_cost(
1592    num_vars: usize,
1593    clauses: &[Vec<Lit>],
1594    use_cut: bool,
1595    budget: usize,
1596) -> SearchCost {
1597    let mut nodes = 0usize;
1598    match cost_rec(clauses, vec![None; num_vars], use_cut, budget, &mut nodes) {
1599        Some(sat) => SearchCost::Decided { sat, nodes },
1600        None => SearchCost::Exceeded { budget },
1601    }
1602}
1603
1604/// **Recursive antipodal symmetry breaking.** Branch search that, at *every* node, re-detects whether
1605/// the residual is antipodally symmetric ([`is_antipodally_symmetric`]); when it is, it fixes the pivot
1606/// to `false` WLOG and prunes the `true` branch — soundly, since the residual's models come in antipodal
1607/// pairs. A disjoint union of self-complementary blocks keeps regaining the symmetry as each block's
1608/// first variable is fixed, so the break fires *recursively*, collapsing one factor of 2 per block.
1609pub fn search_cost_antipodal(num_vars: usize, clauses: &[Vec<Lit>], budget: usize) -> SearchCost {
1610    let mut nodes = 0usize;
1611    match antipodal_rec(clauses, vec![None; num_vars], budget, &mut nodes) {
1612        Some(sat) => SearchCost::Decided { sat, nodes },
1613        None => SearchCost::Exceeded { budget },
1614    }
1615}
1616
1617fn antipodal_rec(
1618    clauses: &[Vec<Lit>],
1619    assignment: Vec<Option<bool>>,
1620    budget: usize,
1621    nodes: &mut usize,
1622) -> Option<bool> {
1623    *nodes += 1;
1624    if *nodes > budget {
1625        return None;
1626    }
1627    let residual = restrict(clauses, &assignment);
1628    if residual.iter().any(|c| c.is_empty()) {
1629        return Some(false);
1630    }
1631    if residual.is_empty() {
1632        return Some(true);
1633    }
1634    let pivot = residual[0][0].var() as usize;
1635    // When the residual is antipodally symmetric, the `true` branch mirrors the `false` one — prune it.
1636    let values: &[bool] = if is_antipodally_symmetric(&residual) {
1637        &[false]
1638    } else {
1639        &[false, true]
1640    };
1641    for &value in values {
1642        let mut next = assignment.clone();
1643        next[pivot] = Some(value);
1644        match antipodal_rec(clauses, next, budget, nodes) {
1645            Some(true) => return Some(true),
1646            Some(false) => {}
1647            None => return None,
1648        }
1649    }
1650    Some(false)
1651}
1652
1653fn cost_rec(
1654    clauses: &[Vec<Lit>],
1655    assignment: Vec<Option<bool>>,
1656    use_cut: bool,
1657    budget: usize,
1658    nodes: &mut usize,
1659) -> Option<bool> {
1660    *nodes += 1;
1661    if *nodes > budget {
1662        return None;
1663    }
1664    let residual = restrict(clauses, &assignment);
1665    if residual.iter().any(|c| c.is_empty()) {
1666        return Some(false);
1667    }
1668    if residual.is_empty() {
1669        return Some(true);
1670    }
1671    if use_cut {
1672        if let Some(e) = clauses_to_expr(&residual) {
1673            if crate::pigeonhole::decide_pigeonhole_unsat(&e)
1674                || crate::xorsat::refute_via_parity(&e)
1675                || crate::pseudo_boolean::refute_clausal(&e)
1676            {
1677                return Some(false);
1678            }
1679        }
1680    }
1681    let Some(pivot) = assignment.iter().position(|a| a.is_none()) else {
1682        return Some(true);
1683    };
1684    for value in [false, true] {
1685        let mut next = assignment.clone();
1686        next[pivot] = Some(value);
1687        match cost_rec(clauses, next, use_cut, budget, nodes) {
1688            Some(true) => return Some(true),
1689            Some(false) => {}
1690            None => return None,
1691        }
1692    }
1693    Some(false)
1694}
1695
1696fn ladder_sym(
1697    clauses: &[Vec<Lit>],
1698    assignment: Vec<Option<bool>>,
1699    depth: usize,
1700    generators: &[Perm],
1701    use_cut: bool,
1702    stats: &mut LadderStats,
1703) -> bool {
1704    stats.nodes += 1;
1705    stats.max_depth = stats.max_depth.max(depth);
1706    let residual = restrict(clauses, &assignment);
1707    if residual.iter().any(|c| c.is_empty()) {
1708        return false;
1709    }
1710    if residual.is_empty() {
1711        return true;
1712    }
1713    if use_cut {
1714        if let Some(e) = clauses_to_expr(&residual) {
1715            if crate::pigeonhole::decide_pigeonhole_unsat(&e)
1716                || crate::xorsat::refute_via_parity(&e)
1717                || crate::pseudo_boolean::refute_clausal(&e)
1718            {
1719                stats.cut_closures += 1;
1720                return false;
1721            }
1722        }
1723    }
1724    // Branch the lowest-index undecided variable (index order is what makes lex-leader sound).
1725    let Some(pivot) = assignment.iter().position(|a| a.is_none()) else {
1726        return true;
1727    };
1728    for value in [false, true] {
1729        let mut next = assignment.clone();
1730        next[pivot] = Some(value);
1731        if violates_lex_leader(&next, generators) {
1732            stats.pruned += 1;
1733            continue; // a symmetric, lex-smaller assignment is explored on an earlier branch
1734        }
1735        if ladder_sym(clauses, next, depth + 1, generators, use_cut, stats) {
1736            return true;
1737        }
1738    }
1739    false
1740}
1741
1742/// Does some generator map the decided prefix of `a` to a lexicographically *smaller* decided
1743/// assignment over the same decided set? If so, `a` is not the lex-leader of its orbit and may be
1744/// pruned. Sound: an automorphism decreasing `a` proves the leader is strictly below `a`. (Checking
1745/// generators, not the whole group, only prunes *less* — never unsoundly.)
1746fn violates_lex_leader(a: &[Option<bool>], generators: &[Perm]) -> bool {
1747    let n = a.len();
1748    for sigma in generators {
1749        let mut b = vec![None; n];
1750        for v in 0..n {
1751            if let Some(val) = a[v] {
1752                let image = sigma.apply(Lit::pos(v as u32));
1753                b[image.var() as usize] = Some(if image.is_positive() { val } else { !val });
1754            }
1755        }
1756        // Only compare when σ keeps the decided set fixed (a clean restricted comparison).
1757        if (0..n).any(|v| a[v].is_some() != b[v].is_some()) {
1758            continue;
1759        }
1760        // Lexicographic compare b against a; prune iff b < a (false < true at the first difference).
1761        for v in 0..n {
1762            if let (Some(av), Some(bv)) = (a[v], b[v]) {
1763                if av != bv {
1764                    if !bv {
1765                        return true;
1766                    }
1767                    break;
1768                }
1769            }
1770        }
1771    }
1772    false
1773}
1774
1775fn ladder(
1776    clauses: &[Vec<Lit>],
1777    assignment: Vec<Option<bool>>,
1778    depth: usize,
1779    stats: &mut LadderStats,
1780) -> bool {
1781    stats.nodes += 1;
1782    stats.max_depth = stats.max_depth.max(depth);
1783    let residual = restrict(clauses, &assignment);
1784    if residual.iter().any(|c| c.is_empty()) {
1785        return false; // an empty clause: this subcube is fully covered — UNSAT branch
1786    }
1787    if residual.is_empty() {
1788        return true; // nothing left to cover: a corner escapes — SAT
1789    }
1790    // Unit propagation: a forced literal reduces the free dimension with no branching.
1791    if let Some(unit) = residual.iter().find(|c| c.len() == 1) {
1792        let l = unit[0];
1793        let mut next = assignment.clone();
1794        next[l.var() as usize] = Some(l.is_positive());
1795        return ladder(clauses, next, depth + 1, stats);
1796    }
1797    // Cut: a certified shadow crushes the whole subcube if it recognizes the residual.
1798    if let Some(e) = clauses_to_expr(&residual) {
1799        if crate::pigeonhole::decide_pigeonhole_unsat(&e)
1800            || crate::xorsat::refute_via_parity(&e)
1801            || crate::pseudo_boolean::refute_clausal(&e)
1802        {
1803            stats.cut_closures += 1;
1804            return false;
1805        }
1806    }
1807    // Branch: split on a residual variable and ladder down (residual clauses are width ≥ 2 here).
1808    let pivot = residual[0][0].var() as usize;
1809    for value in [false, true] {
1810        let mut next = assignment.clone();
1811        next[pivot] = Some(value);
1812        if ladder(clauses, next, depth + 1, stats) {
1813            return true;
1814        }
1815    }
1816    false
1817}
1818
1819/// The verdict of auto-cutting a cover: which certified cut showed it total (no corner escapes), or
1820/// that a corner escapes (satisfiable), or that it is not a cover the prover decides.
1821#[derive(Clone, Debug, PartialEq, Eq)]
1822pub enum CoverVerdict {
1823    /// Total cover — UNSAT, every corner blocked. `cut` names the structured hyperplane family that
1824    /// certified it in polynomial time (counting / parity / cutting-planes), or `None` when the general
1825    /// certified prover (symmetry-broken CDCL → RUP) closed it.
1826    Total { cut: Option<Shadow> },
1827    /// A corner escapes the cover — satisfiable.
1828    Escapes,
1829    /// Not a propositional cover the prover handles.
1830    Unknown,
1831}
1832
1833impl Cover {
1834    /// **Auto-cut and crush.** Try each certified cut in turn — the counting hyperplane (Hall), the
1835    /// affine GF(2) cut (Gaussian), the cardinality cutting plane (Farkas) — and fall back to the
1836    /// general certified prover if no structured cut fits. One call, every family: it reports which
1837    /// hyperplane family closed the cover, or that a corner escapes. This is the whole campaign behind
1838    /// a single door — and it is exactly `sat::prove_unsat`'s cascade, surfaced with the cut it used.
1839    pub fn auto_certify(&self) -> CoverVerdict {
1840        let Some(e) = self.to_expr() else {
1841            return CoverVerdict::Unknown;
1842        };
1843        if crate::pigeonhole::decide_pigeonhole_unsat(&e) {
1844            return CoverVerdict::Total {
1845                cut: Some(Shadow::Counting),
1846            };
1847        }
1848        if crate::xorsat::refute_via_parity(&e) {
1849            return CoverVerdict::Total {
1850                cut: Some(Shadow::Parity),
1851            };
1852        }
1853        if crate::pseudo_boolean::refute_clausal(&e) {
1854            return CoverVerdict::Total {
1855                cut: Some(Shadow::CuttingPlanes),
1856            };
1857        }
1858        match crate::sat::prove_unsat(&e) {
1859            crate::sat::UnsatOutcome::Refuted => CoverVerdict::Total { cut: None },
1860            crate::sat::UnsatOutcome::Sat(_) => CoverVerdict::Escapes,
1861            crate::sat::UnsatOutcome::Unsupported => CoverVerdict::Unknown,
1862        }
1863    }
1864}
1865
1866/// The abstract signature of a family: its rules symmetry-broken to their orbit *types*, and which
1867/// certified shadow (if any) refutes it. This is the auto-collapse spread across families — the same
1868/// machinery that found pigeonhole's two-type counting abstraction, applied blind to any cover.
1869#[derive(Clone, Debug, PartialEq, Eq)]
1870pub struct FamilySignature {
1871    pub num_vars: usize,
1872    pub clauses: usize,
1873    pub rule_types: usize,
1874    pub shadow: Option<Shadow>,
1875}
1876
1877/// Symmetry-break any cover to its abstract signature: discover its automorphisms, quotient the rules
1878/// to orbit-types ([`clause_orbits`]), and probe the certified shadows in turn — counting, then parity,
1879/// then cutting-planes. `shadow = None` means no shadow recognizes it (it falls through to the general
1880/// certified CDCL core). A maximally symmetric family collapses to a few rule-types decided by one
1881/// shadow; an unstructured one spreads across many types with no shadow — but still has a backdoor.
1882pub fn abstract_signature(num_vars: usize, clauses: &[Vec<Lit>]) -> FamilySignature {
1883    let generators = crate::symmetry_detect::find_generators(num_vars, clauses);
1884    let rule_types = clause_orbits(clauses, &generators).len();
1885    let shadow = clauses_to_expr(clauses).and_then(|e| {
1886        if crate::pigeonhole::decide_pigeonhole_unsat(&e) {
1887            Some(Shadow::Counting)
1888        } else if crate::xorsat::refute_via_parity(&e) {
1889            Some(Shadow::Parity)
1890        } else if crate::pseudo_boolean::refute_clausal(&e) {
1891            Some(Shadow::CuttingPlanes)
1892        } else {
1893            None
1894        }
1895    });
1896    FamilySignature {
1897        num_vars,
1898        clauses: clauses.len(),
1899        rule_types,
1900        shadow,
1901    }
1902}
1903
1904// ---- There is no such thing as random: backdoors to easy classes -------------------------------
1905//
1906// A "statistically random" instance is, once generated, a fixed deterministic object with definite
1907// structure — it merely lacks an obvious *global* symmetry. Its structure is *local*: a small set of
1908// variables (a **backdoor**) whose every fixing collapses the residual into a polynomially-decidable
1909// class. Hardness without a clean global symmetry is not noise; it is unfound structure. These
1910// primitives find that structure and use it — `2^k` easy branches instead of a `2ⁿ` search — which is
1911// also exactly how symmetry breaking buys *speed*, not just classification.
1912
1913/// The residual CNF after fixing variables: `assignment[v] = Some(b)` fixes `v`, `None` leaves it
1914/// free. Clauses satisfied by a fixed literal are dropped; falsified literals are removed. An empty
1915/// clause in the result means the restriction already falsifies the formula.
1916pub fn restrict(clauses: &[Vec<Lit>], assignment: &[Option<bool>]) -> Vec<Vec<Lit>> {
1917    let mut out = Vec::new();
1918    'clause: for c in clauses {
1919        let mut residual = Vec::new();
1920        for &l in c {
1921            match assignment.get(l.var() as usize).copied().flatten() {
1922                Some(value) => {
1923                    if value == l.is_positive() {
1924                        continue 'clause; // a fixed literal satisfies the clause — drop it
1925                    }
1926                    // otherwise the literal is falsified — omit it from the residual
1927                }
1928                None => residual.push(l),
1929            }
1930        }
1931        out.push(residual);
1932    }
1933    out
1934}
1935
1936fn to_twosat_lit(l: Lit) -> crate::twosat::Lit {
1937    if l.is_positive() {
1938        crate::twosat::Lit::pos(l.var() as usize)
1939    } else {
1940        crate::twosat::Lit::neg(l.var() as usize)
1941    }
1942}
1943
1944/// Decide a width-≤2 CNF in polynomial time via the 2-SAT SCC solver. `true` = satisfiable. An empty
1945/// clause forces UNSAT. Panics if handed a clause wider than 2 (not a 2-SAT instance).
1946pub fn decide_2sat(clauses: &[Vec<Lit>], num_vars: usize) -> bool {
1947    let mut pairs = Vec::with_capacity(clauses.len());
1948    for c in clauses {
1949        match c.as_slice() {
1950            [] => return false,
1951            [a] => pairs.push((to_twosat_lit(*a), to_twosat_lit(*a))),
1952            [a, b] => pairs.push((to_twosat_lit(*a), to_twosat_lit(*b))),
1953            _ => panic!("decide_2sat given a width-{} clause", c.len()),
1954        }
1955    }
1956    matches!(
1957        crate::twosat::solve(&pairs, num_vars),
1958        crate::twosat::TwoSatOutcome::Sat(_)
1959    )
1960}
1961
1962/// Greedily find a **backdoor to 2-SAT**: a set of variables `U` such that every clause has at most
1963/// two literals outside `U`. Then under *any* assignment to `U`, each clause is either satisfied or
1964/// shrinks to width ≤ 2, so the residual is 2-SAT — poly-decidable. Built by repeatedly fixing the
1965/// variable that appears in the most still-too-wide clauses (a hitting set of the wide clauses).
1966pub fn greedy_2sat_backdoor(clauses: &[Vec<Lit>], num_vars: usize) -> Vec<usize> {
1967    let mut chosen = vec![false; num_vars];
1968    let mut backdoor = Vec::new();
1969    loop {
1970        let mut freq = vec![0usize; num_vars];
1971        let mut any_wide = false;
1972        for c in clauses {
1973            let free = c.iter().filter(|l| !chosen[l.var() as usize]).count();
1974            if free > 2 {
1975                any_wide = true;
1976                for l in c {
1977                    if !chosen[l.var() as usize] {
1978                        freq[l.var() as usize] += 1;
1979                    }
1980                }
1981            }
1982        }
1983        if !any_wide {
1984            break;
1985        }
1986        let best = (0..num_vars).max_by_key(|&v| freq[v]).unwrap();
1987        chosen[best] = true;
1988        backdoor.push(best);
1989    }
1990    backdoor.sort_unstable();
1991    backdoor
1992}
1993
1994/// Verify `U` is a **strong** backdoor to 2-SAT by enumeration: every one of the `2^{|U|}` assignments
1995/// to `U` yields a residual of width ≤ 2. Bounded to `|U| ≤ 24` (the enumeration guard).
1996pub fn is_strong_backdoor_to_2sat(
1997    clauses: &[Vec<Lit>],
1998    num_vars: usize,
1999    backdoor: &[usize],
2000) -> bool {
2001    let k = backdoor.len();
2002    if k > 24 {
2003        return false;
2004    }
2005    for mask in 0u32..(1u32 << k) {
2006        let mut assignment = vec![None; num_vars];
2007        for (i, &v) in backdoor.iter().enumerate() {
2008            assignment[v] = Some(mask & (1 << i) != 0);
2009        }
2010        if restrict(clauses, &assignment).iter().any(|c| c.len() > 2) {
2011            return false;
2012        }
2013    }
2014    true
2015}
2016
2017/// Decide satisfiability through a 2-SAT backdoor: the instance is satisfiable iff *some* fixing of
2018/// `U` leaves a satisfiable 2-SAT residual. This solves in `2^{|U|}` polynomial branches instead of a
2019/// `2ⁿ` search — the structure (the backdoor) turned an exponential into a small, easy fan-out. `U`
2020/// must be a strong backdoor to 2-SAT (every residual width ≤ 2).
2021pub fn decide_sat_via_2sat_backdoor(
2022    clauses: &[Vec<Lit>],
2023    num_vars: usize,
2024    backdoor: &[usize],
2025) -> bool {
2026    for mask in 0u32..(1u32 << backdoor.len()) {
2027        let mut assignment = vec![None; num_vars];
2028        for (i, &v) in backdoor.iter().enumerate() {
2029            assignment[v] = Some(mask & (1 << i) != 0);
2030        }
2031        let residual = restrict(clauses, &assignment);
2032        if decide_2sat(&residual, num_vars) {
2033            return true;
2034        }
2035    }
2036    false
2037}
2038
2039/// The orbit representative (canonical form) of a blocker under a generating set: the lexicographically
2040/// minimal blocker reachable through the generators. Two blockers are symmetric iff they share a
2041/// canonical form, so canonicalizing is how a symmetry-aware engine dedups derived rules by orbit.
2042pub fn canonical_blocker(b: &Subcube, generators: &[CubeSym]) -> Subcube {
2043    let mut best = *b;
2044    let mut seen = BTreeSet::new();
2045    seen.insert(*b);
2046    let mut stack = vec![*b];
2047    while let Some(x) = stack.pop() {
2048        for g in generators {
2049            let y = g.map_subcube(&x);
2050            if seen.insert(y) {
2051                if y < best {
2052                    best = y;
2053                }
2054                stack.push(y);
2055            }
2056        }
2057    }
2058    best
2059}
2060
2061/// The full orbit of a blocker under the group generated by `generators` (BFS over images). For a
2062/// structured family this is *polynomial*-sized even though `|G|` is astronomical, because the
2063/// blocker's stabilizer is huge (a pigeonhole exclusion has orbit `holes·C(pigeons,2)`, not `|G|`).
2064pub fn blocker_orbit(b: &Subcube, generators: &[CubeSym]) -> Vec<Subcube> {
2065    let mut seen = BTreeSet::new();
2066    seen.insert(*b);
2067    let mut stack = vec![*b];
2068    while let Some(x) = stack.pop() {
2069        for g in generators {
2070            let y = g.map_subcube(&x);
2071            if seen.insert(y) {
2072                stack.push(y);
2073            }
2074        }
2075    }
2076    seen.into_iter().collect()
2077}
2078
2079/// Symmetric resolution closure on orbit *representatives*: resolve each representative against every
2080/// image in another representative's orbit. Since resolution commutes with symmetry — `σ(resolve(c,d))
2081/// = resolve(σc,σd)` — this captures every derivable rule up to symmetry without building the raw
2082/// exponential closure. Returns the saturated count of orbit-types and whether the empty clause (a
2083/// refutation) was derived, bounded by `max_rounds` and a `max_reps` size guard.
2084///
2085/// **Measured limit (honest):** this refutes PHP(3) at 12 orbit-types but does **not** scale — at
2086/// PHP(4) the symmetric closure already explodes past tens of thousands of types. Even quotiented by
2087/// symmetry, the *full* resolution closure is the wrong abstraction; the `max_reps` guard makes it fail
2088/// safe rather than run away. The scalable path is [`pigeonhole_abstract_refutation`] — lift to the
2089/// rule-type level and apply the counting invariant, not the closure.
2090pub fn symmetric_resolution_closure(
2091    cover: &Cover,
2092    generators: &[CubeSym],
2093    max_rounds: usize,
2094    max_reps: usize,
2095) -> (usize, bool) {
2096    let empty = Subcube {
2097        n: cover.n,
2098        care: 0,
2099        value: 0,
2100    };
2101    let mut reps: BTreeSet<Subcube> = cover
2102        .blockers
2103        .iter()
2104        .map(|b| canonical_blocker(b, generators))
2105        .collect();
2106    let mut refuted = reps.contains(&empty);
2107    for _ in 0..max_rounds {
2108        if refuted {
2109            break;
2110        }
2111        let current: Vec<Subcube> = reps.iter().copied().collect();
2112        let orbits: Vec<Vec<Subcube>> = current
2113            .iter()
2114            .map(|d| blocker_orbit(d, generators))
2115            .collect();
2116        let mut added = false;
2117        'outer: for c in &current {
2118            for orbit in &orbits {
2119                for image in orbit {
2120                    if let Some((_, r)) = c.resolve(image) {
2121                        let canon = canonical_blocker(&r, generators);
2122                        if reps.insert(canon) {
2123                            added = true;
2124                            if canon == empty {
2125                                refuted = true;
2126                                break 'outer;
2127                            }
2128                            if reps.len() > max_reps {
2129                                break 'outer;
2130                            }
2131                        }
2132                    }
2133                }
2134            }
2135        }
2136        if !added {
2137            break;
2138        }
2139    }
2140    (reps.len(), refuted)
2141}
2142
2143/// **Symmetric resolution closure — rules beget rules, collapsed by symmetry.** From a cover's
2144/// blockers, repeatedly resolve all pairs (each resolvent a new rule) and record, per round, both the
2145/// raw count of distinct derived rules and the count of their *orbit representatives* under the
2146/// automorphism group. The widening gap between the two is the symmetry collapse of the resolution
2147/// proof: raw resolution explodes, but modulo symmetry only a handful of essentially-distinct rules
2148/// are ever derived — the geometric reason symmetric proof systems refute pigeonhole in polynomial
2149/// size where plain resolution cannot.
2150pub fn symmetric_resolution_growth(
2151    cover: &Cover,
2152    generators: &[CubeSym],
2153    rounds: usize,
2154) -> Vec<(usize, usize)> {
2155    let mut raw: BTreeSet<Subcube> = cover.blockers.iter().copied().collect();
2156    let mut out = Vec::new();
2157    for _ in 0..rounds {
2158        let current: Vec<Subcube> = raw.iter().copied().collect();
2159        for i in 0..current.len() {
2160            for j in (i + 1)..current.len() {
2161                if let Some((_, r)) = current[i].resolve(&current[j]) {
2162                    raw.insert(r);
2163                }
2164            }
2165        }
2166        let orbits: BTreeSet<Subcube> = raw
2167            .iter()
2168            .map(|b| canonical_blocker(b, generators))
2169            .collect();
2170        out.push((raw.len(), orbits.len()));
2171    }
2172    out
2173}
2174
2175/// **Symmetry breaking for speed.** Count the orbits of the `2^{|U|}` backdoor branches (assignments
2176/// to `U`) under the generators that preserve `U` setwise. A symmetry-aware solver inspects one branch
2177/// per orbit instead of all `2^{|U|}` — fewer poly-time solves for the same verdict. Generators that
2178/// move `U` off itself do not act on the branches and are skipped; each kept generator induces a
2179/// permutation-with-flips on the backdoor positions.
2180pub fn backdoor_branch_orbit_count(backdoor: &[usize], generators: &[Perm]) -> u64 {
2181    let k = backdoor.len();
2182    let position: HashMap<usize, usize> =
2183        backdoor.iter().enumerate().map(|(i, &v)| (v, i)).collect();
2184    let mut induced: Vec<(Vec<usize>, u32)> = Vec::new();
2185    for g in generators {
2186        let mut perm = vec![0usize; k];
2187        let mut flip = 0u32;
2188        let mut preserves = true;
2189        for (i, &v) in backdoor.iter().enumerate() {
2190            let image = g.apply(Lit::pos(v as u32));
2191            match position.get(&(image.var() as usize)) {
2192                Some(&j) => {
2193                    perm[i] = j;
2194                    if !image.is_positive() {
2195                        flip |= 1 << j;
2196                    }
2197                }
2198                None => {
2199                    preserves = false;
2200                    break;
2201                }
2202            }
2203        }
2204        if preserves {
2205            induced.push((perm, flip));
2206        }
2207    }
2208    let total = 1u32 << k;
2209    let mut seen = vec![false; total as usize];
2210    let mut orbits = 0u64;
2211    for start in 0..total {
2212        if seen[start as usize] {
2213            continue;
2214        }
2215        orbits += 1;
2216        let mut stack = vec![start];
2217        seen[start as usize] = true;
2218        while let Some(m) = stack.pop() {
2219            for (perm, flip) in &induced {
2220                let mut image = 0u32;
2221                for i in 0..k {
2222                    if m & (1 << i) != 0 {
2223                        image |= 1 << perm[i];
2224                    }
2225                }
2226                image ^= flip;
2227                if !seen[image as usize] {
2228                    seen[image as usize] = true;
2229                    stack.push(image);
2230                }
2231            }
2232        }
2233    }
2234    orbits
2235}
2236
2237/// Build the CNF `ProofExpr` over atoms `x{var}` from raw clauses — the door into the certified
2238/// prover, scalable (no cube). `None` on an empty clause or empty formula.
2239pub fn clauses_to_expr(clauses: &[Vec<Lit>]) -> Option<crate::ProofExpr> {
2240    use crate::ProofExpr;
2241    let lit = |l: &Lit| {
2242        let a = ProofExpr::Atom(format!("x{}", l.var()));
2243        if l.is_positive() {
2244            a
2245        } else {
2246            ProofExpr::Not(Box::new(a))
2247        }
2248    };
2249    // Combine `nodes` into a BALANCED binary tree (depth O(log n)) rather than a linear left spine, so a
2250    // flat CNF's connective tree is logarithmically deep. Every recursive walker over it (clause
2251    // collectors, clausifiers, evaluators) then recurses O(log n) deep and cannot overflow the stack on
2252    // a several-thousand-clause formula — the pathological structure simply is never built.
2253    fn balanced(
2254        mut nodes: Vec<ProofExpr>,
2255        combine: impl Fn(Box<ProofExpr>, Box<ProofExpr>) -> ProofExpr,
2256    ) -> ProofExpr {
2257        while nodes.len() > 1 {
2258            let mut next = Vec::with_capacity((nodes.len() + 1) / 2);
2259            let mut it = nodes.into_iter();
2260            while let Some(a) = it.next() {
2261                match it.next() {
2262                    Some(b) => next.push(combine(Box::new(a), Box::new(b))),
2263                    None => next.push(a),
2264                }
2265            }
2266            nodes = next;
2267        }
2268        nodes
2269            .into_iter()
2270            .next()
2271            .expect("balanced() requires a non-empty node list")
2272    }
2273    let mut built = Vec::with_capacity(clauses.len());
2274    for c in clauses {
2275        if c.is_empty() {
2276            return None;
2277        }
2278        let lits: Vec<ProofExpr> = c.iter().map(|l| lit(l)).collect();
2279        built.push(balanced(lits, |a, b| ProofExpr::Or(a, b)));
2280    }
2281    if built.is_empty() {
2282        return None;
2283    }
2284    Some(balanced(built, |a, b| crate::ProofExpr::And(a, b)))
2285}
2286
2287/// A hypercube symmetry: permute coordinates, then optionally flip each one (`Pnp.lean`'s
2288/// `CubeSymmetry`). `perm[j]` is the coordinate that `j`'s value lands on; `flip[j]` negates it.
2289/// These are the automorphisms that move blockers among blockers and corners among corners with the
2290/// **same** action — the bridge that puts rules and solutions in one mathematical world.
2291#[derive(Clone, Debug)]
2292pub struct CubeSym {
2293    pub perm: Vec<usize>,
2294    pub flip: Vec<bool>,
2295}
2296
2297impl CubeSym {
2298    /// The identity symmetry on `n` coordinates.
2299    pub fn identity(n: usize) -> CubeSym {
2300        CubeSym {
2301            perm: (0..n).collect(),
2302            flip: vec![false; n],
2303        }
2304    }
2305
2306    /// Push a corner forward through the symmetry (`mapVertex`): coordinate `j`'s (possibly flipped)
2307    /// value moves to coordinate `perm[j]`.
2308    pub fn map_corner(&self, c: Corner) -> Corner {
2309        let mut out = 0u64;
2310        for j in 0..self.perm.len() {
2311            let mut bit = (c >> j) & 1;
2312            if self.flip[j] {
2313                bit ^= 1;
2314            }
2315            out |= bit << self.perm[j];
2316        }
2317        out
2318    }
2319
2320    /// Push a blocker forward through the symmetry (`mapBlocker`): each fixed coordinate `j` moves
2321    /// to `perm[j]`, its required value flipped when `flip[j]`.
2322    pub fn map_subcube(&self, s: &Subcube) -> Subcube {
2323        let mut care = 0u64;
2324        let mut value = 0u64;
2325        for j in 0..self.perm.len() {
2326            if s.care & (1u64 << j) != 0 {
2327                let pj = self.perm[j];
2328                care |= 1u64 << pj;
2329                let mut bit = (s.value >> j) & 1;
2330                if self.flip[j] {
2331                    bit ^= 1;
2332                }
2333                value |= bit << pj;
2334            }
2335        }
2336        Subcube {
2337            n: s.n,
2338            care,
2339            value,
2340        }
2341    }
2342
2343    /// Act on a *fractional* point of the cube `[0,1]ⁿ`: coordinate `j`'s value (flipped to `1−x` when
2344    /// `flip[j]`) lands on coordinate `perm[j]`. The linear extension of `map_corner` to the solid cube.
2345    pub fn map_fractional(&self, point: &[f64]) -> Vec<f64> {
2346        let mut out = vec![0.0; self.perm.len()];
2347        for j in 0..self.perm.len() {
2348            out[self.perm[j]] = if self.flip[j] {
2349                1.0 - point[j]
2350            } else {
2351                point[j]
2352            };
2353        }
2354        out
2355    }
2356
2357    /// Compose two cube symmetries: `(self ∘ other)` applies `other` then `self`.
2358    pub fn compose(&self, other: &CubeSym) -> CubeSym {
2359        let n = self.perm.len();
2360        let mut perm = vec![0usize; n];
2361        let mut flip = vec![false; n];
2362        for j in 0..n {
2363            let mid = other.perm[j];
2364            perm[j] = self.perm[mid];
2365            flip[j] = other.flip[j] ^ self.flip[mid];
2366        }
2367        CubeSym { perm, flip }
2368    }
2369
2370    /// Is this symmetry an **automorphism** of the cover — does it map the blocker *set* onto
2371    /// itself? Re-verified directly (the soundness check), exactly as `swap_is_automorphism` is for
2372    /// the clausal path: a finder that proposes a non-automorphism is caught here, never trusted.
2373    pub fn is_automorphism(&self, cover: &Cover) -> bool {
2374        let original: BTreeSet<Subcube> = cover.blockers.iter().copied().collect();
2375        let mapped: BTreeSet<Subcube> =
2376            cover.blockers.iter().map(|b| self.map_subcube(b)).collect();
2377        original == mapped
2378    }
2379}
2380
2381/// The group generated by `generators` (closure under composition) — for small groups, so the
2382/// combinatorial orbit-counting lemma can sum over every element.
2383fn group_closure(generators: &[CubeSym], n: usize) -> Vec<CubeSym> {
2384    let id = CubeSym::identity(n);
2385    let key = |g: &CubeSym| (g.perm.clone(), g.flip.clone());
2386    let mut seen: BTreeSet<(Vec<usize>, Vec<bool>)> = [key(&id)].into_iter().collect();
2387    let mut group = vec![id];
2388    let mut i = 0;
2389    while i < group.len() {
2390        let g = group[i].clone();
2391        i += 1;
2392        for s in generators {
2393            let h = s.compose(&g);
2394            if seen.insert(key(&h)) {
2395                group.push(h);
2396            }
2397        }
2398        if group.len() > 200_000 {
2399            break;
2400        }
2401    }
2402    group
2403}
2404
2405/// **Combinatorics — Burnside's lemma.** The number of corner orbits equals the *average* number of
2406/// corners fixed by a group element: `(1/|G|) Σ_g |Fix(g)|`. A different invariant for the same count the
2407/// orbit-BFS computes — counting by fixed points instead of by walking orbits. (`n ≤ ~16`.)
2408pub fn burnside_corner_orbits(n: usize, generators: &[CubeSym]) -> u64 {
2409    let group = group_closure(generators, n);
2410    let fixed_total: u128 = group
2411        .iter()
2412        .map(|g| {
2413            (0u64..(1u64 << n))
2414                .filter(|&c| g.map_corner(c) == c)
2415                .count() as u128
2416        })
2417        .sum();
2418    (fixed_total / group.len() as u128) as u64
2419}
2420
2421/// **Analysis — the Walsh–Hadamard (Fourier) spectrum.** Expand the cover's vertex-energy function over
2422/// the cube's characters `χ_S(x) = (-1)^{⟨S,x⟩}`: `f̂(S) = 2⁻ⁿ Σ_x energy(x) χ_S(x)`. Harmonic analysis on
2423/// the hypercube — the coefficients are the analytic invariant. (`n ≤ ~16`.)
2424pub fn walsh_hadamard_energy(cover: &Cover) -> Vec<f64> {
2425    let size = 1usize << cover.n;
2426    let f: Vec<f64> = (0..size as u64)
2427        .map(|x| cover.vertex_energy(x) as f64)
2428        .collect();
2429    (0..size)
2430        .map(|s| {
2431            let acc: f64 = (0..size)
2432                .map(|x| {
2433                    if ((s & x) as u64).count_ones() % 2 == 0 {
2434                        f[x]
2435                    } else {
2436                        -f[x]
2437                    }
2438                })
2439                .sum();
2440            acc / size as f64
2441        })
2442        .collect()
2443}
2444
2445/// **Geometry — the f-vector.** The number of blockers of each face dimension. A symmetry permutes
2446/// blockers among themselves but preserves each one's dimension, so the f-vector is a geometric invariant
2447/// of the cover (the discrete analog of a polytope's face counts).
2448pub fn face_vector(cover: &Cover) -> std::collections::BTreeMap<usize, usize> {
2449    let mut fv = std::collections::BTreeMap::new();
2450    for b in &cover.blockers {
2451        *fv.entry(b.dimension()).or_insert(0) += 1;
2452    }
2453    fv
2454}
2455
2456/// Orbit partition of the `2ⁿ` corners under a set of generators, each a verified automorphism.
2457/// Returns one representative per orbit (the orbit-collapsed corner set the cover check needs).
2458/// Materializes a `2ⁿ` seen-bitmap, so this is itself bounded by the hypercube size — it *measures*
2459/// the collapse rather than escaping it; the counting/parity shadows are what decide totality
2460/// without the `2ⁿ` walk. Honest by construction.
2461pub fn orbit_representatives(n: usize, generators: &[CubeSym]) -> Vec<Corner> {
2462    let total = 1u64 << n;
2463    let mut seen = vec![false; total as usize];
2464    let mut reps = Vec::new();
2465    for start in 0u64..total {
2466        if seen[start as usize] {
2467            continue;
2468        }
2469        reps.push(start);
2470        let mut stack = vec![start];
2471        seen[start as usize] = true;
2472        while let Some(c) = stack.pop() {
2473            for g in generators {
2474                let d = g.map_corner(c);
2475                if !seen[d as usize] {
2476                    seen[d as usize] = true;
2477                    stack.push(d);
2478                }
2479            }
2480        }
2481    }
2482    reps
2483}
2484
2485/// How many orbits the corners fall into under these generators.
2486pub fn orbit_count(n: usize, generators: &[CubeSym]) -> u64 {
2487    orbit_representatives(n, generators).len() as u64
2488}
2489
2490/// The **symmetry-broken** cover-totality check: when every generator is a verified automorphism,
2491/// the cover is total iff it covers one representative per orbit. Same verdict as [`Cover::is_total`],
2492/// but it inspects `orbit_count` corners instead of `2ⁿ`. `None` (fail-closed) when some generator is
2493/// not actually an automorphism — never a guessed answer.
2494pub fn is_total_via_orbits(cover: &Cover, generators: &[CubeSym]) -> Option<bool> {
2495    if !generators.iter().all(|g| g.is_automorphism(cover)) {
2496        return None;
2497    }
2498    let reps = orbit_representatives(cover.n, generators);
2499    Some(reps.iter().all(|&c| cover.blocks(c)))
2500}
2501
2502/// One step of the collapse curve: how many orbits remain after stacking the first `k` generators.
2503#[derive(Clone, Copy, Debug, PartialEq, Eq)]
2504pub struct CollapseStep {
2505    pub generators_used: usize,
2506    pub orbits: u64,
2507}
2508
2509/// Stack the generators one at a time and record how the orbit count shrinks — the executable answer
2510/// to "how much does each symmetry break cut the problem?" Begins at `2ⁿ` (no symmetry) and descends
2511/// as generators compose. The ratios are *measured*, not asserted.
2512pub fn collapse_curve(n: usize, generators: &[CubeSym]) -> Vec<CollapseStep> {
2513    let mut steps = Vec::with_capacity(generators.len() + 1);
2514    steps.push(CollapseStep {
2515        generators_used: 0,
2516        orbits: 1u64 << n,
2517    });
2518    for k in 1..=generators.len() {
2519        steps.push(CollapseStep {
2520            generators_used: k,
2521            orbits: orbit_count(n, &generators[..k]),
2522        });
2523    }
2524    steps
2525}
2526
2527/// The pigeonhole cover: `n` pigeons into `n-1` holes. Variable `(p,h)` ("pigeon `p` in hole `h`")
2528/// lives at index `p*(n-1)+h`, matching [`crate::families::php`]. Always buildable, always UNSAT.
2529pub fn php_cover(n: usize) -> Cover {
2530    let (cnf, _) = crate::families::php(n);
2531    Cover::of_cnf(&cnf)
2532}
2533
2534/// The generating symmetries of the pigeonhole cover: adjacent transpositions of pigeons (rows) and
2535/// of holes (columns). Together they generate the full grid symmetry group `Sₙ × Sₙ₋₁` — pure
2536/// coordinate permutations (no phase flips). Each is a [`CubeSym`] over the `n*(n-1)` grid variables.
2537pub fn php_symmetries(n: usize) -> Vec<CubeSym> {
2538    let holes = n.saturating_sub(1);
2539    let num_vars = n * holes;
2540    let var = |p: usize, h: usize| p * holes + h;
2541    let mut gens = Vec::new();
2542    // Adjacent pigeon (row) swaps.
2543    for p in 0..n.saturating_sub(1) {
2544        let mut perm: Vec<usize> = (0..num_vars).collect();
2545        for h in 0..holes {
2546            perm.swap(var(p, h), var(p + 1, h));
2547        }
2548        gens.push(CubeSym {
2549            perm,
2550            flip: vec![false; num_vars],
2551        });
2552    }
2553    // Adjacent hole (column) swaps.
2554    for h in 0..holes.saturating_sub(1) {
2555        let mut perm: Vec<usize> = (0..num_vars).collect();
2556        for p in 0..n {
2557            perm.swap(var(p, h), var(p, h + 1));
2558        }
2559        gens.push(CubeSym {
2560            perm,
2561            flip: vec![false; num_vars],
2562        });
2563    }
2564    gens
2565}
2566
2567/// Generators of the full **hyperoctahedral group** `Bₙ = (ℤ/2)ⁿ ⋊ Sₙ` — the signed permutations,
2568/// the automorphism group of the `n`-cube and the *complete* clause-level symmetry: every [`CubeSym`]
2569/// is one of its elements. The `n−1` adjacent coordinate transpositions generate `Sₙ`; the single
2570/// coordinate-0 flip, conjugated by those, generates the `(ℤ/2)ⁿ` of phase flips; together they
2571/// generate all of `Bₙ`. The [`cube_group_closure`] of these has order exactly `2ⁿ·n!`
2572/// (`1, 2, 8, 48, 384, 3840` for `n = 0..=5`). The census quotients minimal covers by this group.
2573pub fn hyperoctahedral_generators(n: usize) -> Vec<CubeSym> {
2574    let mut gens = Vec::new();
2575    for i in 0..n.saturating_sub(1) {
2576        let mut perm: Vec<usize> = (0..n).collect();
2577        perm.swap(i, i + 1);
2578        gens.push(CubeSym {
2579            perm,
2580            flip: vec![false; n],
2581        });
2582    }
2583    if n > 0 {
2584        let mut flip = vec![false; n];
2585        flip[0] = true;
2586        gens.push(CubeSym {
2587            perm: (0..n).collect(),
2588            flip,
2589        });
2590    }
2591    gens
2592}
2593
2594/// The full group generated by `generators`, materialized (closure under composition) — the public
2595/// door onto the otherwise-internal `group_closure`. For the small groups the census needs (`Bₙ`,
2596/// `n ≤ 5` ⇒ `|G| = 3840`) the orbit–stabilizer cross-checks sum over every element.
2597pub fn cube_group_closure(generators: &[CubeSym], n: usize) -> Vec<CubeSym> {
2598    group_closure(generators, n)
2599}
2600
2601/// **The minimum width of a resolution refutation of an UNSAT cover** — the size of the widest clause
2602/// any width-bounded refutation must carry, the classic resolution complexity measure (Ben-Sasson–
2603/// Wigderson). A subcube *is* a clause (`Subcube::clause_literals`) and [`Subcube::resolve`] is the
2604/// geometry of the resolution step; the empty subcube (`care = 0`, the whole cube blocked) is the
2605/// derived contradiction. For width budget `w` we seed with the input blockers of support `≤ w` and
2606/// saturate under width-`≤ w` resolution; the least `w` that derives the empty subcube is the width.
2607/// `None` only if the cover is satisfiable (no refutation at any width); every UNSAT cover succeeds by
2608/// `w = n` since full-width resolution is complete. (For small covers — it enumerates resolvents.)
2609pub fn min_resolution_width(cover: &Cover) -> Option<usize> {
2610    let n = cover.n;
2611    let empty = Subcube {
2612        n,
2613        care: 0,
2614        value: 0,
2615    };
2616    for w in 0..=n {
2617        let mut set: BTreeSet<Subcube> = cover
2618            .blockers
2619            .iter()
2620            .copied()
2621            .filter(|b| b.care.count_ones() as usize <= w)
2622            .collect();
2623        if set.contains(&empty) {
2624            return Some(w);
2625        }
2626        loop {
2627            let snapshot: Vec<Subcube> = set.iter().copied().collect();
2628            let mut added = false;
2629            for i in 0..snapshot.len() {
2630                for j in (i + 1)..snapshot.len() {
2631                    if let Some((_, r)) = snapshot[i].resolve(&snapshot[j]) {
2632                        if r.care.count_ones() as usize <= w && set.insert(r) {
2633                            added = true;
2634                        }
2635                    }
2636                }
2637            }
2638            if set.contains(&empty) {
2639                return Some(w);
2640            }
2641            if !added {
2642                break;
2643            }
2644        }
2645    }
2646    None
2647}
2648
2649/// The lexicographic key of a cover — its sorted blocker list — for orbit canonicalization. Two covers
2650/// are the same set of clauses iff their keys match.
2651fn cover_key(blockers: &[Subcube]) -> Vec<Subcube> {
2652    let mut k = blockers.to_vec();
2653    k.sort_unstable();
2654    k.dedup();
2655    k
2656}
2657
2658/// The canonical key of a cover under a **materialized** group: the lexicographically least sorted
2659/// blocker list over all images `{ g·blockers : g ∈ group }`. A flat `min` over the precomputed group —
2660/// no per-call orbit BFS — so it is cheap enough to evaluate on every node of the orderly-generation
2661/// search. Constant on a `Bₙ` orbit and distinct across orbits, hence a sound orbit invariant.
2662fn canonical_key(blockers: &[Subcube], group: &[CubeSym]) -> Vec<Subcube> {
2663    group
2664        .iter()
2665        .map(|g| {
2666            cover_key(
2667                &blockers
2668                    .iter()
2669                    .map(|b| g.map_subcube(b))
2670                    .collect::<Vec<_>>(),
2671            )
2672        })
2673        .min()
2674        .unwrap_or_else(|| cover_key(blockers))
2675}
2676
2677/// **The `Bₙ`-canonical form of a cover, and its orbit size.** Acts the group on the *whole* cover by
2678/// `g·C = { g.map_subcube(b) }` and returns the lexicographically least sorted-blocker key together with
2679/// the number of distinct covers in the orbit. The canonical key is constant on an orbit and distinct
2680/// across orbits, a sound orbit invariant; the orbit size feeds the orbit–stabilizer identity
2681/// `|Stab| · orbit_size = |Bₙ|`.
2682pub fn canonical_cover(cover: &Cover, generators: &[CubeSym]) -> (Vec<Subcube>, usize) {
2683    let group = group_closure(generators, cover.n);
2684    let images: BTreeSet<Vec<Subcube>> = group
2685        .iter()
2686        .map(|g| {
2687            cover_key(
2688                &cover
2689                    .blockers
2690                    .iter()
2691                    .map(|b| g.map_subcube(b))
2692                    .collect::<Vec<_>>(),
2693            )
2694        })
2695        .collect();
2696    let best = images
2697        .iter()
2698        .next()
2699        .cloned()
2700        .unwrap_or_else(|| cover_key(&cover.blockers));
2701    (best, images.len())
2702}
2703
2704/// **Enumerate every minimal UNSAT cover of the `n`-cube, one canonical representative per `Bₙ` orbit.**
2705/// A minimal cover is a set of subcube blockers that covers every corner (UNSAT) and *none of which is
2706/// droppable* (every blocker privately owns some corner) — i.e. a minimal unsatisfiable CNF (an MUS),
2707/// the irreducible atom of the UNSAT universe. Branch on the lex-least uncovered corner: it lies in
2708/// exactly `2ⁿ` subcubes (one per support `care ⊆ [n]`, with `value = corner & care`); recurse on each.
2709/// **Monotone pruning** kills a branch the moment any chosen blocker becomes fully redundant (it can
2710/// never recover a private corner once one is stolen). A leaf is total ∧ fully essential; leaves are
2711/// folded to their [`canonical_cover`] key so each orbit is reported once. (Exhaustive; for small `n`.)
2712pub fn minimal_cover_orbits(n: usize) -> Vec<Cover> {
2713    let generators = hyperoctahedral_generators(n);
2714    let group = group_closure(&generators, n); // the materialized Bₙ, built once and reused per node
2715    let mut orbits: HashMap<Vec<Subcube>, Cover> = HashMap::new();
2716    // **Orderly generation.** Visit each `Bₙ`-equivalence-class of partial covers exactly once, keyed
2717    // by its canonical form: expanding any representative of a class yields the same child classes (the
2718    // lex-least-uncovered corner and its covering subcubes commute with the group action), so one
2719    // representative per class still reaches every orbit leaf. This collapses both the branch-order
2720    // duplication and the up-to-`|Bₙ|` symmetric copies that otherwise make the raw tree intractable.
2721    let mut visited: BTreeSet<Vec<Subcube>> = BTreeSet::new();
2722    let mut chosen: Vec<Subcube> = Vec::new();
2723    enumerate_minimal_covers(n, &mut chosen, &group, &mut visited, &mut orbits);
2724    let mut out: Vec<Cover> = orbits.into_values().collect();
2725    out.sort_by(|a, b| cover_key(&a.blockers).cmp(&cover_key(&b.blockers)));
2726    out
2727}
2728
2729/// A blocker is *redundant* in a partial cover when every corner it blocks is also blocked by some
2730/// other chosen blocker — it owns no private corner. Used both for monotone pruning and the leaf
2731/// minimality check.
2732fn blocker_is_redundant(blockers: &[Subcube], i: usize) -> bool {
2733    blockers[i].footprint().iter().all(|&c| {
2734        blockers
2735            .iter()
2736            .enumerate()
2737            .any(|(j, b)| j != i && b.covers(c))
2738    })
2739}
2740
2741fn enumerate_minimal_covers(
2742    n: usize,
2743    chosen: &mut Vec<Subcube>,
2744    group: &[CubeSym],
2745    visited: &mut BTreeSet<Vec<Subcube>>,
2746    orbits: &mut HashMap<Vec<Subcube>, Cover>,
2747) {
2748    // Monotone minimality: if any chosen blocker is already fully redundant, no extension is minimal.
2749    if (0..chosen.len()).any(|i| blocker_is_redundant(chosen, i)) {
2750        return;
2751    }
2752    // Orderly generation: skip this partial if a symmetric copy (same canonical class) was already
2753    // expanded — every orbit it could reach is reachable from that copy.
2754    let canon = canonical_key(chosen, group);
2755    if !visited.insert(canon.clone()) {
2756        return;
2757    }
2758    let cover = Cover {
2759        n,
2760        blockers: chosen.clone(),
2761    };
2762    match cover.escaping_corner() {
2763        None => {
2764            // Total. By the monotone check above, every blocker is essential — a genuine minimal cover.
2765            // Its canonical key is the partial's canonical key (already computed).
2766            orbits.entry(canon).or_insert(cover);
2767        }
2768        Some(c) => {
2769            // Branch over the subcubes that contain the lex-least uncovered corner `c`: a subcube
2770            // contains `c` iff `value = c & care`, and every `care ⊆ [n]` is an integer in `0..2ⁿ`. We
2771            // start at `care = 1` to exclude the degenerate `care = 0` whole-cube blocker — the empty
2772            // clause `⊥`, which carries no variable structure and is the *only* minimal cover it can
2773            // belong to (it makes every other blocker redundant). The census is over genuine CNF: every
2774            // clause mentions at least one variable.
2775            for care in 1u64..(1u64 << n) {
2776                let blocker = Subcube {
2777                    n,
2778                    care,
2779                    value: c & care,
2780                };
2781                if !chosen.contains(&blocker) {
2782                    chosen.push(blocker);
2783                    enumerate_minimal_covers(n, chosen, group, visited, orbits);
2784                    chosen.pop();
2785                }
2786            }
2787        }
2788    }
2789}
2790
2791#[cfg(test)]
2792#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/hypercube/tests.rs"]
2793mod tests;