An instance of a constraint satisfaction problem [1]} is a triple \(\mathcal {I}=\langle {\it Var},U,\) , where \({\it Var}\)  is a finite set of
variables, \(U\)  is a finite domain of values, and \(\lbrace C_1,C_2,\ldots ,C_q\rbrace \)  is a finite set of constraints. Each constraint \(C_v\) , for \(1\le v\le q\) , is a pair \((S_v,r_v)\) , where \(S_v\subseteq {\it Var}\)  is a set of variables called the constraint scope, and \(r_v\)  is a set of
substitutions (also called tuples) from variables in \(S_v\)  to values in \(U\)  indicating the allowed combinations of simultaneous values
for the variables in \(S_v\) . Any substitution from a set of variables \(V\subseteq {\it Var}\)  to \(U\)  is extensively denoted as the set of pairs
of the form \(X/u\) , where \(u\in U\)  is the value to which \(X\in V\)  is mapped. Then, a solution to \(\mathcal {I}\)  is a substitution \(\theta :{\it Var}\mapsto U\)  for which \(q\) -tuples \(t_1\in r_1,...,t_q\in r_q\)  exist such that \(\theta =t_1\cup ...\cup t_q\) .
