2.1.7. Counting view

Considering a constraint for which not all variables are fixed yet, a question is to count, or estimate, its number of solutions. This is useful for writing heuristics that take into account the tightness of the constraints in order, for example, to select the next variable to assign. Considering a pure functional dependency constraint it is interesting to consider how the number of solutions of that constraint varies depending on the value of the pure functional dependency parameter (e.g.,Β in the context of the πš—πšŸπšŠπš•πšžπšŽ(𝙽,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚) constraint, its number of solutions if extremely low when 𝙽=1, then increase as 𝙽 increases up to a point where it decreases again and ends up with 𝙽=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| like an πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš). This is for instance useful for ranking pure functional dependency constraints in the context of the constraint seekerΒ [BeldiceanuSimonis11].

Counting the number of solutions to an πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint is equivalent to counting the number of maximum matchings in a bipartite graph, which is #P-completeΒ [Valiant79]. Consequently faster approximations for estimating the number of solutions are used in practiceΒ [ZanariniPesant10].