-
Notifications
You must be signed in to change notification settings - Fork 6
Description
A distinct is perhaps the most expensive constraint that we have because it builds a "pyramid" of propagators. One distrinct on n
variables causes n^2-1
propagators because it has to create an neq
for every pair of variables (but not to itself). Being able to eliminate some means a potential reduction of a lot.
Now solved variables in a distinct
are easily resolved. Say we have a var x
which is solved, we search for the value of x
in all the other vars. If we encounter it, we remove it from the domain. Then we drop this var from the list of vars for distinct
. Repeat for all vars.
In the real world this may not help much, but there's at least one case in the curator right now that does something "silly" like distinct([1,1], [2,2], [3,3], [4,4], [5,5], [6,6], [7,7], [8,8], [9,9], [10,10], [11,11], [12,12], [13,13], [14,14], [15,15], [16,16], [17,17], [18,18])
. That is a distinct
on 18 vars, causing 18^2-1=323
propagators for "obviously" no good reason. I mean, there's probably a reason, but finitedomain should definitely eliminate these cases as soon as possible and the generator should reconsider whether it actually needs to do this in the first place.