Использование поиска с возвратами для удовлетворения ограничений было предложено Битнером и Рейнгольдом [135], но эти ученые проследили истоки идей своего основного алгоритма до работ XIX века. Кроме того, Битнер и Рейнгольд впервые предложили использовать эвристику MRV, названную ими эвристикой с наиболее ограниченной переменной. Брелаз [181] использовал степенную эвристику для устранения неопределенности, возникающей после применения эвристики MRV. Полученный в итоге алгоритм, несмотря на его простоту, все еще остается наилучшим методом раскрашивания произвольных графов в к цветов. Харалик и Эллиот [618] предложили эвристику с наименее ограничительным значением.

Расширению популярности методов распространения ограничений способствовало успешное решение Вальцем [1552] задач полиэдральной линейной разметки для систем компьютерного зрения. Вальц показал, что применение методов распространения ограничений при решении многих задач позволяет полностью исключить необходимость в использовании возвратов. Монтанари [1073] ввел понятие сетей ограничений и предложил метод распространения ограничений на основе понятия совместимости пути. Ален Макворт [967] предложил алгоритм АС-3 для обеспечения совместимости дуг, а также выдвинул общую идею о том, что поиск с возвратами необходимо сочетать с обеспечением совместимости некоторой степени. Более эффективный алгоритм обеспечения совместимости дуг, АС-4, был разработан Мором и Хендерсоном [1068]. Вскоре после появления статьи Макворта исследователи приступили к экспериментам в области поиска компромисса между затратами на обеспечение совместимости и достигаемыми за счет этого преимуществами с точки зрения сокращения объема поиска. Харалик и Эллиот [618] предпочли минимальный алгоритм предварительной проверки, описанный Макгрегором [1028], а Гашниг [522] предложил применять полную проверку совместимости дуг после присваивания значения каждой переменной; в дальнейшем соответствующему алгоритму в работе Сабина и Фрейдера [1335] было присвоено название MAC. В последней статье представлены некоторые убедительные свидетельства того, что при решении более трудных задач CSP полная проверка совместимости дуг вполне окупается. Фрейдер [497], [498] исследовал понятие k-совместимости и ее связь со сложностью решения задач CSP. Апт [36] описал универсальную алгоритмическую инфраструктуру, в рамках которой могут быть проанализированы алгоритмы распространения совместимости.

Специальные методы обработки ограничений высокого порядка были созданы в основном в контексте логического программирования в ограничениях. Превосходный обзор исследований в этой области приведен в [987]. Ограничение Alldiff исследовалось в [1272]. Ограничения с пределами были включены в тематику логического программирования в ограничениях ван Хентенриком и др. [1533].