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

into a rectangular grid. The grid, which is given as part of the problem, specifies 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 fill 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 fill 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 efficiently 

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