AI II

1) Consider the problem of constructing (not solving) crossword puzzles: ﬁtting words

into a rectangular grid. The grid, which is given as part of the problem, speciﬁes which

squares are blank and which are shaded. Assume that a list of words (i.e., a dictionary) is

provided and that the task is to ﬁll in the blank squares using any subset of the list. Formulate

this problem precisely in two ways:

a. As a general search problem. Choose an appropriate search algorithm, and specify a

heuristic function, if you think one is needed. Is it better to ﬁll in blanks one letter at a

time or one word at a time?

b. As a constraint satisfaction problem. Should the variables be words or letters?

Which formulation do you think will be better? Why?

2) What is the worst-case complexity of running AC-3 on a tree-structured CSP?

3) AC-3 puts back on the queue every arc (Xk , Xi ) whenever any value is deleted from

the domain of Xi , even if each value of Xk is consistent with several remaining values of Xi .

Suppose that, for every arc (Xk , Xi ), we keep track of the number of remaining values of Xi

that are consistent with each value of Xk . Explain how to update these numbers efﬁciently

and hence show that arc consistency can be enforced in total time O(n2 d2 ). (the latter subscripts should be superscripts.)

(Previous questions from Russell and Norvig chapter 5)

2006 P3Q3

2001 P9Q8

How might minimax be modified for 3 or 4 player games?

If you did not last week, attempt the question on recursive-best-first search