Another method for simplifying the network is domain splitting or case analysis. The idea is to split a problem into a number of disjoint cases and solve each case separately. The set of all solutions to the initial problem is the union of the solutions to each case.

In the simplest case, suppose there is a binary variable $X$ with domain $\{t,f\}$. All of the solutions either have $X=t$ or $X=f$. One way to find all of the solutions is to set $X=t$, find all of the solutions with this assignment, and then assign $X=f$ and find all solutions with this assignment. Assigning a value to a variable gives a smaller reduced problem to solve. If we only want to find one solution, we can look for the solutions with $X=t$, and if we do not find any, we can look for the solutions with $X=f$.

If the domain of a variable has more than two elements, for example if the domain of $A$ is $\{1,2,3,4\}$, there are a number of ways to split it

• •

  Split the domain into a case for each value. For example, split $A$ into the four cases $A=1$, $A=2$, $A=3$, and $A=4$.

• •

  Always split the domain into two disjoint non-empty subsets. For example, split $A$ into the two cases: $A\in \{1,2\}$ and the case $A\in \{3,4\}$.

The first approach makes more progress with one split, but the second may allow for more pruning with fewer steps. For example, if the same values for $B$ can be pruned whether $A$ is 1 or 2, the second case allows this fact to be discovered once and not have to be rediscovered for each element of $A$. This saving depends on how the domains are split.

Recursively solving the cases using domain splitting, recognizing when there is no solution based on the assignments, is equivalent to the search algorithm of Section 4.3. We can be more efficient by interleaving arc consistency with the search.

One effective way to solve a CSP is to use arc consistency to simplify the network before each step of domain splitting. That is, to solve a problem,

• •

  simplify the problem using arc consistency, and

• •

  if the problem is not solved, select a variable whose domain has more than one element, split it, and recursively solve each case.

One thing to notice about this algorithm is that it does not require arc consistency to start from scratch after domain splitting. If the variable $X$ has its domain split, to_do can start with just the arcs that are possibly no longer arc consistent as a result of the split. These are the arcs of the form , where $X$ appears in $r$ and $Y$ is not $X$.

Figure 4.5 shows how to solve a CSP with arc consistency and domain splitting. $\text{CSP\_Solver}(\text{CSP})$ returns a solution to constraint satisfaction problem CSP if there is (at least) one, or false otherwise. Note that the “or” in line 16 is assumed to return the value of its first argument it is not false, and otherwise returns the value of the second argument.

It is possible to use essentially the same algorithm to find all solutions: line 7 should return the empty set, line 9 should return the set containing one element, and line 16 should return the union of the answers from each case.

Domain splitting forms a search space from which any of the methods of Chapter 3 can be used. However, as it is only the solution and not the path that is of interest, and because the search space is finite, depth-first search is often used for these problems.

One other enhancement make domain splitting much more efficient when counting the number of solutions or finding all solutions. If assigning values to the variables disconnects the graph, each disconnected component can be solved separately. The solution to the complete problem is the cross product of the solutions to each component. This can save much computation when one is counting the number of solutions. For example, if one component has 100 solutions and the other component has 20 solutions, there are 2000 solutions. This is a more efficient way to count than finding each of the 2000 solutions separately.