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 $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$$(𝙽,\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂})$ 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 $𝙽=\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right|$ like an $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$). 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 $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ 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].