ConstraintSatisfactionProblem

Constraint satisfaction problems (CSPs) are a framework for solving combinatorial problems. A CSP consists of a set of variables, each with a finite domain of possible values, and a set of constraints that specify allowable combinations of values for subsets of variables. The goal is to assign a value to every variable such that all constraints are satisfied.

Formally, a CSP is described by a triple (V, D, C). V = {v1, ..., vn} is a set of variables. D assigns to each variable vi a finite domain Di. C is a set of constraints restricting the values that subsets of variables can take. A solution is a complete assignment that satisfies every constraint.

Common examples include map coloring, where adjacent regions must have different colors; Sudoku, where each row, column, and region must contain the digits 1–9 without repetition; and various scheduling or resource allocation problems.

Solving CSPs typically involves search and inference. Backtracking search systematically explores assignments, while constraint propagation reduces domains by enforcing consistency; techniques include arc consistency (AC-3) and path consistency. Heuristics such as the minimum remaining values (MRV) and degree heuristic guide variable ordering, and the least-constraining value heuristic helps value choice. For large or hard instances, local search methods like min-conflicts can be effective.

The general problem is NP-complete, but many practical CSPs have structure (e.g., tree-like constraint graphs) that allows polynomial-time solutions. CSPs are foundational in artificial intelligence and operations research, underpinning scheduling, configuration, planning, and puzzle solving.