Основной метод обратного перехода был разработан Джоном Гашнигом [521], [522]. Кондрак и ван Бик [831] показали, что этот алгоритм по сути перекрывается алгоритмом предварительной проверки. Обратный переход, управляемый конфликтами, был предложен Проссером [1240]. Наиболее общая и мощная форма интеллектуального поиска с возвратами фактически разработана еще довольно давно Стал-маном и Зюссманом [1456]. Предложенный ими метод поиска с возвратами, управляемого зависимостями, привел к разработке систем обеспечения истинности [409], которые будут рассматриваться в разделе 10.8. Связь между этими двумя научными областями проанализирована в [348].

В указанной работе Сталмана и Зюссмана была также предложена идея регистрации ограничения, в соответствии с которой частичные результаты, полученные в ходе поиска, можно сохранять и повторно использовать на последующих этапах этого поиска. Данная идея была введена формально в поиск с возвратами Дектером [366]. Особенно простым методом является ^ проставление обратных отметок [522], в котором для предотвращения повторной проверки ограничений сохраняются и используются совместимые и несовместимые попарные присваивания. Проставление обратных отметок можно комбинировать с обратным переходом, управляемым конфликтами; в [831] представлен гибридный алгоритм, который превосходит любой из этих методов, отдельно взятых (и это подтверждается формальным доказательством). В методе динамического поиска с возвратами [558] сохраняются успешные частичные присваивания из полученных позднее подмножеств переменных при поиске с возвратами по предыдущему варианту, который не влияет на дальнейший успех.

Применение локального поиска при решении задач удовлетворения ограничений стало популярным после публикации [799] с описанием метода эмуляции отжига (см. главу 4), который широко используется для решения задач планирования. Эвристика с минимальными конфликтами была впервые предложена в [601] и независимо разработана в [1058]. В [1447] показано, как эта эвристика может использоваться для решения задачи с 3 000 000 ферзей меньше чем за минуту. Этот поразительный успех локального поиска на основе эвристики с минимальными конфликтами при решении задачи с п ферзями привел к переоценке характера и распространения "легких"и "трудных" задач. В [244] исследовалась сложность задач CSP, сформированных случайным образом, и было обнаружено, что почти все такие задачи являются либо тривиально легкими, либо не имеют решений. "Трудные" экземпляры задач встречаются, только если параметры генератора задач устанавливаются в некотором узком диапазоне, в пределах которого лишь примерно половина задач является разрешимой. Этот феномен рассматривается дополнительно в главе 7.