We study an algorithm for the SAT problem which is based on the Davis and Putnam procedure. The main idea is to increase the
application of the unit clause rule during the search. When there is no unit clause in the set of clauses, our method tries
to produce one occuring in the current subset of binary clauses. A literal deduction algorithm is implemented and applied
at each branching node of the search tree. This method AVAL is a combination of the Davis and Putnam principle and of the
mono-literal deduction procedure. Its efficiency comes from the average complexity of the literal deduction procedure which
is linear in the number of variables. The method is called “AVAL” (avalanch) because of its behaviour on hard random SAT problems.
When solving these instances, an avalanche of mono-literals is deduced after the first success of literal production and from
that point, the search effort is reduced to unit propagations, thus completing the remaining part of enumeration in polynomial
time.
Keywords Satisfiability - deduction - enumeration