Valiant [24] as the class of counting problems that can be computed in **nondeterministic polynomial time. Notwithstanding the complexity, there is demand for**
solution counting in real applications. For instance, in bioinformatics **counting** optimal protein structures is of high importance for the study of protein energy landscapes, kinetics, and protein evolution [20, 25] and can be done **using CP [2].**
Already folklore, standard solving methods for CSPs like Depth-First Search
(DFS) leave room for saving redundant work, in particular when counting all solutions [10]. Recent work by Dechter et al. [8, 15] introduced And/Or search for solution counting and optimization, which makes use of repeated and**-decomposition during the search following a pseudo-tree. Their work thoroughly studies**
and develops a rich theory of And/Or trees.

While not in the context of general constraint propagation, similar ideas were discussed before for SAT-solving [3, 5, 14]. The SAT approaches also introduce the idea of analyzing the induced dependency structure dynamically **during the** search. This avoids redundancy that occurs due to the emergence of independent connected components in the dependency graph during the search. Motivation and contribution**. The motivation for this paper is to tackle the** same kind of redundancy for solving very hard real world problems, **such as the**
counting of protein structures, that require a full-fledged constraint programming system. This requests for a method which is tailored for integration into modern CP systems and directly supports features such as global **constraints and** dynamic search heuristics. To make use of the statically unpredictable effects of constraint propagation and entailment, the presented method avoids redundant search dynamically.

Our main contribution is to present how to integrate And/Or tree search into a state-of-the-art, propagation-based constraint solver. This is exemplified by extending the Gecode system [11]. We describe decomposition during search **(DDS)**
on different levels of abstraction, down to concrete implementation **details.**
In detail, we stress the impact that constraint propagation has on **decomposability of the constraint graph, and how DDS interacts (and works seamlessly**
together) with propagators for global constraints, the workhorses of modern propagation-based solvers. We show that global constraint decomposition is the key to enable the application of DDS, and discuss techniques that enable global constraint decomposition. The practical value of DDS in the presence of global constraints is shown empirically, using a well integrated and competitive implementation for the Gecode library.

Overview**. The paper starts with a presentation of the notations and concepts** that are used throughout the later sections. In Sec. 3, we briefly **recapitulate** And/Or search, and then present, on a high level of abstraction, decomposition during search **(DDS), our integration of And/Or search into a propagation-based** constraint solver. Sec. 4 deals with the interaction of DDS with propagation and search heuristics. Section 5 discusses how global constraints interact with DDS,
focusing on decomposition strategies for some important representatives.

On a lower level of abstraction, Sec. 6 sketches the concrete implementation of DDS using the Gecode C++ **constraint programming library. With the help**