2) A classic example of a constraint satisfaction problem is a crossword puzzle. This example contains six three-letter words: three words across (labeled A1, A2, A3) and three words down (labeled D1, D3, D3). Each word must be chosen from the list of forty possible words shown on the right. A1.D1 D2 D3 add, ado, age, ago, aid, ail, aim, air, and, any, ape, apt, arc, are, ark, arm, art, ash, A2 ask, auk, awe, awl, aye, bad, bag, ban, bat, bee, boa, ear, eel, eft, far, fat, fit, lee, oaf, rat, tar, tie. A3 a) There are many alternate representations in terms of variables, including: i) A representation where the domains of the variables correspond to words in English. ii) A representation where the domains of the variables correspond to letters of the alphabet. For each of these representations, describe the set of variables, give the number of variables that would be needed to capture the specific puzzle shown above. b) Using the first of these representations, draw the constraint graph for this problem. c) Apply arc-consistency in this graph, and give the (possibly) reduced domain of each variable. d) Apply backtracking search, with the relevant heuristics (minimum-remaining-values, degree, least-constraining-value) to solve this problem. Break ties using alphabetical ordering. Give your final solution. 2) A classic example of a constraint satisfaction problem is a crossword puzzle. This example contains six three-letter words: three words across (labeled A1, A2, A3) and three words down (labeled D1, D3, D3). Each word must be chosen from the list of forty possible words shown on the right. A1.D1 D2 D3 add, ado, age, ago, aid, ail, aim, air, and, any, ape, apt, arc, are, ark, arm, art, ash, A2 ask, auk, awe, awl, aye, bad, bag, ban, bat, bee, boa, ear, eel, eft, far, fat, fit, lee, oaf, rat, tar, tie. A3 a) There are many alternate representations in terms of variables, including: i) A representation where the domains of the variables correspond to words in English. ii) A representation where the domains of the variables correspond to letters of the alphabet. For each of these representations, describe the set of variables, give the number of variables that would be needed to capture the specific puzzle shown above. b) Using the first of these representations, draw the constraint graph for this problem. c) Apply arc-consistency in this graph, and give the (possibly) reduced domain of each variable. d) Apply backtracking search, with the relevant heuristics (minimum-remaining-values, degree, least-constraining-value) to solve this problem. Break ties using alphabetical ordering. Give your final solution