Backtracking and Probing

Paul Walton Purdom, Jr., Indiana University

G. Neil Haven, Indiana University

Partial support provided by NSF Grant CCR 92-03942.

Abstract: We analyze two algorithms for solving constraint satisfaction problems. One of these algorithms, Probe Order Backtracking, has an average running time much faster than any previously analyzed algorithm for problems where solutions are common. Probe Order Backtracking uses a probing assignment (a preselected test assignment to unset variables) to help guide the search for a solution to a constraint satisfaction problem. If the problem is not satisfied when the unset variables are temporarily set to the probing assignment, the algorithm selects one of the relations that the probing assignment fails to satisfy and selects an unset variable from that relation. Then at each backtracking step it generates subproblems by setting the selected variable each possible way. It simplifies each subproblem, and tries the same technique on them. For random problems with v variables, t clauses, and probability p that a literal appears in a clause, the average time for Probe Order Backtracking is no more than vn when p >= (ln t)=v plus lower order terms. The best previous result was p >= p(ln t)=v. When the algorithm is combined with an algorithm of Franco that makes selective use of resolution, the average time for solving random problems is polynomial for all values of p when t <= O(n1=3(v= ln v)2=3). The best previous result was t <= O(n1=3(v= ln v)1=6). Probe Order Backtracking also runs in polynomial average time when p <= 1=v, compared with the best previous result of p <= 1=(2v). With Probe Order Backtracking the range of p that leads to more than polynomial time is much smaller than that for previously analyzed algorithms.

1 Backtracking

The constraint satisfaction problem is to determine whether a set of constraints over discrete variables can be satisfied. Each constraint must have a form that is easy to evaluate, so any difficulty in solving such a problem comes from the interaction between the constraints and the need to find a setting for the variables that simultaneously satisfies all of the constraints.

Constraint satisfaction problems are extremely common. Indeed, the proof that a problem is NP- complete implies an efficient way to transform the problem into a constraint satisfaction problem. Most NP- complete problems are initially stated as constraint satisfaction problems. A few special forms of constraint satisfaction problems have known algorithms that solve problem instances in polynomial worst-case time. However, for the general constraint satisfaction problem no known algorithm is fast for the worst case.

When no polynomial-time algorithm is known for a particular form of constraint satisfaction problem, it is common practice to solve problem instances with a search algorithm. The basic idea of searching is to choose a variable and generate subproblems by assigning each possible value to the variable. In each subproblem the relations are simplified by plugging in the value of the selected variable. This step of generating simplified subproblems is called splitting. If any subproblem has a solution, then the original problem has a solution. Otherwise, the original problem has no solution. Subproblems that are simple enough (such as those with no unset variables) are solved directly. More complex subproblems are solved by applying the technique recursively.

If a problem contains the always false relation, then the problem has no solution. Simple Backtracking improves over plain search by immediately reporting no solution for such problems. Backtracking often saves a huge amount of time.

2 Probing

This paper considers two algorithms that are improvements over Simple Backtracking. Both algorithms use the idea of probing : if a fixed assignment to the unset variables solves the problem, no additional investigation is needed. Our algorithms probe by setting each unset variable to false and testing to see whether all relations simplify to true. The two probing algorithms are simple enough that it is possible to analyze their average running time.