Constraint Satisfaction Problems (CSP)
CSPs represent a state with a set of variable/value pairs and
represent the conditions for a solution by a set of constraints
on the variables. Many important real-world problems can
be described as CSPs.
Three basic components
• Variables: The things that need to be determined are variables.
Boolean, integer, and categorical variables
• Domains: The range of potential values that a variable can have is
represented by domains. Depending on the issue, a domain may be finite or
limitless. For instance, in Sudoku, the set of numbers from 1 to 9 can serve as
the domain of a variable representing a problem cell.
• Constraints: The guidelines that control how variables relate to one another
are known as constraints .
A sudoku problem, the restrictions might be that each row, column,
and 3×3 box can only have one instance of each number from 1 to 9.
Constraint Satisfaction Problems (CSP) representation:
• The finite set of variables V1, V2, V3 ……………..Vn.
• Non-empty domain for every single variable D1, D2, D3 …………..Dn.
• The finite set of constraints C1, C2 …….…, Cm.
– where each constraint Ci restricts the possible values for variables,
• e.g., V1 ≠ V2
– Each constraint Ci is a pair <scope, relation>
• Example: <(V1, V2), V1 not equal to V2>
• X1 and X2 both have the domain {A, B}
Constraints:
(X1,X2),[(A,B),(B,A)] or
(X1,X2), X1 ≠ X2
– Scope = set of variables that participate in constraint.
– Relation = list of valid variable value combinations.
• There might be a clear list of permitted combinations. Perhaps a relation that is abstract and
that allows for membership testing and listing.
Example of csp
• Sudoku
• Cryptarithmetic
• Crosswords
• n-Queen
• Map coloring
Real-world CSP:
• Scheduling: How to efficiently and effectively schedule resources like personnel,
equipment, and facilities. The constraints in this domain specify the availability and
capacity of each resource, whereas the variables indicate the time slots or
resources.
• Vehicle routing: The issue of minimizing travel time or distance by optimizing a
fleet of vehicles’ routes. In this domain, the constraints specify each vehicle’s
capacity, delivery locations, and time windows, while the variables indicate the
routes taken by the vehicles.
• Assignment: How to optimally assign assignments or jobs to humans or machines.
In this field, the variables stand in for the tasks, while the constraints specify the
knowledge, capacity, and workload of each person or machine.
• Sudoku: Sudoku can be modeled as a CSP problem, where the variables stand in
for the grid’s cells and the constraints specify the game’s rules, such as prohibiting
the repetition of the same number in a row, column, or area.
• Constraint-based image segmentation: The segmentation of an image into areas
with various qualities (such as color, texture, or shape) can be treated as a CSP
issue in computer vision, where the variables represent the regions and the
constraints specify how similar or unlike neighboring regions are to one another.
Advantage of formulating a problem as a CSP:
• CSPs yield a natural representation for a wide variety of problems;
• CSP solvers can be faster than state-space searchers because the CSP
solver can quickly eliminate large swatches of the search space;
• With CSP, once we find out that a partial assignment is not a solution, we
can immediately discard further refinements of the partial assignment.
• We can see why a assignment is not a solution—which variables violate a
constraint.