Domain splitting

Domain splitting is a search technique used in constraint satisfaction solvers when propagation alone is insufficient to find a solution. Instead of assigning a single value to a variable, the solver splits a variable's domain into two or more subsets and explores each subset as a separate branch of the search tree. The most common form is binary splitting: a domain {a, b, c, d} is divided into {a, b} and {c, d}, and the solver attempts to solve the problem under each restriction.

Domain splitting is conceptually distinct from value assignment: it is a meta-search strategy that operates on the structure of the search space rather than on individual values. The choice of how to split — which variable, which partition — is a critical heuristic. Domain size splitting partitions the domain in half by size. Value-based splitting partitions according to some semantic criterion (e.g., small vs. large values). Constraint-based splitting partitions the domain according to which constraints would be most satisfied or most violated by each subset.

The power of domain splitting is that it can expose structure that propagation misses. A constraint network may be arc-consistent but still unsolvable; domain splitting forces the solver to explore the structural topology of the constraint space. It is the bridge between local consistency and global search: propagation narrows the domains, and splitting partitions what remains.

Domain splitting also has a systems-level interpretation. It is a form of problem decomposition — the computational equivalent of divide-and-conquer. In distributed constraint satisfaction, domain splitting is the mechanism by which subproblems are allocated to different agents or processors. The efficiency of the distributed solver depends on how well the splitting minimizes inter-processor constraint violations.