Backtracking and probing
Paul Walton Purdom, G. Neil Haven · DIMACS series in discrete mathematics and theoretical computer science · 1997
: 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 m...