values which xi may take; and C is a set of e constraints {c1, c2*, ..., c*e} between variables in subsets of X. Each ci ∈ C expresses a relation defining which variable assignment combinations are allowed for the variables in the scope of the constraint, *vars(*ci). Two variables are said to be *neighbors* if they share a constraint. The *arity* of a constraint is the number of variables in the scope of the constraint. The *degree* of a variable xi, denoted by Γ(xi), is the number of constraints in which xi participates. A binary constraint between variables xi and xj will be denoted by cij .

A partial assignment is a set of tuple pairs, each tuple consisting of an instantiated variable and the value that is assigned to it in the current search node. A full assignment is one containing all n variables. A solution to a CSP
is a full assignment such that no constraint is violated.

In binary CSPs any constraint cij defines two directed arcs (xi,xj ) and
(xj ,xi). A directed constraint (xi,xj ) is *arc consistent* (AC) iff for every value a ∈ D(xi) there exists at least one value b ∈ D(xj ) such that the pair (a,b) satisfies cij . In this case we say that b is a *support* of a on the directed constraint
(xi,xj ). Accordingly, a is a support of b on the directed constraint (xj ,xi). A
problem is AC iff there are no empty domains and all arcs are AC. Enforcing AC on a problem results in the removal of all non-supported values from the domains of the variables. The definition of arc consistency for non-binary constraints, usually called *generalized arc consistency* (GAC), is a direct extension of the definition of AC. A non-binary constraint c, with *vars*(c)={x1, x2*, ..., x*k}, is GAC iff for every variable xi ∈ *vars*(c) and every value a ∈ D(xi) there exists a tuple τ that satisfies c and includes the assignment of a to xi[28, 26]. In this case τ is a support of a on constraint c. A problem is GAC iff all constraints are GAC. In the rest of the paper we will assume that (G)AC is the propagation method applied to all constraints.

Many consistency properties and corresponding propagation algorithms stronger than AC and GAC have been proposed in the literature. One of the most studied is singleton (G)AC which, as we will explain in the following section, has also been used to guide the selection process for a certain variable ordering heuristic. A variable xiis *singleton generalized arc consistent* (SGAC) iff for each value ai ∈ D(xi), after assigning ai to xi and applying GAC in the problem, there is no empty domain [14].

A *support check* (consistency check) is a test to find out if a tuple supports a given value. In the case of binary CSPs a support check simply verifies if two values support each other or not. The *revision* of a variable-constraint pair
(*c, x*i), with xi ∈ *vars*(c), verifies if all values in D(xi) have support on c. In the binary case the revision of an arc (xi,xj ) verifies if all values in D(xi) have supports in D(xj ). We say that a revision is *fruitful* if it deletes at least one value, while it is *redundant* if it achieves no pruning. A *DWO-revision* is one that causes a domain wipeout (DWO). That is, it removes the last remaining value(s) from a domain.

Complete search algorithms for CSPs are typically based on backtracking depth-first search where branching decisions (i.e. variable assignments) are interleaved with constraint propagation. The search algorithm used in the exper-