Constraint satisfaction problem

A constraint satisfaction problem consists of variables, possible values for each variable, and constraints that specify which combinations of values are allowed. A solution assigns a value to every variable without violating any constraint.

Constraint propagation: A family of methods that removes domain values incompatible with constraints before or during search. It prunes impossible values before branching on assignments.
Variable (mathematics): A symbol or entity whose value is allowed to vary within a mathematical expression or problem. CSP variables are the unknowns that an assignment must fill.
Sudoku: A number-placement puzzle in which each row, column, and marked region must contain every digit once. Its cells are variables, digits are domains, and placement rules are constraints.
SAT solving: The task of deciding whether a Boolean formula has a satisfying truth assignment. SAT uses Boolean variables and clauses, while CSPs allow general domains and constraints.
Backtracking: A search method that builds a partial solution and reverses choices when they cannot lead to a complete one. It explores assignments incrementally and retreats when a constraint is violated.
Domain (mathematics): A set of permitted input or value choices associated with a mathematical object or problem. Each CSP variable draws its candidate values from a domain.
Graph coloring: The problem of assigning colors to graph vertices so adjacent vertices receive different colors. It models map coloring and frequency assignment as pairwise constraints.
Linear programming: An optimization method for finding extrema of a linear objective under linear constraints. Its algebraic restrictions differ from the arbitrary discrete constraints common in CSPs.
Arc consistency: A property of a binary constraint network in which every value has compatible support in each neighboring variable's domain. It formalizes a common level of constraint propagation.
Constraint: A condition that restricts the permitted values or combinations of values in a problem. Constraints define which complete assignments count as solutions.

Linked from 21 pages