Hidden transformation

The hidden transformation reformulates a constraint satisfaction problem in such a way all constraints have at most two variables.

If a problem has constraints with a larger arity (number of variables), conversion into a problem made of binary constraints allows for execution of these solving algorithms.

The number of variables in a constraint is called its arity.

The hidden transformation converts an arbitrary constraint satisfaction problem into a binary one.

The transformation is similar to that generating the dual problem.

The domain of each such variable is the set of satisfying tuples of the corresponding constraint.

The constraints of the new problem enforce the value of the original variables to be consistent with the values of the new variables.

The graph representing the result of this transformation is bipartite, as all constraints are between a new and an old variable.

Moreover, the constraints are functional: for any given value of a new variable, only one value of the old variable may satisfy the constraint.