DM826 - Modeling and Solving Constrained Optimization Problems
Sheet 2, Spring 2012 [pdf format]

Prepare the following exercises (together with those left from Sheet 1) for discussion in class on Monday 13th February 2012.

Exercise 1 Are the two following CSPs arc consistent:

• ⟨ {x=1,y∈{0,1},z∈{0,1}}; x ∧ y = z;⟩
• ⟨ {x∈{0,1},y∈{0,1},z=1}; x ∧ y = z;⟩

Exercise 2 Consider the n-queens problem with n≥ 3 and its formulation as CSP that uses the least variables (that is, n variables that indicate the position of the queens, say, on the columns). Is the initial status of this CSP problem arc consistent? If not, enforce arc consistency.

Exercise 3 Crossword puzzle Consider the crossword grid of Figure 1 and suppose we are to fill it with the words taken from the following list:

• HOSES, LASER, SAILS, SHEET, STEER,
• HEEL, HIKE, KEEL, KNOT, LINE,
• AFT, ALE, EEL, LEE, TIE.

Formulate the problem as a CSP.

Is the initial status of the formulated CSP arc consistent? If not, enforce arc consistency.

---

Figure 1: The crossword puzzle of exercise 2.

---