Задачи удовлетворения ограничений (Constraint Satisfaction Problems — CSP) состоят из переменных с налагаемыми на них ограничениями. В виде задач CSP могут быть описаны многие важные задачи реального мира. Структуру любой задачи CSP можно представить в виде ее графа ограничений.

Для решения задач CSP обычно применяется поиск с возвратами — одна из форм поиска в глубину.

Независимыми от области определения методами выявления того, какая переменная должна быть выбрана следующей в ходе поиска с возвратами, являются эвристики, основанные на определении минимального количества оставшихся значений, и степешше эвристики. Для упорядочения значений переменной может применяться эвристика с наименее ограничительным значением.

В алгоритме поиска с возвратами можно намного сократить коэффициент ветвления задачи, распространяя последствия частичных присваиваний, сформированных в ходе работы этого алгоритма. Простейшим методом такого распространения является предварительная проверка. Более мощным методом является обеспечение совместимости дуг, но применение этого метода может оказаться более дорогостоящим.

Возврат происходит после того, как для переменной нельзя больше найти допустимое присваивание. При использовании обратного перехода, управляемого конфликтами, возврат происходит непосредственно к источнику проблемы, возникшей в процессе поиска.

Для решения задач с ограничениями весьма успешно используется локальный поиск на основе эвристики с минимальными конфликтами.

Сложность решения задачи CSP в значительной степени зависит от структуры ее графа ограничений. Задачи с древовидной структурой могут быть решены за линейное время. Метод определения условий формирования множества разрыва цикла позволяет преобразовать задачу CSP общего вида в задачу с древовидной структурой и является очень эффективным, если существует возможность найти небольшое множество разрыва цикла. Методы древовидной декомпозиции предусматривают преобразование задачи CSP в дерево подзадач и являются эффективными, если ширина дерева графа ограничений мала.