I want to apply AC-3 algorithm to the following CSP:
There are two variables $A$ and $B$.
Domain of $A: \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\} $
Domain of $B: \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\} $
The constraints:
$$A < B $$ $$B = A^2 $$
I'll apply the AC-3 algorithm depicted in Artificial Intelligence: A Modern Approach, 4th edition (figure 6.3)
Step 1. By converting constraints to arcs, our arc queue will be as following:
$$A < B $$ $$B > A $$ $$B = A^2 $$ $$A = \sqrt{B} $$
According to the algorithm, when processing an arc such as $(X_i, X_j)$, if the domain of $X_i$ was changed, all the arc that their destinations are $X_i$ and their source are a neighbor of $X_i$ must be add to the end of the arc queue except for $X_j$. Since we have only two variables, therefore I think we do not need to add any new arc to the queue.
Step 2. processing the arc queue:
- Applying $A < B$ reduces the domain of $A$ to $ \{ 0, 1, 2, 3, 4, 5, 6, 7, 8 \} $.
- Applying $B > A$ reduce the domain of $B$ to $ \{ 1, 2, 3, 4, 5, 6, 7, 8, 9 \} $.
- Applying $B = A^2$ reduces the domain of $B$ to $ \{ 1, 4, 9 \} $.
- Applying $A = \sqrt{B} $ reduces the domain of $A$ to $ \{ 1, 2, 3 \} $.
So, at the end, the domain of $A$ is $\{1, 2, 3\}$ and the domain of $B$ is $\{1, 4, 9\}$. But this answer is not correct. Since for $1$ belongs to the domain of $B$, there is no element in the domain of $A$ such that $ B < A $ satisfies.
It is obvious that the domains of the arc consistent CSP is as following:
- Domain of $A: \{2, 3\} $
- Domain of $B: \{4, 9\} $
What is my fault?
I think adding arc $(X_j, X_i)$ as well as other neighbor arcs $(X_k, X_i)$, when the domain of $X_i$ is reduced by applying arc $(X_i, X_j)$, leads to correct answer.
