  Search is a key service within constraint programming systems, and it demands
the restoration of previously accessed states during the exploration of a
search tree. Restoration proceeds either bottom-up within the tree to roll back
previously performed operations using a trail, or top-down to redo them,
starting from a previously stored state and using suitable information stored
along the way. In this paper, we elucidate existing restoration techniques
using a pair of abstract methods and employ them to present a new technique
that we call recollection. The proposed technique stores the variables that
were affected by constraint propagation during fix points reasoning steps, and
it conducts neither operation roll-back nor recomputation, while consuming much
less memory than storing previous visited states. We implemented this idea as a
prototype within the Gecode solver. An empirical evaluation reveals that
constraint problems with expensive propagation and frequent failures can
benefit from recollection with respect to runtime at the expense of a marginal
increase in memory consumption, comparing with the most competitive variant of
recomputation.
