Algorithm 5 constraint-oriented AC3 1: Q ← {cij | cij ∈ C}
2: ∀ cij ∈ C, ∀xi ∈ vars(cij ), ctr (cij , xi) ← 1 3: while Q 6= ∅ do 4: get cij from Q
5: for each xj ∈ *vars*(cij ) do 6: if NEEDS-NOT-BE-REVISED(cij , xj ) then continue 7: nbRemovals ← REVISE(cij , xj )
8: if *nbRemovals* > 0 then 9: if dom(xj ) = ∅ then return false 10: for each cjk | cjk 6= cij ∧ xj ∈ *vars*(cjk) do 11: Q ← Q ∪ {xj}
12: ctr (cjk, xj ) ← ctr (cjk, xj ) + *nbRemovals* 13: end for 14: end if 15: end for 16: for each xj ∈ vars(cij ) do ctr (cij , xj ) ← 0 17: end while 18: return true When a value is deleted from the domain of a variable, the counter that keeps the number of acceptable arcs has to be updated. This process is usually time consuming because the algorithm has to identify the constraints in which the specific variable participates and to recalculate the counters with acceptable value pairs. Also an additional overhead is needed to reorder the list.

The heuristic *dom j up* counts the number of remaining values in each variable's current domain during search. Variables are inserted in the list by increasing size of their domains. This heuristic reduces significantly list additions and constraint checks and is the most efficient heuristic among those proposed in [38].

The *deg down* heuristic counts the current degree of each variable. The initial *degree* of a variable xiis the number of variables that share a constraint with xi. During search, the *current degree* of xiis the number of unassigned variables that share a constraint with xi. The *deg down* heuristic sorts variables in the list by decreasing size of their current degree. As noticed in [38] and confirmed in [7], the (*deg down*) heuristic does not offer any improvement.

Gent et al. [19] proposed another heuristic called kac. This heuristic is based on the number of acceptable pairs of values in each constraint and tries to minimize the constrainedness of the resulting subproblem. Experiments have shown that kac is time expensive but it performs less constraint checks when compared to *sat up* and *dom j up*.

Boussemart et al. [7] performed an empirical investigation of the heuristics of
[38] with respect to the different variants (arc, variable and constraint) of AC-3. In addition, they introduced some new heuristics. Concerning the arc-oriented AC-3 variant, they have examined the *dom j up* as a stand alone heuristic