Исследования, касающиеся структуры и сложности задач CSP, начались с [499], где было показано, что поиск в деревьях с совместимыми дугами происходит без каких-либо возвратов. Аналогичные результаты применительно к ациклическим гиперграфам были получены в области теории баз данных [92]. Со времени публикации этих статей достигнут значительный прогресс в части получения более общих результатов, касающихся связи между сложностью решения задачи CSP и структурой ее графа ограничений. Понятие ширины дерева было введено специалистами по теории графов Робертсоном и Сеймуром [1295]. Дектер и Перл [372], [373], основываясь на работе Фрейдера, применяли то же понятие (названное ими индуцированной шириной) к задачам удовлетворения ограничений и разработали подход с древовидной декомпозицией, кратко описанный в разделе 5.4. Опираясь на эту работу и на результаты из области теории баз данных, Готлобб и др. [585], [586] разработали понятие ширины гипердерева, которое основано на методе характеризации задачи CSP как гиперграфа. Они не только показали, что любую задачу CSP с шириной гипердерева w можно решить за время, но и обосновали утверждение, что критерий ширины гипердерева превосходит все ранее предложенные критерии "ширины" в том смысле, что в некоторых случаях ширина гипердерева является конечной, тогда как ширина, определяемая другими критериями, — неограниченной.

В литературе можно найти несколько хороших обзоров с описанием методов решения задач CSP, включая [73], [370] и [866], а также энциклопедические сборники статей [368] и [968]. В [1194] приведен обзор разрешимых классов задач CSP и описаны как методы структурной декомпозиции, так и методы, основанные на свойствах областей определения или свойствах самих ограничений. В [831] приведен аналитический обзор алгоритмов поиска с возвратами, а в [56] приведен обзор, характеризующийся большей практической направленностью. В [987] и [1514] эта тематика рассматривается гораздо более глубоко, чем было возможно ее представить в данной главе. Некоторые интересные приложения описаны в сборнике статей [500], который вышел под редакцией Фрейдера и Макворта. Статьи на тему удовлетворения ограничений регулярно публикуются в журнале Artificial Intelligence и в специализированном журнале Constraints. Основным местом встречи специалистов в этой области является конференция International Conference on Principles and Practice of Constraint Programming, часто называемая просто СР.