## 2.6 Distribution and Search Trees

To solve a finite domain problem , we can always choose a constraint and solve both and . We say that we have distributed with .

We can apply the idea to spaces. Suppose is a stable space that is neither failed nor solved. Then we can choose a constraint and distribute with . Distribution yields two spaces, one obtained by adding a propagator for , and one obtained by adding a propagator for .

The combination of constraint propagation and distribution yields a complete solution method for finite domain problems. Given a problem, we set up a space whose store contains the basic constraints and whose propagators impose the nonbasic constraints of the problem. Then we run the propagators until the space becomes stable. If the space is failed or solved, we are done. Otherwise, we choose a not yet determined variable and an integer such that is consistent with the constraint store and distribute the space with the constraint . Since we can tell both and to the constraint store (the store already knows a domain for ), chances are that constraint propagation can restart in both spaces.

By proceeding this way we obtain a search tree as shown in Figure 2.1. Each node of the tree corresponds to a space. Each leaf of the tree corresponds to a space that is either solved or failed. The search tree is always finite since there are only finitely many variables all a priori constrained to finite domains.

Figure 2.1: A search tree. Diamonds represent solved spaces and boxes represent failed spaces.

Christian Schulte and Gert Smolka
Version 1.4.0 (20080702)