Modified backjumping algorithms for solving constraint satisfaction problems

The backtracking algorithm is a prominent search technique in AI, particula rly due to its use in Constraint Satisfaction Problems (CSPs), Truth Mainte nance Systems (TMS), and PROLOG. In the context of CSPs, Dechter(5) and Gas hnig(10) proposed two variants of the backtracking algorithm known as backj umping algorithms. One is graph-based and the other is failure-based backju mping algorithm. These algorithms attempt to backjump to the source of fail ure in case of a dead-end situation. This improves the backtracking perform ance. However, these algorithms are not consistent in the selection of the variable to backjump. In this paper, the modifications of both types of backjumping algorithms ar e proposed. These algorithms adopt a technique to select the variable to ba ckjump in a consistent manner. This further increases the search efficiency in them. The merits of these modified algorithms are investigated theoreti cally. Experimental results on the zebra problem and random problems show t hat the modified algorithms give better results on most occasions.