... node1
In the paper by Bacchus et al. bcvbw02 the cost of applying a variable ordering heuristic at each node is also taken into account. When we theoretically compare search algorithms in this paper we assume that they use the same variable ordering, so we do not take this cost into account. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...#tex2html_wrap_inline1728#2
We assume, without loss of generality, that the algorithm looks for supports by checking the tuples in lexicographic order. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... it3
Note that dual variables that are already in the stack are never added to it. In this sense, the stack is implemented as a set. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... variable4
``One pass'' means that each constraint is processed only once. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... AC-20015
Note that we can construct similar examples for any generic AC algorithm. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... classes6
Puzzles 6$\times$6-10$\times$10 correspond to square grids with no blank squares. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... encoding7
This was verified by looking at the node visits of the two algorithms. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... connected8
Experiments showed that these are the minimum additions that need to be made in order to get hard problems without altering the structure of the problems too much. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... MGAC9
To create the instances we varied the type of the constraints and the values of parameters $s$ and $s'$ until non-trivial problems were generated. We consider as trivial problems that are arc inconsistent or solvable with no backtracking. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... encoding10
Although the title of Smith's paper smith02 refers to the DE, the model of the ``still-life'' problem used is based on the double encoding. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.