Backjump-based backtracking for constraint satisfaction problems

The performance of backtracking algorithms for solving nite-domain constraint sat-isfaction problems can be improved substantially by look-back and look-ahead meth-ods. Look-back techniques extract information by analyzing failing search paths that are terminated by dead-ends. Look-ahead techniques use constraint propagation al-gorithms to avoid such dead-ends altogether. This survey describes a number of look-back variants including backjumping and constraint recording which recognize and avoid some unnecessary explorations of the search space. The last portion of the paper gives an overview of look-ahead methods such as forward checking and dynamic variable ordering, and discusses their combination with backjumping