Приведенный выше алгоритм поиска с возвратами содержит следующую строку:

По умолчанию функция Select-Unassigned-Variable выбирает следующую переменную с неприсвоенным значением в порядке, указанном в списке Variables [csp]. Такое статическое упорядочение переменных редко приводит к наиболее эффективному поиску. Например, после присваиваний WA=red и NT= green остается только одно возможное значение для SA, поэтому имеет смысл на следующем этапе выполнить присваивание SA=blue, а не присваивать значение переменной Q. В действительности после присваивания значения переменной SA все варианты выбора значений для Q, NSW и V становятся вынужденными. Эта интуитивная идея (согласно которой в первую очередь следует выбирать переменную с наименьшим количеством "допустимых" значений) называется эвристикой с минимальным количеством оставшихся значений (Minimum Remaining Values — MRV). Эту эвристику называют также эвристикой с "переменной, на которую распространяется наибольшее количество ограниченной", или эвристикой "до первого неудачного завершения"; последнее название применяется потому, что такая эвристическая функция предусматривает выбор переменной, которая с наибольшей вероятностью вскоре приведет к неудаче, усекая тем самым дерево поиска. Если существует переменная х с нулевым количеством оставшихся допустимых значений, эвристическая функция MRV выберет X и неудача будет обнаружена немедленно; это позволяет избежать бессмысленных поисков среди других переменных, которые всегда будут оканчиваться неудачей после того, как в конечном итоге будет выбрана переменная х. Производительность поиска с использованием этой эвристической функции показана во втором столбце табл. 5.1, обозначенном как Поиск с возвратами на основе MRV. Производительность поиска повышается от 3 до 3000 раз по сравнению с простым поиском с возвратами, в зависимости от задачи. Следует отметить, что в применяемом здесь показателе производительности не учитывается дополнительная стоимость вычисления значений эвристической функции; в следующем подразделе описан метод, который позволяет удерживать это значение стоимости в приемлемых рамках.