Skip to main content

logicaffeine_proof/
families.rs

1//! Parametric generators for symmetry-rich SAT families — the canonical hard cases where
2//! symmetry breaking earns its keep. They are programmatic (reproducible, offline, parametric)
3//! rather than vendored `.cnf` files, and each is pinned to its known verdict so the solver and
4//! the certified pipeline can be tested against ground truth.
5
6use crate::cdcl::Lit;
7use crate::dimacs::DimacsCnf;
8
9/// The known verdict of a generated instance, for test oracles.
10#[derive(Clone, Copy, Debug, PartialEq, Eq)]
11pub enum ExpectedVerdict {
12    Sat,
13    Unsat,
14}
15
16/// The pigeonhole principle PHP(n): `n` pigeons into `n-1` holes — unsatisfiable, and the
17/// textbook symmetry / resolution-hard family (any resolution refutation is exponential, while
18/// breaking the `S_n × S_{n-1}` symmetry collapses it). The variable for "pigeon `p` sits in
19/// hole `h`" lives at index `p*(n-1) + h`, so pigeons index rows and holes index columns.
20pub fn php(n: usize) -> (DimacsCnf, ExpectedVerdict) {
21    let holes = n.saturating_sub(1);
22    let num_vars = n * holes;
23    let var = |p: usize, h: usize| Lit::pos((p * holes + h) as u32);
24    let mut clauses: Vec<Vec<Lit>> = Vec::new();
25    // Each pigeon occupies at least one hole (an empty disjunction when holes == 0).
26    for p in 0..n {
27        clauses.push((0..holes).map(|h| var(p, h)).collect());
28    }
29    // No two pigeons share a hole.
30    for h in 0..holes {
31        for p in 0..n {
32            for q in (p + 1)..n {
33                clauses.push(vec![var(p, h).negated(), var(q, h).negated()]);
34            }
35        }
36    }
37    (DimacsCnf { num_vars, clauses }, ExpectedVerdict::Unsat)
38}
39
40/// **Coupled exactly-one + parity** — a scalable MIXED family that needs BOTH structures at once. The
41/// selectors `x₀…x_{n-1}` are constrained to *exactly one* true (an at-most-one clique + an at-least-one
42/// clause — a cardinality covering) AND to *even* total parity `⊕ xᵢ = 0` (a GF(2) system, encoded by a
43/// width-3 prefix-XOR chain with auxiliaries `sᵢ = ⊕_{j≤i} xⱼ` plus the unit `s_{n-1} = 0`). Exactly-one
44/// forces an ODD selector count, the parity forces EVEN — **UNSAT**, yet neither substructure alone is
45/// (the parity chain is satisfiable, exactly-one is satisfiable). The canonical shape for the fused
46/// parity+cardinality route ([`crate::lyapunov::fused_parity_cardinality_decide`]); `2n` variables.
47pub fn parity_exactly_one(n: usize) -> (DimacsCnf, ExpectedVerdict) {
48    assert!(n >= 2, "need at least two selectors");
49    let x = |i: usize| i as u32; // selectors 0..n-1
50    let s = |i: usize| (n + i) as u32; // prefix-XOR auxiliaries n..2n-1
51    let mut clauses: Vec<Vec<Lit>> = Vec::new();
52    // exactly-one of the selectors: at-least-one ∨, then pairwise at-most-one.
53    clauses.push((0..n).map(|i| Lit::pos(x(i))).collect());
54    for i in 0..n {
55        for j in (i + 1)..n {
56            clauses.push(vec![Lit::neg(x(i)), Lit::neg(x(j))]);
57        }
58    }
59    // Prefix-XOR chain: s₀ = x₀, sᵢ = s_{i-1} ⊕ xᵢ, s_{n-1} = 0 — each a small XOR gadget.
60    let gadget = |vars: &[u32], out: &mut Vec<Vec<Lit>>| {
61        let k = vars.len();
62        for mask in 0u32..(1 << k) {
63            if mask.count_ones() % 2 == 1 {
64                out.push(
65                    (0..k)
66                        .map(|t| Lit::new(vars[t], (mask >> t) & 1 == 0))
67                        .collect(),
68                );
69            }
70        }
71    };
72    gadget(&[s(0), x(0)], &mut clauses);
73    for i in 1..n {
74        gadget(&[s(i), s(i - 1), x(i)], &mut clauses);
75    }
76    clauses.push(vec![Lit::neg(s(n - 1))]);
77    (
78        DimacsCnf {
79            num_vars: 2 * n,
80            clauses,
81        },
82        ExpectedVerdict::Unsat,
83    )
84}
85
86/// Graph `k`-coloring of the complete graph `K_n` — the canonical *color-permutation* symmetry
87/// family (the color group `S_k` acts, on top of the vertex group `S_n`). It is unsatisfiable
88/// exactly when `k < n` (a clique of size `n` needs `n` colors). The variable "vertex `v` takes
89/// color `c`" lives at index `v*k + c`.
90pub fn clique_coloring(n: usize, k: usize) -> (DimacsCnf, ExpectedVerdict) {
91    let num_vars = n * k;
92    let var = |v: usize, c: usize| Lit::pos((v * k + c) as u32);
93    let mut clauses: Vec<Vec<Lit>> = Vec::new();
94    // Every vertex takes at least one color.
95    for v in 0..n {
96        clauses.push((0..k).map(|c| var(v, c)).collect());
97    }
98    // Adjacent vertices (every pair, in K_n) must differ in color.
99    for u in 0..n {
100        for w in (u + 1)..n {
101            for c in 0..k {
102                clauses.push(vec![var(u, c).negated(), var(w, c).negated()]);
103            }
104        }
105    }
106    let verdict = if k < n {
107        ExpectedVerdict::Unsat
108    } else {
109        ExpectedVerdict::Sat
110    };
111    (DimacsCnf { num_vars, clauses }, verdict)
112}
113
114/// The mutilated chessboard: an `n×n` board with two OPPOSITE corners removed, asking for a perfect
115/// domino tiling. Every domino covers one black and one white square, but the two removed corners
116/// share a colour (for even `n`), so the black/white counts differ by two and no tiling exists —
117/// UNSAT, and a textbook resolution-exponential family. The infeasibility is a bipartite-matching
118/// (Hall) obstruction, which our covering route certifies in polynomial time. Variables are dominoes
119/// (grid edges between adjacent surviving squares); each surviving square must be covered by exactly
120/// one. `n` must be even (so the parity argument bites).
121pub fn mutilated_chessboard(n: usize) -> (DimacsCnf, ExpectedVerdict) {
122    assert!(
123        n >= 4 && n % 2 == 0,
124        "the parity argument needs an even board ≥ 4"
125    );
126    let removed = |r: usize, c: usize| (r == 0 && c == 0) || (r == n - 1 && c == n - 1);
127    let sq = |r: usize, c: usize| r * n + c;
128    // Edges: horizontal (r,c)–(r,c+1) and vertical (r,c)–(r+1,c), both endpoints surviving.
129    let mut edges: Vec<(usize, usize)> = Vec::new();
130    for r in 0..n {
131        for c in 0..n {
132            if removed(r, c) {
133                continue;
134            }
135            if c + 1 < n && !removed(r, c + 1) {
136                edges.push((sq(r, c), sq(r, c + 1)));
137            }
138            if r + 1 < n && !removed(r + 1, c) {
139                edges.push((sq(r, c), sq(r + 1, c)));
140            }
141        }
142    }
143    let num_vars = edges.len();
144    let mut incident: std::collections::HashMap<usize, Vec<usize>> =
145        std::collections::HashMap::new();
146    for (e, &(a, b)) in edges.iter().enumerate() {
147        incident.entry(a).or_default().push(e);
148        incident.entry(b).or_default().push(e);
149    }
150    let mut clauses: Vec<Vec<Lit>> = Vec::new();
151    for r in 0..n {
152        for c in 0..n {
153            if removed(r, c) {
154                continue;
155            }
156            let inc = incident.get(&sq(r, c)).cloned().unwrap_or_default();
157            clauses.push(inc.iter().map(|&e| Lit::pos(e as u32)).collect()); // covered ≥ once
158            for i in 0..inc.len() {
159                for j in (i + 1)..inc.len() {
160                    clauses.push(vec![
161                        Lit::pos(inc[i] as u32).negated(),
162                        Lit::pos(inc[j] as u32).negated(),
163                    ]); // ≤ once
164                }
165            }
166        }
167    }
168    (DimacsCnf { num_vars, clauses }, ExpectedVerdict::Unsat)
169}
170
171/// The linear ordering principle GT(n): no finite strict total order lacks a maximal element — yet
172/// this formula asserts exactly that, so it is UNSAT. `x[i][j]` (index `i*n + j`) reads "i < j".
173/// Antisymmetry + totality + transitivity force a linear order, and the "every element has a greater
174/// one" clauses then contradict finiteness. A canonical resolution-hard family — it stresses the
175/// CDCL core / cutting-plane reasoning rather than a matching or parity specialist.
176pub fn ordering_principle(n: usize) -> (DimacsCnf, ExpectedVerdict) {
177    assert!(n >= 2);
178    let var = |i: usize, j: usize| Lit::pos((i * n + j) as u32);
179    let num_vars = n * n;
180    let mut clauses: Vec<Vec<Lit>> = Vec::new();
181    for i in 0..n {
182        for j in (i + 1)..n {
183            clauses.push(vec![var(i, j), var(j, i)]); // totality
184            clauses.push(vec![var(i, j).negated(), var(j, i).negated()]); // antisymmetry
185        }
186    }
187    for i in 0..n {
188        for j in 0..n {
189            for k in 0..n {
190                if i != j && j != k && i != k {
191                    clauses.push(vec![var(i, j).negated(), var(j, k).negated(), var(i, k)]);
192                    // transitivity
193                }
194            }
195        }
196    }
197    for i in 0..n {
198        clauses.push((0..n).filter(|&j| j != i).map(|j| var(i, j)).collect()); // i has a greater element
199    }
200    (DimacsCnf { num_vars, clauses }, ExpectedVerdict::Unsat)
201}
202
203/// A random 3-SAT instance: `num_clauses` clauses of three distinct variables with random signs,
204/// over `vars` variables, from a seeded SplitMix64 stream (reproducible — no wall-clock). Near the
205/// clause/variable ratio 4.26 these are the canonical *hard, non-symmetric* benchmarks — the
206/// general-instance control where raw CDCL quality (not symmetry breaking) decides the race.
207pub fn random_3sat(vars: usize, num_clauses: usize, seed: u64) -> DimacsCnf {
208    let mut state = seed;
209    let mut next = move || {
210        state = state.wrapping_add(0x9E3779B97F4A7C15);
211        let mut z = state;
212        z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
213        z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);
214        z ^ (z >> 31)
215    };
216    let mut clauses: Vec<Vec<Lit>> = Vec::with_capacity(num_clauses);
217    while clauses.len() < num_clauses {
218        let mut vs: Vec<u32> = Vec::with_capacity(3);
219        while vs.len() < 3 {
220            let v = (next() as usize % vars) as u32;
221            if !vs.contains(&v) {
222                vs.push(v);
223            }
224        }
225        clauses.push(vs.iter().map(|&v| Lit::new(v, next() & 1 == 0)).collect());
226    }
227    DimacsCnf {
228        num_vars: vars,
229        clauses,
230    }
231}
232
233/// A random **k-SAT** instance: `num_clauses` clauses of `k` distinct variables with random signs, over
234/// `vars` variables, from a seeded SplitMix64 stream (reproducible — no wall-clock). Generalizes
235/// [`random_3sat`]. The satisfiability threshold climbs with `k` roughly as `α_k ≈ 2ᵏ ln 2` (≈ 4.27 for
236/// k=3, ≈ 9.93 for k=4, ≈ 21.1 for k=5). Requires `k ≤ vars`.
237pub fn random_ksat(k: usize, vars: usize, num_clauses: usize, seed: u64) -> DimacsCnf {
238    let mut state = seed;
239    let mut next = move || {
240        state = state.wrapping_add(0x9E3779B97F4A7C15);
241        let mut z = state;
242        z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
243        z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);
244        z ^ (z >> 31)
245    };
246    let mut clauses: Vec<Vec<Lit>> = Vec::with_capacity(num_clauses);
247    while clauses.len() < num_clauses {
248        let mut vs: Vec<u32> = Vec::with_capacity(k);
249        while vs.len() < k {
250            let v = (next() as usize % vars) as u32;
251            if !vs.contains(&v) {
252                vs.push(v);
253            }
254        }
255        clauses.push(vs.iter().map(|&v| Lit::new(v, next() & 1 == 0)).collect());
256    }
257    DimacsCnf {
258        num_vars: vars,
259        clauses,
260    }
261}
262
263/// The CNF clauses encoding the parity constraint `v0 ⊕ v1 ⊕ … = rhs` over any arity (forbid every
264/// wrong-parity assignment of the listed variables — `2^{|vs|-1}` clauses, each of width `|vs|`).
265fn xor_clauses(vs: &[u32], rhs: bool) -> Vec<Vec<Lit>> {
266    let mut out = Vec::new();
267    for mask in 0u32..(1 << vs.len()) {
268        let odd = mask.count_ones() % 2 == 1;
269        if odd != rhs {
270            // Forbid this assignment: a literal is true exactly when it differs from the mask bit.
271            out.push(
272                vs.iter()
273                    .enumerate()
274                    .map(|(i, &v)| Lit::new(v, (mask >> i) & 1 == 0))
275                    .collect(),
276            );
277        }
278    }
279    out
280}
281
282/// Fold a freshly sampled `k`-subset's coefficient row into the running GF(2) echelon basis (rows keyed
283/// by pivot = least set variable). Returns `true` and extends the basis if the row is linearly
284/// independent of those seen so far, `false` if it lies in their span. This is the rank meter that lets
285/// [`random_kxor`] build a *guaranteed*-inconsistent system rather than a merely-probable one.
286fn gf2_absorb(basis: &mut std::collections::HashMap<u32, Vec<u32>>, vars: &[u32]) -> bool {
287    let mut row: std::collections::BTreeSet<u32> = vars.iter().copied().collect();
288    while let Some(&pivot) = row.iter().next() {
289        match basis.get(&pivot) {
290            Some(b) => {
291                for &v in b {
292                    if !row.remove(&v) {
293                        row.insert(v); // symmetric difference: row ⊕ basis[pivot]
294                    }
295                }
296            }
297            None => {
298                basis.insert(pivot, row.iter().copied().collect());
299                return true;
300            }
301        }
302    }
303    false
304}
305
306/// A **guaranteed-unsatisfiable** random **k-XOR** (parity) system over `n` variables: at least `m`
307/// equations of `k` distinct variables, all consistent with a planted assignment `p` except one whose
308/// right-hand side is flipped. Generalizes [`parity_unsat`] (the `k = 3` case).
309///
310/// The flip alone does **not** force inconsistency — it does so only once the flipped row lies in the
311/// span of the others, which a naive "flip the last equation" does not guarantee near `m ≈ n` (it
312/// silently yields *satisfiable* instances). So we build the consistent rows until the coefficient
313/// matrix reaches its **maximum achievable GF(2) rank** (`n` for odd `k`; `n − 1` for even `k`, whose
314/// even-weight rows can never span the all-ones functional) and *at least* `m` rows total, then append
315/// one more equation with a flipped right-hand side. At maximal rank that final row is redundant, so the
316/// system's solution set — `{p}` for odd `k`, `{p, p̄}` for even `k` — is pinned, and *every* pinned
317/// solution violates the flipped row: **the system is inconsistent by construction**, for any seed.
318/// Full-rank `k`-XOR above the XOR-SAT threshold is also exponentially hard for resolution
319/// (Ben-Sasson–Wigderson 2001) — hence for every CDCL solver — yet linear for Gaussian elimination over
320/// GF(2). Each equation expands to `2^{k-1}` width-`k` clauses, so keep `k` modest. `m` is a floor on the
321/// equation count (full rank may need a few more). Returns the XOR equations and the equisatisfiable CNF.
322pub fn random_kxor(
323    k: usize,
324    n: usize,
325    m: usize,
326    seed: u64,
327) -> (Vec<crate::xorsat::XorEquation>, DimacsCnf) {
328    assert!((1..=n).contains(&k) && m >= 1, "need 1 ≤ k ≤ n and m ≥ 1");
329    let mut state = seed;
330    let mut next = move || {
331        state = state.wrapping_add(0x9E3779B97F4A7C15);
332        let mut z = state;
333        z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
334        z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);
335        z ^ (z >> 31)
336    };
337    let planted: Vec<bool> = (0..n).map(|_| next() & 1 == 0).collect();
338    let mut draw = || {
339        let mut vs: Vec<u32> = Vec::with_capacity(k);
340        while vs.len() < k {
341            let v = (next() as usize % n) as u32;
342            if !vs.contains(&v) {
343                vs.push(v);
344            }
345        }
346        vs
347    };
348    let consistent_rhs = |vs: &[u32]| vs.iter().fold(false, |a, &v| a ^ planted[v as usize]);
349
350    // Phase 1: consistent rows until the coefficient matrix is at maximal rank AND there are ≥ m of them.
351    let target_rank = if k % 2 == 1 { n } else { n.saturating_sub(1) };
352    let cap = 8 * n + 64; // generous guard; random k-subsets reach maximal rank far inside this.
353    let mut basis: std::collections::HashMap<u32, Vec<u32>> = std::collections::HashMap::new();
354    let mut rows: Vec<(Vec<u32>, bool)> = Vec::new();
355    let mut rank = 0usize;
356    while (rank < target_rank || rows.len() < m) && rows.len() < cap {
357        let vs = draw();
358        if gf2_absorb(&mut basis, &vs) {
359            rank += 1;
360        }
361        let rhs = consistent_rhs(&vs);
362        rows.push((vs, rhs));
363    }
364    // Phase 2: one more equation, right-hand side FLIPPED. At maximal rank it is redundant, so the pinned
365    // solution set is unchanged by it — yet no pinned solution satisfies it ⇒ the system is UNSAT.
366    let vs = draw();
367    let rhs = !consistent_rhs(&vs);
368    rows.push((vs, rhs));
369
370    let mut eqs = Vec::new();
371    let mut clauses = Vec::new();
372    for (vs, rhs) in &rows {
373        eqs.push(crate::xorsat::XorEquation::new(
374            vs.iter().map(|&v| v as usize).collect::<Vec<_>>(),
375            *rhs,
376        ));
377        clauses.extend(xor_clauses(vs, *rhs));
378    }
379    (
380        eqs,
381        DimacsCnf {
382            num_vars: n,
383            clauses,
384        },
385    )
386}
387
388/// A **guaranteed-unsatisfiable** random 3-XOR (parity) system — the `k = 3` case of [`random_kxor`]:
389/// at least `m` 3-XOR equations over `n` variables, all consistent with a planted assignment except one
390/// flipped row, built up to maximal GF(2) rank so the inconsistency holds for *any* seed (see
391/// [`random_kxor`] for why the naive single flip does not suffice). Full-rank 3-XOR above the XOR-SAT
392/// threshold is **exponentially hard for resolution** (Ben-Sasson–Wigderson 2001), hence for every CDCL
393/// solver — yet linear for Gaussian elimination over GF(2). Returns the XOR equations (for
394/// [`crate::xorsat`]) and the equisatisfiable CNF (for a resolution solver).
395pub fn parity_unsat(n: usize, m: usize, seed: u64) -> (Vec<crate::xorsat::XorEquation>, DimacsCnf) {
396    random_kxor(3, n, m, seed)
397}
398
399/// A random 3-regular graph on `n` (even) vertices via the configuration model with self-loop /
400/// multi-edge rejection — an expander with high probability, which is what makes the Tseitin
401/// formula on it *exponentially* hard for resolution (Urquhart 1987; Ben-Sasson–Wigderson 2001).
402fn random_3regular(n: usize, seed: u64) -> Vec<(usize, usize)> {
403    let mut state = seed ^ 0x9E3779B97F4A7C15;
404    let mut next = move || {
405        state = state.wrapping_add(0x9E3779B97F4A7C15);
406        let mut z = state;
407        z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
408        z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);
409        z ^ (z >> 31)
410    };
411    for _ in 0..4000 {
412        let mut stubs: Vec<usize> = (0..n).flat_map(|v| [v, v, v]).collect();
413        for i in (1..stubs.len()).rev() {
414            let j = (next() as usize) % (i + 1);
415            stubs.swap(i, j);
416        }
417        let mut edges = Vec::new();
418        let mut seen = std::collections::HashSet::new();
419        let mut ok = true;
420        for c in stubs.chunks(2) {
421            let (a, b) = (c[0].min(c[1]), c[0].max(c[1]));
422            if a == b || !seen.insert((a, b)) {
423                ok = false;
424                break;
425            }
426            edges.push((a, b));
427        }
428        if ok {
429            return edges;
430        }
431    }
432    panic!("could not build a simple 3-regular graph on {n} vertices");
433}
434
435/// The **Tseitin formula on a random 3-regular expander** with odd total charge — UNSATISFIABLE,
436/// exponentially hard for resolution (so every CDCL solver blows up), yet solved in polynomial time
437/// by Gaussian elimination over GF(2). A *non-pigeonhole* hard family: the hardness is parity /
438/// graph expansion, not covering symmetry. One Boolean per edge; per vertex, the XOR of its incident
439/// edges equals that vertex's charge (vertex 0 charged, the rest not — an odd sum, hence
440/// inconsistent). Returns the XOR system (for [`crate::xorsat`]) and the equisatisfiable CNF.
441pub fn tseitin_expander(
442    n: usize,
443    seed: u64,
444) -> (Vec<crate::xorsat::XorEquation>, DimacsCnf, ExpectedVerdict) {
445    assert!(
446        n % 2 == 0 && n >= 4,
447        "a 3-regular graph needs an even vertex count ≥ 4"
448    );
449    let edges = random_3regular(n, seed);
450    let m = edges.len();
451    let mut incident: Vec<Vec<usize>> = vec![Vec::new(); n];
452    for (e, &(a, b)) in edges.iter().enumerate() {
453        incident[a].push(e);
454        incident[b].push(e);
455    }
456    let mut eqs = Vec::new();
457    let mut clauses = Vec::new();
458    for v in 0..n {
459        let inc = &incident[v];
460        let r = v == 0; // odd total charge ⇒ UNSAT
461        eqs.push(crate::xorsat::XorEquation::new(inc.clone(), r));
462        let d = inc.len();
463        for mask in 0u32..(1u32 << d) {
464            if ((mask.count_ones() % 2) == 1) != r {
465                clauses.push(
466                    (0..d)
467                        .map(|i| Lit::new(inc[i] as u32, (mask >> i) & 1 == 0))
468                        .collect(),
469                );
470            }
471        }
472    }
473    (
474        eqs,
475        DimacsCnf {
476            num_vars: m,
477            clauses,
478        },
479        ExpectedVerdict::Unsat,
480    )
481}
482
483/// The **Tseitin formula on a `w × n` grid** with odd total charge — UNSATISFIABLE, and the sharpest
484/// indictment of resolution search there is. A grid has treewidth exactly `w` (a fixed constant,
485/// independent of the length `n`), so a POLYNOMIAL-size, bounded-width resolution refutation provably
486/// EXISTS. Yet CDCL solvers without Gaussian reasoning blow up on the parity regardless — they cannot
487/// find the short proof that is known to exist — while Gaussian elimination over GF(2) decides it in
488/// near-linear time. One Boolean per grid edge; per vertex, the XOR of its incident edges equals its
489/// charge (vertex 0 charged, the rest not — an odd sum, hence inconsistent). Returns the XOR system
490/// (for [`crate::xorsat`]) and the equisatisfiable CNF.
491pub fn grid_tseitin(
492    w: usize,
493    n: usize,
494) -> (Vec<crate::xorsat::XorEquation>, DimacsCnf, ExpectedVerdict) {
495    assert!(w >= 2 && n >= 2, "a grid needs both dimensions ≥ 2");
496    let vid = |i: usize, j: usize| i * n + j;
497    let mut incident: Vec<Vec<usize>> = vec![Vec::new(); w * n];
498    let mut num_edges = 0usize;
499    for i in 0..w {
500        for j in 0..n {
501            let v = vid(i, j);
502            if j + 1 < n {
503                let e = num_edges;
504                num_edges += 1;
505                incident[v].push(e);
506                incident[vid(i, j + 1)].push(e);
507            }
508            if i + 1 < w {
509                let e = num_edges;
510                num_edges += 1;
511                incident[v].push(e);
512                incident[vid(i + 1, j)].push(e);
513            }
514        }
515    }
516    let mut eqs = Vec::new();
517    let mut clauses = Vec::new();
518    for v in 0..(w * n) {
519        let inc = &incident[v];
520        let r = v == 0; // odd total charge ⇒ UNSAT
521        eqs.push(crate::xorsat::XorEquation::new(inc.clone(), r));
522        let d = inc.len();
523        for mask in 0u32..(1u32 << d) {
524            if ((mask.count_ones() % 2) == 1) != r {
525                clauses.push(
526                    (0..d)
527                        .map(|i| Lit::new(inc[i] as u32, (mask >> i) & 1 == 0))
528                        .collect(),
529                );
530            }
531        }
532    }
533    (
534        eqs,
535        DimacsCnf {
536            num_vars: num_edges,
537            clauses,
538        },
539        ExpectedVerdict::Unsat,
540    )
541}
542
543/// The **mod-`p` Tseitin obstruction on a random 3-regular expander** — the parity crush carried to
544/// every prime. Each edge carries a `GF(p)` flow variable; orient each edge and impose, at every
545/// vertex, the signed divergence `Σ_out − Σ_in ≡ charge (mod p)`. Summing all vertices telescopes the
546/// edge variables to `0`, so the system is inconsistent exactly when the total charge `≢ 0 (mod p)`.
547/// We charge two vertices (total `2`): **inconsistent over `GF(p)` for every odd prime `p`, yet
548/// consistent over `GF(2)`** (`2 ≡ 0`) — a family the parity cut is structurally blind to, decided
549/// instantly by Gaussian elimination over the *right* `GF(p)`, and (on an expander) exponentially hard
550/// for resolution. Returns the `GF(p)` system (for [`crate::modp`]), the equisatisfiable one-hot
551/// Boolean CNF (for resolution solvers), and the `GF(p)` verdict.
552pub fn mod_p_tseitin_expander(
553    n: usize,
554    p: u64,
555    seed: u64,
556) -> (Vec<crate::modp::ModpEquation>, DimacsCnf, ExpectedVerdict) {
557    assert!(
558        p >= 3,
559        "the mod-p obstruction needs an odd prime (p=2 is the parity case, consistent here)"
560    );
561    mod_tseitin_expander_core(n, p, seed)
562}
563
564/// The **composite-modulus** sibling of [`mod_p_tseitin_expander`]: the same total-charge-2 divergence
565/// obstruction over `ℤ/m` for a squarefree composite `m` (e.g. `m = 6`), with a mixed-radix one-hot
566/// Boolean encoding (`m` values per edge). By CRT `ℤ/m ≅ ∏ GF(pᵢ)`, so the system is inconsistent over
567/// `ℤ/m` exactly when it is inconsistent over some prime factor — total charge `2 ≢ 0 (mod m)` for any
568/// `m ≥ 3` that does not divide `2` — and [`crate::modm::solve`] decides it through that factor with a
569/// solver-free re-checkable certificate ([`crate::modm::is_refutation`]). This drives the **ring**
570/// route (`ℤ/m` Gaussian via CRT), not the prime-field route, on a CNF that resolution still walls on.
571pub fn mod_m_tseitin_expander(
572    n: usize,
573    m: u64,
574    seed: u64,
575) -> (Vec<crate::modp::ModpEquation>, DimacsCnf, ExpectedVerdict) {
576    assert!(
577        m >= 3,
578        "the composite obstruction needs a modulus ≥ 3 (m=2 is the parity case, consistent here)"
579    );
580    mod_tseitin_expander_core(n, m, seed)
581}
582
583/// Shared construction for the total-charge-2 divergence obstruction over `ℤ/modulus` on a random
584/// 3-regular expander, used by both the prime-field ([`mod_p_tseitin_expander`]) and composite-ring
585/// ([`mod_m_tseitin_expander`]) families. Returns the `ℤ/modulus` divergence system, the equisatisfiable
586/// one-hot Boolean CNF (`modulus` values per edge), and the UNSAT verdict. Charging two vertices makes
587/// the total `2`, which is `≢ 0 (mod modulus)` for every `modulus ≥ 3` yet `≡ 0 (mod 2)` — so the parity
588/// cut is blind to it and only Gaussian elimination over the right characteristic decides it.
589fn mod_tseitin_expander_core(
590    n: usize,
591    modulus: u64,
592    seed: u64,
593) -> (Vec<crate::modp::ModpEquation>, DimacsCnf, ExpectedVerdict) {
594    use crate::cdcl::Lit;
595    use crate::modp::ModpEquation;
596    assert!(
597        n % 2 == 0 && n >= 4,
598        "a 3-regular graph needs an even vertex count ≥ 4"
599    );
600    let edges = random_3regular(n, seed); // each (a, b) with a < b; orient a → b (tail a, head b)
601    let ne = edges.len();
602    let charge = |v: usize| u64::from(v == 0 || v == 1); // total charge 2: ≢0 mod modulus (≥3), ≡0 mod 2
603
604    // The ℤ/modulus divergence system: +x_e at the tail, −x_e (= (modulus−1)·x_e) at the head.
605    let mut eqs: Vec<ModpEquation> = Vec::new();
606    for v in 0..n {
607        let mut coeffs: Vec<(usize, u64)> = Vec::new();
608        for (e, &(a, b)) in edges.iter().enumerate() {
609            if a == v {
610                coeffs.push((e, 1));
611            } else if b == v {
612                coeffs.push((e, modulus - 1));
613            }
614        }
615        eqs.push(ModpEquation::new(coeffs, charge(v)));
616    }
617
618    // The equisatisfiable Boolean CNF: one-hot bit b(e, val) = "edge e takes value val" (var e*modulus+val).
619    let bvar = |e: usize, val: u64| (e * modulus as usize + val as usize) as u32;
620    let mut clauses: Vec<Vec<Lit>> = Vec::new();
621    for e in 0..ne {
622        clauses.push((0..modulus).map(|val| Lit::pos(bvar(e, val))).collect()); // ≥1 value
623        for v1 in 0..modulus {
624            for v2 in (v1 + 1)..modulus {
625                clauses.push(vec![Lit::neg(bvar(e, v1)), Lit::neg(bvar(e, v2))]);
626                // ≤1 value
627            }
628        }
629    }
630    // Per vertex, forbid every assignment of its incident edge-values whose signed sum ≢ charge.
631    for v in 0..n {
632        let incident: Vec<(usize, i64)> = edges
633            .iter()
634            .enumerate()
635            .filter_map(|(e, &(a, b))| {
636                if a == v {
637                    Some((e, 1i64))
638                } else if b == v {
639                    Some((e, -1i64))
640                } else {
641                    None
642                }
643            })
644            .collect();
645        let d = incident.len();
646        let want = charge(v) as i64;
647        let pi = modulus as i64;
648        for idx in 0..modulus.pow(d as u32) {
649            let mut x = idx;
650            let mut combo = vec![0u64; d];
651            for slot in combo.iter_mut() {
652                *slot = x % modulus;
653                x /= modulus;
654            }
655            let s = incident
656                .iter()
657                .zip(&combo)
658                .fold(0i64, |acc, (&(_, sign), &val)| acc + sign * val as i64);
659            if (s.rem_euclid(pi)) != (want.rem_euclid(pi)) {
660                clauses.push(
661                    incident
662                        .iter()
663                        .zip(&combo)
664                        .map(|(&(e, _), &val)| Lit::neg(bvar(e, val)))
665                        .collect(),
666                );
667            }
668        }
669    }
670
671    (
672        eqs,
673        DimacsCnf {
674            num_vars: ne * modulus as usize,
675            clauses,
676        },
677        ExpectedVerdict::Unsat,
678    )
679}
680
681/// A **satisfiable** sibling of [`mod_p_tseitin_expander`] over the same 3-regular graph and the same
682/// one-hot Boolean encoding, but with a charge distribution whose total `≡ 0 (mod p)`. The divergence
683/// system `Σ_out x − Σ_in x ≡ charge(v)` is consistent exactly when the charges sum to zero (summing all
684/// vertex equations telescopes the left side to `0`), so this instance is SAT — the control for the GF(p)
685/// route's model-returning path. Charge: `+1` at vertex 0, `−1 (= p−1)` at vertex 1, zero elsewhere.
686pub fn mod_p_consistent_onehot(
687    n: usize,
688    p: u64,
689    seed: u64,
690) -> (Vec<crate::modp::ModpEquation>, DimacsCnf, ExpectedVerdict) {
691    use crate::cdcl::Lit;
692    use crate::modp::ModpEquation;
693    assert!(
694        n % 2 == 0 && n >= 4,
695        "a 3-regular graph needs an even vertex count ≥ 4"
696    );
697    assert!(p >= 3, "the mod-p one-hot encoding needs an odd prime");
698    let edges = random_3regular(n, seed);
699    let ne = edges.len();
700    let charge = |v: usize| -> u64 {
701        match v {
702            0 => 1,
703            1 => p - 1,
704            _ => 0,
705        }
706    }; // total charge ≡ 0 (mod p) ⟹ consistent
707
708    let mut eqs: Vec<ModpEquation> = Vec::new();
709    for v in 0..n {
710        let mut coeffs: Vec<(usize, u64)> = Vec::new();
711        for (e, &(a, b)) in edges.iter().enumerate() {
712            if a == v {
713                coeffs.push((e, 1));
714            } else if b == v {
715                coeffs.push((e, p - 1));
716            }
717        }
718        eqs.push(ModpEquation::new(coeffs, charge(v)));
719    }
720
721    let bvar = |e: usize, val: u64| (e * p as usize + val as usize) as u32;
722    let mut clauses: Vec<Vec<Lit>> = Vec::new();
723    for e in 0..ne {
724        clauses.push((0..p).map(|val| Lit::pos(bvar(e, val))).collect());
725        for v1 in 0..p {
726            for v2 in (v1 + 1)..p {
727                clauses.push(vec![Lit::neg(bvar(e, v1)), Lit::neg(bvar(e, v2))]);
728            }
729        }
730    }
731    for v in 0..n {
732        let incident: Vec<(usize, i64)> = edges
733            .iter()
734            .enumerate()
735            .filter_map(|(e, &(a, b))| {
736                if a == v {
737                    Some((e, 1i64))
738                } else if b == v {
739                    Some((e, -1i64))
740                } else {
741                    None
742                }
743            })
744            .collect();
745        let d = incident.len();
746        let want = charge(v) as i64;
747        let pi = p as i64;
748        for idx in 0..p.pow(d as u32) {
749            let mut x = idx;
750            let mut combo = vec![0u64; d];
751            for slot in combo.iter_mut() {
752                *slot = x % p;
753                x /= p;
754            }
755            let s = incident
756                .iter()
757                .zip(&combo)
758                .fold(0i64, |acc, (&(_, sign), &val)| acc + sign * val as i64);
759            if (s.rem_euclid(pi)) != (want.rem_euclid(pi)) {
760                clauses.push(
761                    incident
762                        .iter()
763                        .zip(&combo)
764                        .map(|(&(e, _), &val)| Lit::neg(bvar(e, val)))
765                        .collect(),
766                );
767            }
768        }
769    }
770
771    (
772        eqs,
773        DimacsCnf {
774            num_vars: ne * p as usize,
775            clauses,
776        },
777        ExpectedVerdict::Sat,
778    )
779}
780
781/// The **first-moment (counting) upper bound** on the random k-SAT satisfiability threshold:
782/// `α*(k) = ln 2 / ln(2ᵏ / (2ᵏ − 1))`. Above this clause density the expected number of satisfying
783/// assignments `E[X] = 2ⁿ(1 − 2⁻ᵏ)^{αn} = (2·(1 − 2⁻ᵏ)^α)ⁿ` has per-variable base `< 1`, so `E[X] → 0`
784/// and the instance is UNSAT with high probability (Markov) — a **rigorous** upper bound on the true
785/// threshold, exact and closed-form (no sampling). The sequence climbs as `2ᵏ ln 2 − (ln 2)/2`,
786/// asymptotically **doubling per k**: `2.41, 5.19, 10.74, 21.83, 44.02, …` for `k = 2, 3, 4, 5, 6, …`.
787/// The *true* thresholds (≈ 1, 4.27, 9.93, 21.1, …) lie below it; the gap → ½ as k → ∞ (the difference
788/// between the first-moment bound `2ᵏln2 − ½ln2` and the sharp value `2ᵏln2 − (1+ln2)/2`).
789pub fn ksat_threshold_first_moment_upper(k: u32) -> f64 {
790    let pow = (1u64 << k) as f64;
791    std::f64::consts::LN_2 / (pow / (pow - 1.0)).ln()
792}
793
794/// All `q`-element subsets of `{0, …, n−1}` in lexicographic order (the standard combinatorial
795/// odometer). Returns empty when `q > n`. Used to build the hyperedge / clique families below; keep
796/// `n` and `q` small, the count is `C(n, q)`.
797fn combinations(n: usize, q: usize) -> Vec<Vec<usize>> {
798    let mut out = Vec::new();
799    if q == 0 || q > n {
800        return out;
801    }
802    let mut idx: Vec<usize> = (0..q).collect();
803    loop {
804        out.push(idx.clone());
805        let mut i = q;
806        loop {
807            if i == 0 {
808                return out;
809            }
810            i -= 1;
811            if idx[i] != i + n - q {
812                break;
813            }
814        }
815        idx[i] += 1;
816        for j in (i + 1)..q {
817            idx[j] = idx[j - 1] + 1;
818        }
819    }
820}
821
822/// The **weak pigeonhole principle** `PHP^{holes}_{pigeons}`: `pigeons` pigeons into `holes` holes —
823/// unsatisfiable exactly when `pigeons > holes`. Generalizes [`php`] (which is the tight
824/// `holes = pigeons − 1` case) to any hole count, including the *weak* regime (`holes = 2·pigeons`,
825/// `pigeons²`, …) used to probe how far symmetry breaking scales as the holes-to-pigeons ratio grows.
826/// Same variable layout as [`php`] — "pigeon `p` in hole `h`" at index `p*holes + h` — so
827/// `weak_php(n, n−1)` is byte-for-byte `php(n)`.
828pub fn weak_php(pigeons: usize, holes: usize) -> (DimacsCnf, ExpectedVerdict) {
829    let num_vars = pigeons * holes;
830    let var = |p: usize, h: usize| Lit::pos((p * holes + h) as u32);
831    let mut clauses: Vec<Vec<Lit>> = Vec::new();
832    for p in 0..pigeons {
833        clauses.push((0..holes).map(|h| var(p, h)).collect()); // each pigeon in ≥ 1 hole
834    }
835    for h in 0..holes {
836        for p in 0..pigeons {
837            for q in (p + 1)..pigeons {
838                clauses.push(vec![var(p, h).negated(), var(q, h).negated()]); // ≤ 1 pigeon per hole
839            }
840        }
841    }
842    let verdict = if pigeons > holes {
843        ExpectedVerdict::Unsat
844    } else {
845        ExpectedVerdict::Sat
846    };
847    (DimacsCnf { num_vars, clauses }, verdict)
848}
849
850/// The **functional pigeonhole principle** FPHP(n): `php(n)` strengthened so each pigeon sits in *at
851/// most* one hole (the placement is a function, not a relation). Adds the "no pigeon in two holes"
852/// clauses on top of PHP; still UNSAT, still `S_n × S_{n−1}`-symmetric, and the standard strengthening
853/// used to check that symmetry breaking survives the extra functional clauses. Same layout as [`php`].
854pub fn functional_php(n: usize) -> (DimacsCnf, ExpectedVerdict) {
855    let holes = n.saturating_sub(1);
856    let (mut cnf, _) = php(n);
857    let var = |p: usize, h: usize| Lit::pos((p * holes + h) as u32);
858    for p in 0..n {
859        for h1 in 0..holes {
860            for h2 in (h1 + 1)..holes {
861                cnf.clauses
862                    .push(vec![var(p, h1).negated(), var(p, h2).negated()]); // ≤ 1 hole per pigeon
863            }
864        }
865    }
866    (cnf, ExpectedVerdict::Unsat)
867}
868
869/// The **onto (bijective) pigeonhole principle** onto-FPHP(n): `functional_php(n)` further forced to
870/// be *onto* — every hole receives at least one pigeon. The placement is now a bijection `n → n−1`,
871/// which cannot exist; UNSAT. This is the hardest standard PHP variant for symmetry reasoning (it pins
872/// both the pigeon and the hole side), and the maximal clause set over the shared [`php`] layout.
873pub fn onto_php(n: usize) -> (DimacsCnf, ExpectedVerdict) {
874    let holes = n.saturating_sub(1);
875    let (mut cnf, _) = functional_php(n);
876    let var = |p: usize, h: usize| Lit::pos((p * holes + h) as u32);
877    for h in 0..holes {
878        cnf.clauses.push((0..n).map(|p| var(p, h)).collect()); // each hole gets ≥ 1 pigeon (onto)
879    }
880    (cnf, ExpectedVerdict::Unsat)
881}
882
883/// The **modular counting principle** `Count_q(n)`: can the `n`-element set `{0,…,n−1}` be exactly
884/// partitioned into blocks of size `q`? A Boolean per `q`-subset (hyperedge); clauses force every
885/// element to lie in ≥ 1 chosen block and forbid any two *overlapping* blocks — so the chosen blocks
886/// are a perfect `q`-cover (an exact partition). That exists iff `q ∣ n`, hence the formula is
887/// **UNSAT exactly when `q ∤ n`**. This is the canonical *modular* family — the obstruction is a
888/// counting argument mod `q` that resolution cannot make at low width (Ajtai; Beame–Pitassi), the
889/// natural target of the GF(q) / mod-`m` rung. `q = 2` is perfect matching on the complete graph `K_n`
890/// (UNSAT for odd `n`). The hyperedge count is `C(n, q)`, so keep `n`, `q` small.
891pub fn mod_counting(n: usize, q: usize) -> (DimacsCnf, ExpectedVerdict) {
892    assert!(q >= 2 && n >= q, "need a block size q ≥ 2 with n ≥ q");
893    let edges = combinations(n, q);
894    let num_vars = edges.len();
895    let mut incident: Vec<Vec<usize>> = vec![Vec::new(); n];
896    for (e, edge) in edges.iter().enumerate() {
897        for &v in edge {
898            incident[v].push(e);
899        }
900    }
901    let mut clauses: Vec<Vec<Lit>> = Vec::new();
902    for inc in &incident {
903        clauses.push(inc.iter().map(|&e| Lit::pos(e as u32)).collect()); // every element covered ≥ once
904    }
905    for e in 0..edges.len() {
906        for f in (e + 1)..edges.len() {
907            if edges[e].iter().any(|v| edges[f].contains(v)) {
908                clauses.push(vec![Lit::neg(e as u32), Lit::neg(f as u32)]); // overlapping blocks are exclusive
909            }
910        }
911    }
912    let verdict = if n % q == 0 {
913        ExpectedVerdict::Sat
914    } else {
915        ExpectedVerdict::Unsat
916    };
917    (DimacsCnf { num_vars, clauses }, verdict)
918}
919
920/// The exactly-one groups of [`mod_counting`]'s **linear encoding**: for each point, the variables of
921/// its covering clause — the incident `q`-subsets, in the same variable order as [`mod_counting`].
922/// Feed to `polycalc::exactly_one_linear_generators` for the degree-1 point generators plus overlap
923/// pairs (the encoding the modular-counting degree lower bounds are stated against).
924pub fn mod_counting_groups(n: usize, q: usize) -> Vec<Vec<u32>> {
925    let (cnf, _) = mod_counting(n, q);
926    cnf.clauses
927        .iter()
928        .filter(|c| c.iter().all(|l| l.is_positive()))
929        .map(|c| c.iter().map(|l| l.var()).collect())
930        .collect()
931}
932
933/// The edge layout of [`mod_counting`]: variable `e` is the `q`-subset `mod_counting_edges(n, q)[e]`
934/// of the point set `{0,…,n−1}` — the map a witness-support predicate needs to read a monomial as a
935/// set of blocks.
936pub fn mod_counting_edges(n: usize, q: usize) -> Vec<Vec<usize>> {
937    combinations(n, q)
938}
939
940/// The known two-colour Ramsey numbers `R(s, t)` for the small `(s, t)` we can actually build CNFs for
941/// (symmetric: `R(s, t) = R(t, s)`); `None` when the value is still an open problem. `R(s, t)` is the
942/// least `n` such that every red/blue colouring of `K_n`'s edges contains a red `K_s` or a blue `K_t`.
943pub fn ramsey_number(s: usize, t: usize) -> Option<usize> {
944    let (a, b) = (s.min(t), s.max(t));
945    match (a, b) {
946        (1, _) => Some(1),
947        (2, b) => Some(b),
948        (3, 3) => Some(6),
949        (3, 4) => Some(9),
950        (3, 5) => Some(14),
951        (3, 6) => Some(18),
952        (3, 7) => Some(23),
953        (3, 8) => Some(28),
954        (3, 9) => Some(36),
955        (4, 4) => Some(18),
956        (4, 5) => Some(25),
957        _ => None,
958    }
959}
960
961/// The **Ramsey formula** `Ramsey(s, t; n)`: 2-colour the edges of the complete graph `K_n` (one
962/// Boolean per edge — true = red, false = blue) avoiding every red `K_s` and every blue `K_t`. For each
963/// `s`-clique a clause forbids all its edges being red; for each `t`-clique a clause forbids all blue.
964/// Such a colouring exists iff `n < R(s, t)`, so the formula is **UNSAT exactly when `n ≥ R(s, t)`**.
965/// A genuinely different geometry from pigeonhole/parity — clique structure, not covering or counting —
966/// and a classic CDCL stress family (`Ramsey(3,3;6)` is the smallest UNSAT case). Panics for `(s, t)`
967/// whose Ramsey number is unknown (so the verdict is never guessed); see [`ramsey_number`].
968pub fn ramsey(s: usize, t: usize, n: usize) -> (DimacsCnf, ExpectedVerdict) {
969    assert!(s >= 2 && t >= 2 && n >= 2);
970    let r = ramsey_number(s, t).expect("Ramsey number R(s,t) must be known to pin the verdict");
971    let mut edge_id = std::collections::HashMap::new();
972    for (e, pair) in combinations(n, 2).iter().enumerate() {
973        edge_id.insert((pair[0], pair[1]), e as u32);
974    }
975    let num_vars = edge_id.len();
976    let mut clauses: Vec<Vec<Lit>> = Vec::new();
977    let clique_edges = |clique: &[usize]| -> Vec<u32> {
978        combinations(clique.len(), 2)
979            .iter()
980            .map(|p| edge_id[&(clique[p[0]], clique[p[1]])])
981            .collect()
982    };
983    for clique in combinations(n, s) {
984        clauses.push(clique_edges(&clique).into_iter().map(Lit::neg).collect());
985        // not all red
986    }
987    for clique in combinations(n, t) {
988        clauses.push(clique_edges(&clique).into_iter().map(Lit::pos).collect());
989        // not all blue
990    }
991    let verdict = if n >= r {
992        ExpectedVerdict::Unsat
993    } else {
994        ExpectedVerdict::Sat
995    };
996    (DimacsCnf { num_vars, clauses }, verdict)
997}
998
999/// The **pebbling contradiction** on the pyramid DAG of the given `height` — the canonical resolution
1000/// *space* family (Ben-Sasson–Wigderson; Nordström). The pyramid has rows `0..=height` with row `r`
1001/// holding `r+1` nodes; each node `(r, i)` for `r < height` has the two predecessors `(r+1, i)` and
1002/// `(r+1, i+1)` below it. One Boolean per node "is pebbled": every source (bottom row) is asserted
1003/// pebbled (unit), pebbling propagates up (`pebbled(a) ∧ pebbled(b) → pebbled(parent)`), and the apex
1004/// `(0,0)` is asserted *un*pebbled — a contradiction, so UNSAT. Refutation size is linear (unit
1005/// propagation alone closes it), but refuting it in small *space* provably is not — the axis pigeonhole
1006/// and parity do not touch.
1007pub fn pebbling_pyramid(height: usize) -> (DimacsCnf, ExpectedVerdict) {
1008    let node = |r: usize, i: usize| (r * (r + 1) / 2 + i) as u32; // triangular id, apex = node(0,0) = 0
1009    let num_vars = (height + 1) * (height + 2) / 2;
1010    let mut clauses: Vec<Vec<Lit>> = Vec::new();
1011    for i in 0..=height {
1012        clauses.push(vec![Lit::pos(node(height, i))]); // sources (bottom row) are pebbled
1013    }
1014    for r in 0..height {
1015        for i in 0..=r {
1016            clauses.push(vec![
1017                Lit::neg(node(r + 1, i)),
1018                Lit::neg(node(r + 1, i + 1)),
1019                Lit::pos(node(r, i)),
1020            ]); // both children pebbled ⇒ this node pebbled
1021        }
1022    }
1023    clauses.push(vec![Lit::neg(node(0, 0))]); // the apex is asserted unpebbled — the contradiction
1024    (DimacsCnf { num_vars, clauses }, ExpectedVerdict::Unsat)
1025}
1026
1027#[cfg(test)]
1028#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/families/tests.rs"]
1029mod tests;