2.6 Distribution and Search Trees

To solve a finite domain problem P, we can always choose a constraint C and solve both P\cup\{C\} and P\cup\{\neg C\}. We say that we have distributed P with C.

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

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 x and an integer n such that x=n is consistent with the constraint store and distribute the space with the constraint x=n. Since we can tell both x=n and x\neq n to the constraint store (the store already knows a domain for x), 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)