Stronger CLP/FD sum consistency? (SWI-Prolog)
From
Julio Di Egidio@
[email protected] to
comp.lang.prolog,comp.programming on Sat Oct 24 13:50:45 2026
From Newsgroup: comp.programming
In SWI-Prolog:
Here is a simple scenario where I wish the consistency of
CLP/FD sum constraints would propagate more strongly.
We have boolean variables A,B,C,D and sum constraints on
two subsets of those. It is not difficult to figure out
that that is enough to fix variable A, but CLP/FD doesn't
see it:
```prolog
?- use_module(library(clpfd)).
?- Vs = [A,B,C,D], Vs ins 0..1, sum([A,C,D], #=, 2), sum([B,C,D], #=, 1).
Vs = [A,B,C,D],
A in 0..1,
A+C+D#=2,
B in 0..1,
B+C+D#=1,
C in 0..1,
D in 0..1.
```
On the other hand, I can force it by considering the intersection
of the two subsets, and putting a constraint on that intersection
that is "mutually consistent" with the other two constraints:
```prolog
?- Vs = [A,B,C,D], Vs ins 0..1, sum([C,D], #=, N), sum([A,N], #=, 2), sum([B,N], #=, 1).
Vs = [1,0,C,D],
A = N, N = 1,
B = 0,
C in 0..1,
C+D#=1,
D in 0..1.
```
But of course a solver's code becomes quite more complicated
since, for any new sum constraint on some subset of variables,
we'd have to actually constraint all intersections of that
subset with any other subset of variables that has already
been constrained... or something like that, I am not at the
details yet.
QUESTION: Is all that work really needed? And, am I just
reinventing some wheel, i.e. that can be done easily with
the tools already provided?
BTW, CLP/B does offer that stronger consistency, i.e. it
does solve A in the example, but then CLP/B does not offer
a sum constraint proper, card/2 wants a ground cardinality:
and I have not figured out how to implement a cardinality
constraint for CLP/B myself, though I guess it wouldn't be
simpler than the above. Anyway to go beyond just booleans,
I am more interested in extending on CLP/FD.
-Julio
--- Synchronet 3.22a-Linux NewsLink 1.2