Prepare the following exercises for discussion in class on Thursday 13th October 2016.
Exercise 1 – Modelling
Show that CSP generalizes SAT formulating the following SAT problem as a CSP:
| (x ∨ y ∨ ¬ z) ∧ (¬ w ∨ ¬ z) ∧ (w ∨ ¬ y ∨ z) |
Exercise 2 – Binary CSP
Show how an arbitrary (non-binary) CSP can be polynomially converted into an equivalent binary CSP.
Exercise 3 – Local Consistency
Are the two following CSPs arc consistent:
Exercise 4 – Local Consistency
Consider the n-queens problem with n≥ 3 and its formulation as a binary 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 5 – Domain-based tightenings
Given two CSP P and P′, we write P′ ≼ P iff any instantiation I on Y ⊆ X P locally inconsistent in P is locally inconsistent in P′ as well.
Consider the following CSP: P=⟨ X={x,y}, DE≡{D(x)={1,2,3},D(y)={1,2,3}}, C⟩. Construct two domain tightenings P1 and P2 of P (a domain tightening is P′ such that X P′=X P, DE′ ⊆ DE, C P′= C P) for which the relation ≼ defined above is in fact a partial order. (Assume C admits any combination of values as valid.)
Exercise 6 – Propagation on paper
Consider an initial domain expression {x ∈ {0, 1, 2, 3}, y ∈ {0, 1, 2, 3}} and two constraints x < y and y < x. Apply the propagation algorithm Revise2001 from the lecture using pen and paper.
Exercise 7 – Directed Arc Consistency
A form of weaker arc consistency is directed arc consistency, which enforces consistency only in one direction. Decide if the following CSP ⟨ x ∈ [2..10], y∈ [3..7], x<y⟩ is directed arc consistent in the case of linear ordering y ≺ x and in the case x ≺ y.
Exercise 8 – Crossword puzzle
Is the initial status of the CSP formulation of the crossword puzzle saw in class arc consistent? If not enforce arc consistency.