|
R56
Backtracking Algorithms for Constraint Satisfaction Problems
Rina Dechter (dechter@ics.uci.edu) & Daniel Frost (frost@ics.uci.edu)

Abstract
Over the past twenty five years many backtracking algorithms have been developed for constraint satisfaction problems. This survey describes the basic backtrack search within the search space framework and then presents a number of improvements developed in the past two decades, including look-back methods such as backjumping, constraint recording, backmarking, and look-ahead methods such as forward checking and dynamic variable ordering.

  [ps] [pdf]