Algorithm 3 variable-oriented AC3 1: Q ← {xi| xi ∈ X}
2: ∀ cij ∈ C, ∀xi ∈ vars(cij ), ctr (cij , xi) ← 1 3: while Q 6= ∅ do 4: get xi from Q
5: for each cij | xi ∈ *vars*(cij ) do 6: if ctr (cij , xi) = 0 then continue 7: for each xj ∈ *vars*(cij ) do 8: if NEEDS-NOT-BE-REVISED(cij , xj ) then continue 9: nbRemovals ← REVISE(cij , xj )
10: if *nbRemovals* > 0 then 11: if dom(xj ) = ∅ then return false 12: Q ← Q ∪ {xj}
13: for each cjk | cjk 6= cij ∧ xj ∈ *vars*(cjk) do 14: ctr (cjk, xj ) ← ctr (cjk, xj ) + *nbRemovals* 15: end for 16: end if 17: end for 18: for each xj ∈ vars(cij ) do ctr (cij , xj ) ← 0 19: end for 20: end while 21: return true Algorithm 4 needs-not-be-revised(cij , xi)
1: return (ctr (cij , xi) > 0 and @xj ∈ vars(cij ) | xj 6= xi ∧ ctr (cij , xj ) > 0)
5.2. Overview of revision ordering heuristics Revision ordering heuristics is a topic that has received considerable attention in the literature. The first systematic study on this topic was carried out by Wallace and Freuder, who proposed a number of different heuristics that can be used with the arc-oriented variant of AC-3 [38]. These heuristics, which are defined for binary constraints, are based on three major features of CSPs: (i)
the number of acceptable pairs in each constraint (the constraint size or satisfiability), (ii) the number of values in each domain and (iii) the number of binary constraints that each variable participates in (the degree of the variable). Based on these features, they proposed three revision ordering heuristics: (i) ordering the list of arcs by increasing relative satisfiability (*sat up*), (ii) ordering by increasing size of the domain of the variables (*dom j up*) and (iii) ordering by descending degree of each variable (*deg down*).

The heuristic *sat up* counts the number of acceptable pairs of values in each constraint (i.e the number of tuples in the Cartesian product built from the current domains of the variables involved in the constraint) and puts constraints in the list in ascending order of this count. Although this heuristic reduces the list additions and constraint checks, it does not speed up the search process.