A New Look at the Easy-Hard-Easy Pattern of Combinatorial Search
  Difficulty
  The easy-hard-easy pattern in the difficulty of combinatorial search problems
as constraints are added has been explained as due to a competition between the
decrease in number of solutions and increased pruning. We test the generality
of this explanation by examining one of its predictions: if the number of
solutions is held fixed by the choice of problems, then increased pruning
should lead to a monotonic decrease in search cost. Instead, we find the
easy-hard-easy pattern in median search cost even when the number of solutions
is held constant, for some search methods. This generalizes previous
observations of this pattern and shows that the existing theory does not
explain the full range of the peak in search cost. In these cases the pattern
appears to be due to changes in the size of the minimal unsolvable subproblems,
rather than changing numbers of solutions.
