nx_csp_arc_gate.nx source

1import "nx_gate_gn.nx" 2import "nx_gate_base.nx" 3// nx_csp_arc_gate.nx -- CONSTRAINT SATISFACTION / ARC-CONSISTENCY (AC-3, Mackworth): prune domain values that have no 4// supporting value across a constraint, propagating until a fixpoint -- often SOLVING the CSP with no search (operator: 5// fill the GOFAI gap beyond DPLL SAT). Domains as bitmasks, constraints X<Y<Z over {1,2,3}. AC-3 reduces the domains to 6// singletons X=1,Y=2,Z=3 by propagation alone. Pure integer, NO LLM. 7// T0 CSP: variables X,Y,Z each domain {1,2,3}; constraints X<Y and Y<Z. 8// T1 REVISE: arc X<Y removes 3 from X (no Y>3) and 1 from Y (no X<1) -- value pruning. 9// T2 PROPAGATE (AC-3): revising to a fixpoint cascades the prunes across both constraints. 10// T3 SINGLETONS: domains collapse to X={1}, Y={2}, Z={3}. 11// T4 SOLVED-NO-SEARCH: the unique solution fell out of propagation alone (no backtracking needed). 12// T5 = CSP arc-consistency (AC-3) solved the constraint network by propagation, no LLM. 13// license_tier: ORIGINAL 14import "nx_syscalls.nx" 15 16func grow(name: *u8, ok: i64) -> i64 { if ok==1 { gw(" PASS " as *u8) } else { gw(" FAIL " as *u8) } gw(name); gw(" 17" as *u8); return ok } 18func dom_min(mask: i64) -> i64 { var v: i64=1; while v<=3 { if ((mask>>(v-1))&1)==1 { return v } v=v+1 } return 0 } 19func dom_max(mask: i64) -> i64 { var v: i64=3; while v>=1 { if ((mask>>(v-1))&1)==1 { return v } v=v-1 } return 0 } 20func popc(mask: i64) -> i64 { var c: i64=0; var v: i64=0; while v<3 { if ((mask>>v)&1)==1 { c=c+1 } v=v+1 } return c } 21// for constraint A<B, revise A: keep a iff a < max(B). 22func revise_less(A: i64, B: i64) -> i64 { let mx: i64=dom_max(B); var nm: i64=0; var v: i64=1; while v<=3 { if ((A>>(v-1))&1)==1 { if v<mx { nm=nm|(1<<(v-1)) } } v=v+1 } return nm } 23// for constraint A<B, revise B: keep b iff b > min(A). 24func revise_greater(B: i64, A: i64) -> i64 { let mn: i64=dom_min(A); var nm: i64=0; var v: i64=1; while v<=3 { if ((B>>(v-1))&1)==1 { if v>mn { nm=nm|(1<<(v-1)) } } v=v+1 } return nm } 25 26func main() -> i64 { 27 gw("=== nx_csp_arc_gate: CSP arc-consistency (AC-3) -- solve by propagation, no LLM ===\n" as *u8) 28 var pass: i64=0; var total: i64=0 29 var X: i64=7; var Y: i64=7; var Z: i64=7 // {1,2,3} each (bits 0,1,2) 30 31 total=total+1; pass=pass+1 32 gw(" [PASS] T0 CSP: X,Y,Z in {1,2,3}; constraints X<Y, Y<Z\n" as *u8) 33 34 // T1 single revise of arc X<Y. 35 let X1: i64=revise_less(X,Y); let Y1: i64=revise_greater(Y,X) 36 total=total+1; if X1==3 { if Y1==6 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) } } else { gw(" [FAIL] " as *u8) } 37 gw("T1 REVISE: arc X<Y -> X loses 3 (X={1,2}), Y loses 1 (Y={2,3})\n" as *u8) 38 39 // T2-T3 AC-3 to fixpoint. 40 var changed: i64=1; var iters: i64=0 41 while changed==1 { changed=0 42 let nX: i64=revise_less(X,Y); if nX!=X { X=nX; changed=1 } 43 let nY1: i64=revise_greater(Y,X); if nY1!=Y { Y=nY1; changed=1 } 44 let nY2: i64=revise_less(Y,Z); if nY2!=Y { Y=nY2; changed=1 } 45 let nZ: i64=revise_greater(Z,Y); if nZ!=Z { Z=nZ; changed=1 } 46 iters=iters+1 47 } 48 total=total+1; pass=pass+1 49 gw(" [PASS] T2 PROPAGATE: AC-3 reached a fixpoint in " as *u8); gn(iters); gw(" sweeps (prunes cascaded across both constraints)\n" as *u8) 50 51 // T3 singletons. 52 total=total+1; if popc(X)==1 { if popc(Y)==1 { if popc(Z)==1 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) } } else { gw(" [FAIL] " as *u8) } } else { gw(" [FAIL] " as *u8) } 53 gw("T3 SINGLETONS: X={" as *u8); gn(dom_min(X)); gw("}, Y={" as *u8); gn(dom_min(Y)); gw("}, Z={" as *u8); gn(dom_min(Z)); gw("}\n" as *u8) 54 55 // T4 solved (1<2<3, no search). 56 total=total+1; if dom_min(X)==1 { if dom_min(Y)==2 { if dom_min(Z)==3 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) } } else { gw(" [FAIL] " as *u8) } } else { gw(" [FAIL] " as *u8) } 57 gw("T4 SOLVED-NO-SEARCH: unique solution X=1<Y=2<Z=3 fell out of propagation alone (no backtracking)\n" as *u8) 58 59 total=total+1; if dom_min(X)==1 { if dom_min(Z)==3 { pass=pass+1; gw(" [PASS] " as *u8) } else { gw(" [FAIL] " as *u8) } } else { gw(" [FAIL] " as *u8) } 60 gw("T5 CSP ARC-CONSISTENCY: AC-3 solved the constraint network by domain propagation, no LLM\n" as *u8) 61 62 gw("\n CSP ARC-CONSISTENCY (AC-3, Mackworth): revising each arc removed unsupported domain values, and propagating to a fixpoint\n" as *u8) 63 gw(" collapsed X,Y,Z to the unique solution 1<2<3 with NO search. Pure integer bitmask domains, NO LLM. Extends the DPLL SAT\n" as *u8) 64 gw(" solver into general constraint propagation -- the GOFAI row. Last foundation rung: STRIPS planning.\n" as *u8) 65 gw("CSP-ARC verdict=" as *u8) 66 if pass==total { gw("GREEN passes=" as *u8); gn(pass); gw("/" as *u8); gn(total); gw(" -- AC-3 solved the CSP by propagation, no LLM\n" as *u8); sys_exit(0); return 0 } 67 gw("RED passes=" as *u8); gn(pass); gw("/" as *u8); gn(total); gw("\n" as *u8); sys_exit(1); return 1 68}