Degree heuristic

Choose an unassigned variable constrained to the greatest number of other unassigned variables. This is commonly a tie-breaker after minimum remaining values. The relevant vertex degree is computed in the remaining constraint graph, rather than counting neighbors already assigned. It aims to make each decision constrain many future decisions without changing the solution set.