Bayes Networks for Estimating the Number of Solutions to a CSP

Abstract

The problem of counting the number of solutions to a constraint satisfaction problem (CSP) is rephrased in terms of probability updating in Bayes networks. Approximating the probabilities in Bayes networks is a problem which has been studied for a while, and may well provide a good approximation to counting the number of solutions. We use a simple approximation based on independence, and show that it is correct for tree-structured CSPs. For other CSPs, it is a less optimistic approximation than those suggested in prior work, and experiments show that it is more accurate on the average. We present empirical evidence that our approximation is a useful search heuristic for finding a single solution to a CSP.