Counting Solutions of CSPs: A Structural Approach

摘要

Determining the number of solutions of a CSP has several applications in AI, in statistical physics, and in guiding backtrack search heuristics. It is a #P-complete problem for which some exact and approximate algorithms have been designed. Successful CSP models often use high-arity, global constraints to capture the structure of a problem. This paper exploits such structure and derives polytime evaluations of the number of solutions of individual constraints. These may be combined to approximate the total number of solutions or used to guide search heuristics. We give algorithms for several of the main families of constraints and discuss the possible uses of such solution counts.