Exercise 4.1 Consider the crossword puzzle shown in Figure 4.13. Youmust find six three-letter words: three words read across (A1, A2, and A3) and three words read down (D1, D2, and D3). Each word must be chosen from the list of forty possible words shown. Try to solve it yourself, first by intuition, then by hand using first domain consistency and then arc consistency.

There are at least two ways to represent the crossword puzzle shown in Figure 4.13 as a constraint satisfaction problem.

The first is to represent the word positions (A1, A2, A3, D1, D2, and D3) as variables, with the set of words as possible values. The constraints are that the letter is the same where the words intersect.

The second is to represent the nine squares as variables. The domain of each variable is the set of letters of the alphabet, {a,

b, . . . , z}. The constraints are that there is a word in the word list that contains the corresponding letters. For example, the top-left square and the center-top square cannot both have the value a, because there is no word starting with aa.

(a) Give an example of pruning due to domain consistency using the first representation

(if one exists).

(b) Give an example of pruning due to arc consistency using the first representation

(if one exists).

(c) Are domain consistency plus arc consistency adequate to solve this problem using the first representation? Explain.

(d) Give an example of pruning due to domain consistency using the second representation (if one exists).

(e) Give an example of pruning due to arc consistency using the second representation (if one exists).

(f) Are domain consistency plus arc consistency adequate to solve this problem using the second representation?
(g) Which representation leads to a more efficient solution using consistencybased techniques? Give the evidence on which you are basing your answer.