How to turn a ternary constraint into three binary constraints?

Question

I'm trying to solve problem 6.6 from the book Artificial Intelligence: A Modern Approach, by Peter Norvig and Stuart Russell.

This is in the context of Constraint Satisfaction Problem and how you can re-formulate some problems with the constraints expressed as a bunch of binary constraints to use the generalized solver CSP algorithm.

But I'm stuck with that exercise, I can't sketch a demonstration.

6.6 Show how a single ternary constraint such as "A + B = C" can be turned into three binary constraints by using an auxiliary variable. You may assume finite domains.

(Hint: Consider a new variable that takes on values that are pairs of others values, and consider constraints such as "X is the first element of the pair Y.") Next, show how constraints can be eliminated by altering the domain of variables. This completes the demonstration that any CSP can be transformed into a CSP with only binary constraints.

Answer 1

Let $D_a$ be the domain for A, and $a_i$ the elements of $D_a$. Let $D_b$ and $D_c$ work similarly for $B$ and $C$ respectively.

We introduce $D_t = \{t | t = (c_i - b_j, c_i)\}$ for all $c_i$ in $D_c$ and $b_j$ in $D_b$. We can see that $\{t[0]\}$ (i.e. $\{c_i - b_j, \forall i,j\}$) must be equal to $D_a$.

So we can represent the constraint on $A$ by the relation $R_At = { (a_k, t_l) | a_k = t_l[0]}$ for $a_k$ in $D_a$ and $t_l$ in $D_t$. That is, $a_k$ must equal the first element in the pair from $t_l$, which means there is a $b_j$ and a $c_i$ consistent with that $a_k$.

The constraint on $B$ is the relation $R_{Bt} = \{(b_j, t_l) | b_j + t_l[0] = t_l[1]\}$. Since $t_l$[0] = $c_i - b_j$, $t_l$[0] + $b_j$ must equal $c_i$, which is t[1], so if this holds, there is a $b_j$ in $D_b$ that is consistent with $t_l$.

Lastly, $R_{Ct} = \{ (c_i, t_l) | c_i = t_l[1]\}$, which is really just an identity. So what we've done is solved $A + B = C$ for $A$ and encoded that into $R_{At}$. From that solution and knowledge of the original $C$ (stored in t[1]) we can re-create $C$ from a valid $B$, which is the $R_{Bt}$ relation.

And lastly $C$ must be in the original set of $C$'s used to build all the $t$'s. If all three of these constraints hold, then we must have a $C$, a $B$ used to solve for $A$, and an $A$ that matches that solution.

The second part is really just path-consistency. For every $A$, choose a $B$, and see if there's a possible $C = A + B$. If so, Add that those values to final domains $D_a$, $D_b$, and $D_c$. I forget if there's a better performing algorithm than this, but I doubt it since here you can use associativity of addition to avoid checking the opposite order of selecting $A$ and $B$. In general, you have to consider both orders.