Binary Encodings

There are two well-known methods for transforming a non-binary CSP into a binary one; the dual graph encoding and the hidden variable encoding. Both encode the non-binary constraints to variables that have as domains the valid tuples of the constraints. That is, by building a binary encoding of a non-binary constraint we store the extensional representation of the constraint (the set of allowed tuples). A third method is the double encoding which combines the other two.