Эта эвристическая функция MRV вообще не оказывает никакой помощи при выборе для окрашивания в Австралии первого региона, поскольку первоначально каждый регион имеет три допустимых цвета. В таком случае удобной становится степенняя эвристика. В этой эвристике предпринимается попытка уменьшить коэффициент ветвления в будущих вариантах за счет выбора переменной, которая участвует в наибольшем количестве ограничений на другие переменные с неприсвоенными значениями. На рис. 5.1 переменной с наибольшей степенью, 5, является переменная SА; другие переменные имеют степень 2 или 3, за исключением Т, которая имеет степень 0. В действительности после выбора переменной SA применение степенной эвристики позволяет решить задачу без каких-либо неудачных этапов — теперь можно выбрать любой согласованный цвет в каждой точке выбора и все равно прийти к решению без поиска с возвратами. Эвристика с минимальным количеством оставшихся значений обычно обеспечивает более мощное руководство, но степенная эвристика может оказаться полезной в качестве средства разрешения неопределенных ситуаций.

После выбора одной из переменных в этом алгоритме необходимо принять решение о том, в каком порядке должны проверяться ее значения. Для этого в некоторых случаях может оказаться эффективной эвристика с наименее ограничительным значением. В ней предпочитается значение, в котором из рассмотрения исключается наименьшее количество вариантов выбора значений для соседних переменных в графе ограничений. Например, предположим, что на рис. 5.1 сформировано частичное присваивание с WA=red и NT-green и что следующий вариант выбора предназначен для Q. Синий цвет был бы плохим вариантом, поскольку исключил бы последнее допустимое значение, оставшееся для соседней переменной относительно О, т.е. переменной SA. Поэтому эвристика с "наименее ограничительным значением" предпочитает значение red, а не blue. Вообще говоря, в этой эвристике предпринимается попытка сохранить максимальную гибкость для последующих присваиваний значений переменным. Безусловно, если бы мы стремились найти все решения некоторой задачи, а не первое из них, то такое упорядочение не имело бы значения, поскольку нам так или иначе пришлось бы рассмотреть каждое значение. Такое же замечание остается справедливым, если данная задача вообще не имеет решений.