Generalised Backjumping

Reference: P. Clark and R. Holte. Generalised Backjumping. Tech. Report TR-92-20, Dept CS, Univ. Ottawa, May 1992.

Abstract: Gaschnig's backjumping algorithm has become one of the standard methods for constraint satisfaction, performing dependency-directed backtracking (`backjumping') from nodes which cannot be further expanded during tree search. In this paper, we show how this algorithm can be extended to also permit backjumping from nodes which were expanded, but whose subtrees eventually failed. We experimentally compare Gaschnig's backjumping and our extended algorithm (`generalised backjumping') on two standard constraint satisfaction problems (8-queens and zebras). We show that generalised backjumping can substantially reduce the search performed by the original algorithm, thus demonstrating a significant development of this established search technique.