To enable consistency methods to find all of the solutions, we need to incorporate search. While the search methods of Section 4.2 can be adapted to allow for simplification of the domains, we can do better by domain splitting, a form of case analysis that interleaves search and arc consistency. 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 of the 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=\mathrm{\hspace{0.17em}1}$, $A=\mathrm{\hspace{0.17em}2}$, $A=\mathrm{\hspace{0.17em}3}$, and $A=\mathrm{\hspace{0.17em}4}$.

• •

  Always split the domain into two disjoint non-empty subsets. For example, split $A$ into the two cases $A\in \{1,2\}$ and $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.2. It can be more efficient to interleave 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.

Arc consistency does not need to start from scratch after domain splitting. If the variable $X$ has its domain split, $to\mathrm{\_}do$ can start with just the arcs that are possibly no longer arc consistent as a result of the split. These are all the arcs of the form , where $X$ appears in $r$ and $Y$ is not $X$.

Figure 4.6 shows how to solve a CSP with arc consistency and domain splitting. $Con\mathrm{\_}Solve(Vs,dom,Cs,to\mathrm{\_}do)$ returns a solution to constraint satisfaction problem $Vs,dom,Cs$ if there is (at least) one, or $false$ otherwise. Initially, $dom$ contains the domain for each variable, and $to\mathrm{\_}do$ is . The “or” in line 13 is assumed to return the value of its first argument if it is not false, and otherwise returns the value of the second argument. $GAC$ must not change $to\mathrm{\_}do$, otherwise the second $td$ might have the wrong value.

It is possible to use essentially the same algorithm to find all solutions: line 4 should return the empty set, line 6 should return the set containing one element, and line 13 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 can make domain splitting much more efficient when counting the number of 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 product of the solutions to each component. For example, if one component has 100 solutions and the other component has 20 solutions, there are 2000 solutions. Treating them independently is more efficient than finding each of the 2000 solutions separately.