Does it choose a variable or a value?

It chooses a variable. A value-ordering heuristic, such as least-constraining value, makes the next distinct choice.

Is higher degree always better?

No. It is a heuristic based on potential influence, not a guarantee of minimal search.

Does counting constraints equal counting neighbors?

In a simple binary graph with one edge per constrained pair they coincide. Multiple constraints per pair or higher-arity constraints require an explicit convention.

AI Glossary / Graphs and symbolic AI / Intermediate

Degree heuristic

Definition

The degree heuristic is a variable-selection rule for constraint satisfaction that prefers an unassigned variable involved in many constraints with other unassigned variables. It tries to make influential choices early, often as a tie-breaker after the minimum-remaining-values heuristic.

What it means

A constraint satisfaction problem assigns values to variables while meeting restrictions. Search can be much easier or harder depending on which variable is assigned next, even when the set of valid solutions is unchanged.

The degree heuristic focuses on connections: a variable affecting many unresolved neighbors may constrain a large portion of the remaining problem. Assigning it early can expose conflicts or reduce later choices.

This entry concerns constraint-solving search. It is related to counting graph connections, but it is not a general rule that the most connected node is always the most important or the best starting point for every graph algorithm.

How it works

For a binary constraint problem, form a graph with variables as vertices and an edge between variables that share a constraint. Among eligible unassigned variables, count connections to other unassigned variables and prefer a larger count.

A common combination first applies minimum remaining values, or MRV, which prefers the variable with the fewest currently legal values. The degree heuristic breaks a tie among those candidates by choosing the one constraining the largest number of other unassigned variables.

Counts can change as assignments are made. Static degree counts all original neighbors; a dynamic version emphasizes the still-unassigned neighbors. For constraints involving more than two variables, the implementation must specify what it counts. The heuristic guides search order but does not replace consistency checks or prove that the chosen branch will succeed.

Three practical examples

Timetabling: A scheduler selects a tied event that shares more unresolved room, instructor or participant restrictions.
Puzzle solving: A solver chooses a tied cell or variable that interacts with more unfilled positions.
Configuration: A product configurator selects a component choice that constrains several remaining components, hoping to reveal incompatibilities early.

Think of it this way

Think of resolving a meeting time that affects many other arrangements before deciding a less connected detail. This may reduce later revisions, but it is not guaranteed to be best: one quiet-looking requirement could still be the true bottleneck. The analogy explains search influence, not a rule for ranking people's importance.

Worked example

Consider five unassigned variables A, B, C, D and E. Their constraint graph has edges AB, AC, AD, BC, BE and CD.

The degrees are A = 3, B = 3, C = 3, D = 2 and E = 1. Suppose their currently legal domain sizes are A = 2, B = 2, C = 3, D = 2 and E = 1.

Using MRV first selects E because it has only one legal value. Degree does not override that decision in this combined policy, even though E is the least connected variable.

After assigning E, suppose propagation leaves two legal values each for A, B and D, while C still has three. The MRV candidates are now A, B and D. Count only unassigned neighbors: A connects to B, C and D, giving 3; B connects to A and C, giving 2; D connects to A and C, giving 2. The degree tie-breaker therefore selects A.

If the solver instead kept B's original degree of 3, it could treat A and B as tied. That would be a static-degree policy, not the dynamic count just described.

The graph alone does not tell us which value A should receive. Value ordering is a separate decision, and the domain sizes must be recomputed as required by the solver's propagation strategy.

Illustrative case study

Fictional case: Birch Schedules compares two search configurations for assigning workshop sessions. Both use MRV, but one breaks ties alphabetically while the other uses unresolved constraint degree.

The team records search nodes, backtracks and time spent calculating heuristic scores across several representative schedules. On some instances, selecting a highly connected session exposes conflicts early. On others, the extra counting work offers little benefit.

A review also finds that the prototype counts already assigned neighbors, despite documentation describing a dynamic heuristic. The team aligns the implementation and description before interpreting the results. It does not claim that one successful schedule proves universal superiority. The case illustrates an evaluation method rather than reporting measured performance gains.

Common misconceptions and mistakes

Degree and MRV are the same heuristic. Degree counts relevant connections; MRV counts remaining legal values.
The highest-degree variable must be assigned first. That is one policy, while MRV with degree tie-breaking can choose differently.
Degree never changes. Dynamic degree changes as neighbors are assigned.
A strong variable heuristic removes the need for backtracking. It can still choose values leading to dead ends.

Business use

The degree heuristic is inexpensive to explain and can be useful in constraint-based planning, scheduling and configuration. Its practical benefit depends on problem structure, propagation and the cost of maintaining the counts.

Specify the primary selection rule, tie-breakers and whether degree is static or dynamic. Benchmark the complete solver on representative instances, including difficult and unsatisfiable cases. Measure overhead as well as avoided search. For higher-arity constraints, document the scoring convention so that reported results can be reproduced and compared fairly.

Check your understanding

Two unassigned variables have equal smallest domain sizes. X constrains four other unassigned variables; Y constrains two. Which does the degree tie-breaker prefer?

Answer: X, under the stated dynamic-degree convention. This preference does not decide which value X receives.

Related terms

Learn next

Add an assignment to C in the worked graph and recalculate the remaining degrees. Then compare the degree policy with MRV and explain why domain sizes and graph connections carry different information about the search problem.

Sources

Russell and Norvig's constraint-satisfaction chapter explains degree-based variable selection and its use with MRV: https://aima.cs.berkeley.edu/2nd-ed/newchap05.pdf

The AIMA project provides supporting constraint-programming implementations and exercises: https://github.com/aimacode/aima-python

The five-variable calculation and Birch Schedules case are original illustrations. Static and dynamic counting conventions are explicitly distinguished so that the example does not imply a universal implementation policy.

Previous: Degree adverb Next: Degree of belief