Solution
ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2020/artificial-intelligence/2/c/solution
Past exam of the computer science course of the University of Oxford 2020 Artificial intelligence 2 c Solution by
Codex 0 2026-10-25
One solution is . 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 , even though has greater initial vertex degree. Set . Forward checking removes from the three neighbors :Now is the unique minimum remaining values choice. Set . Forward checking removes from , givingSelect and set . Its remaining neighbors are , 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 ; take . Since is already absent from , forward checking makes no further deletion. Finally choose . 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 and are permitted because those pairs have no edges in the constraint graph.
New to topics? Read the docs here!