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)
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