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

A solution is $(A,B,C,D,E,F,G)=(1,2,1,3,4,2,3)$. Here is a backtracking search with forward checking, listing the chosen value order rather than assuming ascending values. No backtrack is needed on this branch.

Start with the constraint domains in (a). Assign $A=1$; remove $1$ from $B,G,E$. Choose $E=4$; remove $4$ from each remaining neighbour. Now $B,G$ both have domain $\{2,3\}$ and $C,D,F$ each have $\{1,2,3\}$. Choose $B=2$. Its inequality removes $2$ from $G$, forcing $G=3$, and also removes $2$ from $D$, leaving $D\in \{1,3\}$. Assigning $G=3$ removes $3$ from $F$, leaving $F\in \{1,2\}$.

Choose $D=3$. The edge $DC$ reduces $C$ to $\{1,2\}$; $DF$ makes no further deletion because $3$ is already absent from $F$. Choose $F=2$ and then $C=1$. All variables are assigned, and every constrained pair has different values.

In time order, the schedule is

The Head of Department attends slots $1,2,3$ for $A,B,G$; first-year attendees see $C,D$ in slots $1,3$; second-year attendees see $F,G$ in $2,3$; the third-year Keble group sees $B,D$ in $2,3$; Physics attendees see $D,F$ in $3,2$. Slot $4$ is free of every competing talk, so all assumed society overlaps are respected.