Approximate Counting CSP Solutions Using Partition Function
  We propose a new approximate method for counting the number of the solutions
for constraint satisfaction problem (CSP). The method derives from the
partition function based on introducing the free energy and capturing the
relationship of probabilities of variables and constraints, which requires the
marginal probabilities. It firstly obtains the marginal probabilities using the
belief propagation, and then computes the number of solutions according to the
partition function. This allows us to directly plug the marginal probabilities
into the partition function and efficiently count the number of solutions for
CSP. The experimental results show that our method can solve both random
problems and structural problems efficiently.
