Exercise 4.3 Consider the crossword puzzle shown in Figure 4.14 . The available words that can be used are at, eta, be, hat, he, her, it, him, on, one, desk, dance, usage, easy, dove, first, else, loses, fuels, help, haste, given, kind, sense, soon, sound, this, think.

(a) Given the representation with nodes for the positions (1-across, 2-down, etc.)
and words for the domains, specify the network after domain consistency and arc consistency have halted.

(b) Consider the dual representation, in which the squares on the intersection of words are the variables and their domains are the letters that could go in these positions. Give the domains after this network has been made arc consistent. Does the result after arc consistency in this representation correspond to the result in part (a)?

(c) Show how variable elimination can be used to solve the crossword problem.
Start from the arc-consistent network from part (a).

(d) Does a different elimination ordering affect the efficiency? Explain.