CSP arc consistency: $x > y$, $x + y < 7$

306 Views Asked by At

Here is the question that is my problem:

Consider a CSP with variables $X$, $Y$ with domains $\{1, 2, 3, 4, 5, 6\}$ for $X$ and $\{2, 4, 6\}$ for $Y$, and constraints $X \gt Y$ and $X + Y \lt 7$. List the values that will remain in the domain of $X$ after enforcing arc consistency for the arc $X \to Y$ (recall arc consistency for a specific arc only prunes the domain of the tail variable, in this case $X$).

The possible solutions are:

  1. The resulting domain of $X$ is $\{3, 4, 5\}$
  2. The resulting domain of $X$ is $\{4, 5, 6\}$
  3. The resulting domain of $X$ is $\{1, 2, 3, 4\}$
  4. The resulting domain of $X$ is $\{3, 4\}$

I am having a hard time understanding how $x$ should be $\gt$ than $y$, when $x$ does not have any numbers greater than $6$.

2

There are 2 best solutions below

2
On BEST ANSWER

The correct answer is:

The resulting domain of $X$ is {$3$, $4$}

Because the only option for $Y$ is $Y=2$ which makes $X>Y$ and $X+Y<7$.

0
On

Note: $$\begin{cases}x>y\\ x+y<7\end{cases}\Rightarrow \begin{cases}-x+y<0\\ \ \ \ x+y<7\end{cases} \overbrace{\Rightarrow}^{+} y<3.5 \Rightarrow Y=\{2,4,6\}\backslash\{4,6\}=\{2\}.$$ Then: $$\begin{cases}x>2\\ x+2<7\end{cases}\Rightarrow\begin{cases}x>2\\ x<5\end{cases}\Rightarrow X=\{1,2,3,4,5,6\}\backslash\{1,2,5,6\}=\{3,4\}.$$