A CSP is modified to include an auxiliary variable. A component of a constraint of the CSP is modified to refer to the auxiliary variable instead of referring to a pair of variables. A domain for the auxiliary variable may be defined based on domains of the pair of variables. A binding constraint is added to the CSP to bind the value of the auxiliary variable with the values of the pair of variables. The modified CSP is solved using a CSP solver.