В предыдущем разделе приведена формулировка задач CSP в виде задач поиска.Если используется такая формулировка, то появляется возможность решать задачи CSP с помощью любых алгоритмов поиска.

Предположим, что мы применяем алгоритм поиска в ширину к универсальной формулировке задачи CSP, приведенной в предыдущем разделе. Но мы быстро обнаружим нечто ужасное: коэффициент ветвления на верхнем уровне равен nd, поскольку любое из d значений может быть присвоено любой из n переменных. На следующем уровне коэффициент ветвления равен (n-1) d и т.д., на всех nп уровнях. При этом создается дерево n!dⁿ ветвями, даже несмотря на то, что имеется только dⁿ возможных олных присваиваний!

В применяемой нами формулировке задачи, которая внешне казалась разумной, но оказалась плохо продуманной, не было учтено существенно важное войство, общее для всех задач CSP, —  коммутативность. Задача называется коммутативной, если порядок применения любого конкретного множества действий в процессе ее решения не влияет на результат. Именно это свойство характерно для задач CSP, поскольку, присваивая значения переменным, мы достигаем одного и того же частичного присваивания независимо от порядка присваивания. Поэтому во всех алгоритмах поиска CSP преемники формируются с четом возможных присваиваний только для единственной переменной в каждом узле дерева поиска. Например, в корневом узле дерева поиска в задаче раскрашивания карты Австралии можно иметь выбор между SA=red, SA= green и
SA=blue, но мы никогда не должны выбирать между SA=red и WA=blue. Определив такое условие, можно надеяться сократить количество листьев до dⁿ.

Поиск в глубину, в котором каждый раз выбираются значения для одной переменной и выполняется возврат, если больше не остается допустимых значений, которые можно было бы присвоить переменной, называется ^ поиском с возвратами. Этот алгоритм поиска приведен в листинге. Обратите внимание на то, что в этом алгоритме по существу используется метод инкрементного
формирования преемников по одному преемнику за один раз. Кроме того, для формирования преемника текущее присваивание дополняется, а не копируется. Поскольку это представление задач CSP стандартизировано, то в функции Backtracking-Search не требуется учитывать начальное состояние, функцию определения преемника или проверку цели, характерные для рассматриваемой проблемной области. Часть дерева поиска для задачи раскраски карты Австралии показана, где значения присваиваются переменным в порядке WA, NT, Q,... .

Простой алгоритм поиска с возвратами для решения задач удовлетворения ограничений CSP. Этот алгоритм составлен по принципу рекурсивного поиска в глубину. Функции Select-Unassigned-Variable и Order-Domain-Values могут использоваться для реализации эвристических функций общего назначения
function Backtracking-Search(csp) returns решение result
  или индикатор отказа failure
  return Recursive-Backtracking({}, csp)
function Recursive-Backtracking{assignment, csp) returns решение result
  или индикатор отказа failure
  if присваивание assignment является полным then return assignment
  var <— Select-Unassigned-Variable(Variables[csp], assignment, csp)
  for each value in Order-Domain-Values(var, assignment, csp) do
     if значение value является совместимым с присваиванием
    assignment согласно ограничениям Constraints[csp] then
    добавить {var = value} к присваиванию assignment
    result <— Recursive-Backtracking{assignment, csp)
    if result Ф failure then return result
    удалить {var = value} из присваивания assignment
return failure

Часть дерева поиска, сформированного путем простого поиска с возвратами при решении задачи раскрашивания карты

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

• Какой переменной должно быть присвоено значение в следующую очередь и в каком порядке необходимо пытаться присваивать эти значения?
• Как влияют текущие присваивания значений переменным на другие переменные с неприсвоенными значениями?
• Если какой-то путь оказался неудачным (т.е. достигнуто состояние, в котором ни одна переменная не имеет допустимых значений), позволяет ли поиск избежать повторения этой неудачи при прохождении последующих путей?

В приведенных ниже подразделах по очереди даны ответы на каждый из этих вопросов.
Результаты применения различных алгоритмов CSP для решения разных задач. Слева направо показаны алгоритмы простого поиска с возвратами, поиска с возвратами на основе эвристической функции MRV, локального поиска с предварительной проверкой, локального поиска с редварительной проверкой на основе MRV и локального поиска с минимальными конфликтами. В каждой ячейке показано среднее количество проверок совместимости (за пять прогонов), которые  отребовались для решения данной задачи; обратите внимание на то, что все эти числа, кроме двух, находящихся вверху справа, выражены в тысячах (К). Числа в круглых скобках показывают, что за назначенное количество проверок не было найдено ни одного ответа. Первой задачей является поиск раскраски в 4 цвета для 50 штатов США. Остальные задачи взяты из [56]. Во второй задаче подсчитывается общее количество проверок, необходимых для решения всех задач с n ферзями для л от 2 до 50. Третьей задачей является "головоломка с зеброй", которая описана в упр. 5.13. Последние две задачи представляют собой искусственные задачи, формируемые случайным образом (алгоритм с минимальными конфликтами к ним не применялся). Эти результаты показывают, что предварительная проверка на основе эвристической функции MRV является лучшим способом решения всех этих задач по сравнению с другими алгоритмами поиска с возвратами, но этот метод не всегда превосходит локальный поиск с минимальными конфликтами