Recently, two new backtracking algorithms, dynamic backtracking ( DB ) and partial order dynamic backtracking ( PDB ) have been presented. These algorithms have the property to be additive on disjoint subproblems and yet use only polynomial space. Unlike DB , PDB only imposes a partial search order and therefore appears to have more freedom than DB to explore the search space. However, both algorithms are not directly comparable in terms of exibility. In this paper we present new backtracking algorithms that are obtained by relaxing the ordering conditions of PDB . This gives them additional exibility while still being additive on disjoint subproblems. In particular, we show that our algorithms generalize both DB and PDB.