as with backtracking, or using forms of local search which may be incomplete.

When solving a CSP using backtracking search, a sequence of decisions must be made as to which variable to instantiate next. These decisions are referred to as the variable ordering decisions. It has been shown that for many problems the choice of variable ordering can have a dramatic effect on the performance of the backtracking algorithm with huge variances even on a single instance [20, 37].

A variable ordering can be either static, where the ordering is fixed and determined prior to search, or dynamic, where the ordering is determined as the search proceeds. Dynamic variable orderings are considerably more efficient and have thus received much attention in the literature. One common dynamic variable ordering strategy, known as "fail-first", is to select as the next variable the one likely to fail as quickly as possible.

Recent years have seen the emergence of numerous modern heuristics for choosing variables during CSP search. The so called conflict-driven heuristics exploit information about failures gathered throughout search and recorded in the form of constraint weights, while other heuristics measure the importance of variable assignments in reducing the search space. Most of them are quite successful and choosing the best general purpose heuristic is not easy. All these new heuristics have been tested over a narrow set of problems in their original papers and they have been compared mainly with older heuristics. Hence, there is no comprehensive view of the relative strengths and weaknesses of these heuristics.

This paper is an improvement to that published previously in [1]. A first aim of the present work is to experimentally evaluate the performance of the most recent and powerful heuristics over a wide range of benchmarks, in order to reveal their strengths and weaknesses. Results demonstrate that conflict-driven heuristics such as the well known *dom/wdeg* heuristic [8] are in general faster and more robust than other heuristics. Based on these results, as a second contribution, we have tried to improve the behavior of the *dom/wdeg* heuristic resulting in interesting additions to the family of conflict-driven heuristics.

We also investigate new ways to exploit failures in order to speed up constraint solving. To be precise, we investigate the interaction between conflictdriven variable ordering heuristics and revision list ordering heuristics and propose new efficient revision ordering heuristics. Constraint solvers that maintain a local consistency (e.g. Maintaining Arc Consistency, MAC-based solvers) employ a *revision list* of variables, constraints, or (hyper)arcs (depending on the implementation), to propagate the effects of variable assignments. It has been shown that the order in which the elements of the list are selected for revision affects the overall cost of the search. Hence, a number of revision ordering heuristics have been proposed and evaluated [38, 7, 34]. In general, variable ordering and revision ordering heuristics have different tasks to perform when used by a search algorithm such as MAC. Prior to the emergence of conflictdriven variable ordering heuristics it was not possible to achieve an interaction with each other, i.e. the order in which the revision list was organized during propagation could not affect the decision of which variable to select next
(and vice versa). The contribution of revision ordering heuristics to the solver's