2002 | OriginalPaper | Chapter
Determining the Number of Solutions to Binary CSP Instances
Authors : Ola Angelsmark, Peter Jonsson, Svante Linusson, Johan Thapper
Published in: Principles and Practice of Constraint Programming - CP 2002
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Counting the number of solutions to CSP instances has applications in several areas, ranging from statistical physics to artificial intelligence. We give an algorithm for counting the number of solutions to binary CSPs, which works by transforming the problem into a number of 2-sat instances, where the total number of solutions to these instances is the same as those of the original problem. The algorithm consists of two main cases, depending on whether the domain size d is even, in which case the algorithm runs in time, or odd, in which case it runs in if d = 4 · k + 1, and if d = 4 · k + 3. We also give an algorithm for counting the number of possible 3-colourings of a given graph, which runs in , an improvement over our general algorithm gained by using problem specific knowledge.