SDT Course, Constraints final – making the pruning more efficient


This page gives some hints on how to make the constraint endviews/5 do more pruning.

It may be worthwhile to implement some variation of a firstpos/2 constraint, with the following specification:

% firstpos(+L, +K): in list L, the first positive number is K. % It can be assumed that L is proper (i.e., not open-ended). The elements of L are FD-variables % or integers; it can be assumed that all elements of L are non-negative. K is a given positive integer. % firstpos/2 should prune as much as possible, but not perform labeling nor create any choice points. Note that the argument K is an integer and not a constraint variable. Given this, you can easily add a membership constraint (see slide 234) which prescribes that the first element of L is either 0 or K. This would result in the following behaviour: | ?- _L = [A,B,C], domain(_L, 0, 3), firstpos(_L, 2). A in{0}\/{2}, B in 0..3, C in 0..3 ? ; no It would be nice to make this pruning work for all initial elements of a list, in the following sense: if all elements before an element X become 0, then this pruning should be applied to X: | ?- _L = [A,B,C], domain(_L, 0, 3), firstpos(_L, 2), A=0. A = 0, B in{0}\/{2}, C in 0..3 ? ; no The problem with this approach is that, if you write a recursive definition for firstpos/2, you are forced to use a constraint variable instead of the constant K in the recursive call, because the first positive element of the tail is not necessarily the same as that of the whole list: firstpos([H|T], K) :- ... ... #=> K1 #= K, firstpos(T, K1). ... To overcome this problem I suggest an alternative approach, using the reified form of firstpos as a helper predicate: % firstpos(+L, +K, ?B): B is 1 if, and only if the first positive number in list L is K. (B is a Boolean, i.e. 0..1 valued variable) So keep passing the integer K the first positive element should be equal to, and maintain a boolean variable B which prescribes whether the first positive element should be K.
You can then add a reified constraint in the recursion, that whenever B is 1, then the first element of the list has to be either 0 or K.

Please send an email if you need further clarification or help.


Last modified by Péter Szeredi, szeredi@cs.bme.hu, on 11.12.2024.