Рассмотрена проблема подсчета количества решений залами совместимости ограничений (Constraint Satisfaction Problem). Для ее решения был адаптирован метод обратного прослеживания с ацикличным представлением графа ограничений (Backtracking with Tree-Decomposition). Предложен точный алгоритм, сложность котрого экспоненниально зависит от ширины дерева, и приближенный алгоритм, экспоненциально зависящий от размера максимальной клики. Ключевые слова: подсчет решений, задача совместимости ограничений, динамическое программирование, приближенный подсчет. хордальный граф, раскраска графа.
