Каждая подзадача решается независимо; если какая-либо из них не имеет решения, то известно, что вся задача также не имеет решения. Если удается решить все подзадачи, то может быть предпринята попытка составить глобальное решение следующим образом. Прежде всего, каждая подзадача рассматривается как "мегапеременная", областью определения которой является множество всех решений этой подзадачи. Например, самая левая подзадача на рис. 5.8 представляет задачу раскрашивания карты с тремя переменными и поэтому имеет шесть решений; одним из них является. Затем решается задача с ограничениями, связывающими подзадачи; для этого используется эффективный алгоритм для деревьев, приведенный выше. Ограничения, связывающие подзадачи, указывают на то, что решения подзадач должны быть согласованными по их общим переменным. Например, если за основу берется решение первой подзадачи {WA=redf SA=bluef NT= green], то единственным совместимым решением для следующей подзадачи становится

Рис. 5.8. Древовидная декомпозиция графа ограничений, показанного на рис. 5.7, а

Любой конкретный граф ограничений допускает большое количество древовидных декомпозиций; при выборе декомпозиции нужно стремиться к тому, чтобы подзадачи были как можно меньше. Ширина дерева древовидной декомпозиции графа на единицу меньше размера наибольшей подзадачи; ширина дерева самого графа определяется как минимальная ширина дерева среди всех его древовидных декомпозиций. Если граф имеет ширину дерева w и дана соответствующая древовидная декомпозиция, то соответствующая задача может быть решена за время . Это означает, что задачи CSP с графами ограничений, характеризующимися конечной шириной дерева, могут быть решены за полиномиальное время. К сожалению, задача поиска декомпозиции с минимальной шириной дерева является NP-трудной, но существуют эвристические методы, которые хорошо работают на практике.