1. A computer-implemented method for solving a Constraint Satisfaction Problem (CSP), the method performed by a computer having a processor, the method comprising: obtaining the CSP, the CSP comprising at least one constraint over a plurality of variables, the plurality of variables are associated with a plurality of domains; identifying a first constraint of the at least one constraint, the first constraint comprising a first component, the first component indicates performing a first relational operation between a first variable of the plurality of variables and a second variable of the plurality of variables; modifying the CSP to a modified CSP; said modifying the CSP comprises: adding a third variable to the CSP; determining a domain associated with the third variable based on a first domain associated with the first variable and based on a second domain associated with the second variable; adding the domain to the CSP; modifying the first component to a modified first component that indicates performing the first relational operation between the third variable and a constant; generating a third constraint that is satisfied in case the modified first component and the first component are either both satisfied or both unsatisfied; and adding the third constraint to the CSP; and solving the modified CSP by determining satisfiability of the modified CSP.