Sheet 3

Task 1 - Modelling

Show that CSP generalizes SAT formulating the following SAT problem as a CSP:

Task 2 - Binary CSP

Show how an arbitrary (non-binary) CSP can be polynomially converted into an equivalent binary CSP.

Task 3 - Domain-based tightenings

Given two CSP, $\cal P$ and $\cal P’$, we write ${\cal P’} \preceq {\cal P}$ iff any instantiation $I$ on $Y \subseteq X_{\cal P}$ locally inconsistent in $\cal P$ is locally inconsistent in $\cal P’$ as well.

Consider the following CSP:

${\cal P}=\langle X=\{x,y\}, {\cal DE}\equiv\{D(x)=\{1,2,3\},D(y)=\{1,2,3\}\}, {\cal C}\rangle$.

Construct two domain tightenings $\mathcal{P}_1$ and ${\cal P}_2$ of $\cal P$ (a domain tightening is $\cal P’$ such that $X_{\cal P’}=X_{\cal P}$, ${\cal DE}’ \subseteq {\cal DE}, {\cal C}_{\cal P’}={\cal C}_{\cal P}$) for which the relation $\preceq$ defined above is in fact a partial order. (Assume ${\cal C}$ admits any combination of values as valid.)

Task 4 - Local Consistency

Are the two following CSPs arc consistent?

• $\langle \{x=1,y\in\{0,1\},z\in\{0,1\}\}; x \wedge y = z;\rangle$

• $\langle \{x\in\{0,1\},y\in\{0,1\},z=1\}; x \wedge y = z;\rangle$

Task 5 - Local Consistency

Consider the $n$-queens problem with $n\geq 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.

Task 6 - Propagation on paper

Consider an initial domain expression $\{x \in \{0, 1, 2, 3\}, y \in \{0, 1, 2, 3\}\}$ and two constraints $x < y$ and $y < x$. Apply the propagation algorithm Revise2001 from the lecture using pen and paper.

Task 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 $\langle x \in [2..10], y\in [3..7], x<y\rangle$ is directed arc consistent in the case of linear ordering $y \prec x$ and in the case $x \prec y$.

Task 8 - Crossword puzzle

Consider the crossword grid

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.