Search Strategies and Decision Heuristics

A CP solver explores a search tree by repeatedly picking an unassigned variable, branching on its possible values, and propagating constraints. The order in which variables are chosen has an enormous effect on how quickly the solver finds a solution or proves none exists.

A variable-selection heuristic decides which variable to branch on next. The classic choice is the first-fail principle: branch on the variable that is most likely to fail soon. Its standard implementation is smallest domain first — pick the variable whose remaining domain $D(x)$ has the fewest values.

The intuition is simple. If a subtree is going to fail, it should fail cheaply, near the root. A variable with $|D(x)|=2$ creates only two branches; one with $|D(x)|=100$ creates a hundred. Resolving the small-domain variable first prunes the tree earlier.

Example. At some node, three variables are still unassigned:

$$x \in \{1,2,3,4,5\}, \quad y \in \{2,7\}, \quad z \in \{0,3,4,9\}.$$

The domain sizes are $|D(x)|=5,\;|D(y)|=2,\;|D(z)|=4.$ The first-fail heuristic branches on $y$ next.