The Hazards of Fancy Backtracking

Constraint Satisfaction

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 12

Advances in Backtracking

There has been some recent interest in intelligent backtracking procedures that can return to the source of a difficulty without erasing the intermediate work. In this paper, we show that for some problems it can be counterproductive to do this, and in fact that such "inteIIigence" can cause an exponential increase in the size of the ultimate search space. We discuss the reason for this phenomenon, and we present one way to deal with it.