Consider the constraint network in Figure 4.16 (page 175). The form of the constraints are not given, but assume the network is arc consistent and there are multiple values for each variable. Suppose one of the search algorithms has split on variable X, so X is assigned the value a.

(a) Suppose the aim is to count the number of solutions. Bao suggested that the subproblem with X = a can be divided into two that can be solved separately.

How can the solutions to each half be combined?

(b) Suppose the constraints are soft constraints (with costs for each assignment).

Manpreet suggested that the problem with X = a can be divided into two subproblems that can be solved separately, with the solution combined. What are the two independent subproblems? How can the optimal solution (the cost and the total assignment) be computed from a solution to each subproblem?

(c) How can the partitioning of constraints into non-empty sets such that the constraints in each set do not share a non-assigned variable (the sets that can be solved independently) be implemented?