Constraint Satisfaction Problems in Artificial Intelligence

Constraint Satisfaction Problems (CSP) in AI are a fantastic way to handle hard problems that involve making choices and finding the best solution. In a standard search problem, the state is like a "black box." In a standard search problem, the state is like a "black box." In a CSP, the state is made up of a number of variables, each of which can have a range of values, and a set of rules that tell you which combinations of those values are okay.

CSPs are great for planning, scheduling, and allocating resources because they let AI systems utilise general heuristics instead of ones that only work in some cases. This webinar will teach you everything you need to know about AI problems that need certain conditions to be met. You can either watch an example or learn more about constraint satisfaction problems in AI map colouring.

Core Components of a Constraint Satisfaction problems in Artificial Intelligence 

1.1 Variables ($X$)

• Notation: $X = \{X_1, X_2, \dots, X_n\}$
• Example: In a scheduling problem, variables could be the start times of different tasks.

1.2 Domains ($D$)

• Notation: $D = \{D_1, D_2, \dots, D_n\}$
• Types:
  • Finite Domains:  A set of values that doesn't change, like $\{Red, Green, Blue\}$ or $\{1, 2, 3, \dots, 9\}$.
  • Infinite Domains: Continuous values or endless integers, such any real number or the times a work starts on a timeline.

1.3 Constraints ($C$)

• Notation: $C = \{C_1, C_2, \dots, C_m\}$
• Structure: Each constraint is a pair of the form $\langle \text{scope}, \text{relation} \rangle$. The scope is the set of variables that are involved, and the relation is the set of compatible tuples that show the possible combinations of values.

Types of Constraints Satisfaction problems in Artificial Intelligence 

• Unary Constraints: Involve a single variable.
  • Example: "Region A cannot be Red" ($SA \neq Green$).
• Binary Constraints: They have two variables. These are common because you can see them in a Constraint Graph.
  • Example: "Region A and Region B must have different colors" ($WA \neq NT$).
• Higher-Order Constraints: Involve three or more variables.
  • Example: For example, in Cryptarithmetic problems, the "carry" digits are the numbers that are in more than one column equation.

• For example, the Alldiff requirement makes sure that all the variables in a set have different values. This is popular in Sudoku.

Example of constraint satisfaction problems in AI: Map Coloring

Problem Description

CSP Formulation

• Variables ($X$): $\{WA, NT, Q, NSW, V, SA, T\}$ (Western Australia, Northern Territory, Queensland, etc.).
• Domains ($D$): For each variable, $D_i = \{Red, Green, Blue\}$.
• Constraints ($C$): Adjacent regions must have different colors.
  • $(WA \neq NT), (WA \neq SA), (NT \neq SA), (NT \neq Q), (SA \neq Q), (SA \neq NSW), (SA \neq V), (NSW \neq V), (NSW \neq Q)$.

Constraint Graph

• Nodes represent variables.
• Edges (Arcs) represent binary constraints between variables.
• Note: Tasmania ($T$) is an independent subproblem as it shares no borders.

• Constraint Propagation in AI
• IBM vs AI: Is Claude the Beginning of the End for Legacy Software Giants?
• What Is Local Search Algorithm in Artificial Intelligence
• Semantic Networks in Artificial Intelligence
• Artificial Intelligence in Robotics 2026
• What is the Role of Planning in Artificial Intelligence?
• Top 7 Generative AI Courses
• Best AI Courses For Beginners

Algorithms and Heuristics for Solving Constraint Satisfaction probelms

4.1 Backtracking Search

4.2 Heuristics to Improve Search

• Minimum Remaining Values (MRV): Choose the variable that has the fewest "legal" values left. This rule is often called the "Most Constrained Variable" rule.
• Degree Heuristic: Pick the variable that has the most restrictions with other variables that haven't been assigned yet. This is important for breaking ties in MRV.
• Least Constraining Value (LCV): For a given variable, pick the value that limits the fewest options for nearby variables.

4.3 Inference and Constraint Propagation

• Forward Checking: When a variable is assigned, delete conflicting values from the domains of its immediate neighbors.
• Arc Consistency (AC-3): A more rigorous check. An arc $X \to Y$ is consistent if for every value in $X$, there is at least one compatible value in $Y$. The AC-3 algorithm propagates these changes throughout the graph.

Real-World Applications of constraint satisfaction problems in artificial intelligence

1. Scheduling: Setting up the schedules for teachers, aircraft crews, or workers in factories.
2. Sudoku: Sudoku is a $9 \times 9$ grid where every row, column, and $3 \times 3$ block must have different numbers.
3. Cryptarithmetic: Cryptarithmetic is when letters stand for numbers in puzzles like "SEND + MORE = MONEY."
4. Resource Allocation: Following strict guidelines to split up limited resources like workers, power, or bandwidth.
5. N-Queens Problem: The N-Queens Problem is to put N queens on a N x N board so that no two queens can attack each other.

Comparison of Hard and Soft Constraints satisfaction problems in artificial intelligence 

• Hard Constraints: Rules that must be obeyed for a solution to work.
• Soft Constraints (Preferences): Rules that you don't have to follow, but if you do, there is a cost or consequence. These change a CSP into a Constrained Optimisation Problem, where the goal is to lower the total cost.