Past exam of the computer science course of the University of Oxford / 2020 / Artificial intelligence / 2 / c / Solution

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:

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$:Now $b$ is the unique minimum remaining values choice. Set $b=2$. Forward checking removes $2$ from $c,e$, givingSelect $c$ and set $c=3$. Its remaining neighbors are $d,e$, so forward checking givesThe 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 pairsThe unary restrictions also hold. Equalities $a=e$ and $b=d$ are permitted because those pairs have no edges in the constraint graph.