Description

(a) Crossword puzzle: shown below. We want to 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.

(b) Independent set: Given a graph and a number k, find an independent set of size k, that is, a set of k vertices, no two of which are adjacent.
(c) Crypto-arithmetic puzzle: SEND + MORE = MONEY. We want to replace each letter by a different digit so that the equation is correct.
2. Consider a scheduling problem, where there are five activities to be scheduled in four time slots. Suppose we represent the activities by the variables A,B,C,D,E, where the domain of each variable is {1,2,3,4} and the constraints are A > D,D > E,C 6= A,C > E,C 6= D,B ≥ A,B 6= C, and C 6= D +1.
(a) Find the first solution by using the Forward Checking algorithm with the MRV heuristics that we always instantiate next that variable with smallest remaining number of elements in its domain, breaking ties in alphabetic order. Assign values in the current domain of each variable in increasing order. At each node indicate
ii. The CurDom for each variable.
iii. Mark any node with an empty CurDom with DWO.
(b) Enforce GAC on the constraints, and give the resultant variable domains. You should show which values of a domain are removed at each step, and which arc is responsible for removing the value. Then use the GAC algorithm to find the first solution.
3. Determine whether the following sentence is valid using resolution:
(∃x∀yP(x,y)∨∃x∀yQ(x,y)) →∃x∀y(P(x,y)∨ Q(x,y))
4. Victor has been murdered, and Arthur, Bertram, and Carleton are the only suspects (meaning exactly one of them is the murderer). Arthur says that Bertram was the victim’s friend, but that Carleton hated the victim. Bertram says that he was out of town the day of the murder, and besides, he didn’t even
1
(a) Use Resolution to find the murderer. In other words, formalize the facts as a set of clauses, prove that there is a murderer, and extract his identity from the derivation.
2