implement the search heuristic and will be discussed in more detail in Sec. 4.2.

As the branches correspond to a disjunction of P
′**, the recursive counts** add up to the total number of solutions.

![0_image_0.png](0_image_0.png)

The only addition that is necessary to turn DFS into an And/Or search is line 5: If the problem can be decomposed into P
′
1 and P
′
2
(we simplify by assuming only binary decomposition), these partial problems in conjunction are equivalent to P
′**. Hence, we** multiply **the results of the recursive calls.**
In contrast to investigating decomposability only on the initial CSP for a static variable selection, Algorithm 1 follows a dynamic approach: the **check for** decomposability is interleaved with propagation and normal search. **As search** progresses, more and more variables are assigned to values, and more and more constraints are detected to be entailed. We shall see that this greatly increases the potential for decomposition in Sec. 4. Furthermore, decomposition is completely independent of the implementation of LeftChoice and RightChoice**, so any**
search heuristic can be used. Short-circuit**. As a straightforward optimization, we can employ short-circuit**
reasoning in line 5. If DDS(P
′
1
) returns no solutions, we do not have to compute DDS(P
′2) at all. Note the potential pitfall here: There are situations where DFS
detects failure easily, but DDS has to search a huge partial problem P
′
1 **before**
detecting failure in P
′
2
. We come back to this in Sec. 4.2.

Enumerating solutions**. Extending DDS to enumeration of solutions is straightforward: We just have to return an empty list in case of failure (line 3), a singleton list with a solution when we find one (line 4), and interpret addition as list**
concatenation and multiplication as combination of partial solutions. **Instead of** enumeration, we can also build up a tree-shaped compact representation of the solution space (as in Fig. 2 and later in Fig. 9c).

In the rest of this section, we show how to compute the Decompose **function**
efficiently.

## 3.3 Computing The Decomposition

We will now define formally when a CSP can be decomposed, and give a sufficient algorithmic characterization that leads to an efficient implementation.