= Solution
\b[One solution is $(a,b,c,d,e)=(1,2,3,2,1)$.] Use ascending value order; after <minimum remaining values> and the <degree heuristic>, break any remaining <variable> tie alphabetically. Apply the unary restrictions first:
$$
D_a=\{1,2\},\quad D_b=\{1,2,3\},\quad D_c=D_d=D_e=\{1,2,3,4\}.
$$
<Minimum remaining values> selects $a$, even though $c$ has greater initial <vertex degree>. Set $a=1$. <Forward checking> removes $1$ from the three neighbors $b,c,d$:
$$
D_b=\{2,3\},\quad D_c=D_d=\{2,3,4\},\quad D_e=\{1,2,3,4\}.
$$
Now $b$ is the unique <minimum remaining values> choice. Set $b=2$. <Forward checking> removes $2$ from $c,e$, giving
$$
D_c=\{3,4\},\quad D_d=\{2,3,4\},\quad D_e=\{1,3,4\}.
$$
Select $c$ and set $c=3$. Its remaining neighbors are $d,e$, so <forward checking> gives
$$
D_d=\{2,4\},\qquad D_e=\{1,4\}.
$$
The two remaining <variables> tie on <constraint domain> size and each has one unassigned neighbor, so the <degree heuristic> also ties. Alphabetical order selects $d$; take $d=2$. Since $2$ is already absent from $D_e$, <forward checking> makes no further deletion. Finally choose $e=1$. No empty <constraint domain> or violation occurs, so this branch needs no <backtracking>.
All eight <binary constraints> are checked explicitly by the unequal value pairs
$$
(a,b)=(1,2),\ (a,d)=(1,2),\ (a,c)=(1,3),\ (b,e)=(2,1),\ (b,c)=(2,3),\ (c,e)=(3,1),\ (c,d)=(3,2),\ (d,e)=(2,1).
$$
The unary restrictions also hold. Equalities $a=e$ and $b=d$ are permitted because those pairs have no <edges> in the <constraint graph>.
Back to article page
