Domain Reduction

Domain Reduction is an important technique in constraint solving and refers to the process of removing values from variable domains that cannot be part of any consistent solution.

For example, in the Sudoku problem, initially each cell has domain {1..9}. But we can prune the domains by analyzing the constraints:

• If a cell in row 1 already has value 3, remove 3 from the domains of other cells in row 1.

• If a cell in column 5 has value 7, remove 7 from the domains of other cells in column 5.

• If the top-left 3x3 box has cells with values {2,5,8}, remove 2, 5, and 8 from other cells in that box.

Each time we assign a value or infer a constraint, we propagate the effects to prune inconsistent values from neighboring domains. This propagation process iteratively reduces the search space by filtering domains.

Some benefits of domain reduction:

• Removes infeasible values early before attempting assignments
• Makes constraints propagation very efficient
• Can detect inconsistencies early if domain becomes empty
• Reduces search space for backtracking methods

So in summary, domain reduction takes advantage of constraints to aggressively prune inconsistent values from variable domains during search. This makes the remaining search more efficient.