COMPUTER SCIENCE TRIPOS Part IB – 2020 – Paper 6
Artificial Intelligence (sbh11)
A constraint satisfaction problem (CSP) has four variables V1, V2, V3, V4, each with
domain {1, 2}. The constraints for the problem require that given any three variables
exactly one must have the value 1.
(a) Explain how this problem can be represented as a CSP that uses only binary
constraints. Illustrate your answer by giving a graph representing the problem.
[4 marks]
(b) Describe how forward checking can be used to aid the search for a solution to a
CSP. Illustrate your answer by showing how it applies to the problem in Part (a),
for assignments V1 = 1 followed by V2 = 2. [4 marks]
(c) Describe the AC-3 algorithm for imposing consistency in a CSP. Include in your
answer descriptions of an arc, what it means for an arc to be consistent, how
a non-consistent arc can be made consistent, and the overall operation of the
algorithm. [6 marks]
(d) Consider again the problem in Part (a). We initially have no assignments, and
start by setting V1 = 1. Explain in detail what happens if we attempt to adjust
the domains to impose consistency. [6 marks]