Unrestricted Backtracking Algorithms for Satisfiability

Contents

This paper proposes a general framework for implementing backtracking search strategies in Propositional Satisfiability (SAT) algorithms, that is referred to unrestricted backtracking. Different organizations of unrestricted backtracking yield well-known backtracking search strategies. Moreover, this general framework allows devising new backtracking strategies. Hence, we illustrate and compare different organizations of unrestricted backtracking. For example, we propose a stochastic systematic search algorithm for SAT, that randomizes both the variable selection and the backtracking steps of the algorithm. Finally, experimental results provide empirical evidence that different organizations of unrestricted backtracking can result in competitive approaches for solving hard real-world instances of SAT.