Introduction to Constraint Satisfaction Problems (CSPs)

Hello! Welcome to your third lesson in the "Artificial Intelligence: Search and Reasoning" module.

In our previous lessons, we focused on state-space search problems, where the goal was to find an optimal path from a starting state to a goal state. You learned how to formulate these problems and how to solve them using powerful algorithms like A*.

However, many problems in AI aren't about finding a path. Think about solving a Sudoku puzzle, scheduling university exams, or arranging seating at a dinner party. In these cases, the goal isn't to find a sequence of actions, but to find a valid assignment of values to a set of variables that satisfies a collection of rules.

Today, we shift our perspective to learn a powerful framework for modeling these kinds of problems. Our learning outcome is to formulate problems as Constraint Satisfaction Problems (CSPs). This is a fundamental skill in AI that allows us to represent a wide variety of puzzles and real-world challenges in a structured way that a computer can understand and solve.

Defining CSP Problems with Examples — This image shows several classic problems that can be modeled as CSPs: map coloring, Sudoku, cryptarithmetic (a number puzzle), and the N-Queens problem. All of these can be broken down into the core components of variables, domains, and constraints.

1. The Three Pillars of a CSP

At its core, a Constraint Satisfaction Problem is defined by three components. Any problem that can be described using these three pillars can be treated as a CSP.

To get a quick and clear definition of these components, let's watch a short video. The channel, "Gate Smashers," is specifically geared towards students preparing for the GATE exam, so its style should be very helpful.

What is Constraint Satisfaction | Constraint Satisfaction Problem (CSP) in AI with Example

This video, 'What is Constraint Satisfaction', provides a concise introduction to the topic. It clearly defines the three essential components of a CSP.

Watch the video from 01:31 to 02:37. This segment will introduce you to the three pillars of a CSP.

As the video explained, every CSP consists of:

Variables (V): A set of variables ${X_{1}, X_{2}, ..., X_{n}}$ that need to be assigned a value. These represent the decisions we need to make.
Domains (D): A set of domains ${D_{1}, D_{2}, ..., D_{n}}$ , where each domain $D_{i}$ is the set of possible values that variable $X_{i}$ can take.
Constraints (C): A set of rules that specify which combinations of values are allowed for the variables.

A solution to a CSP is a complete assignment of a value from its domain to each variable, such that all the constraints are satisfied simultaneously.

2. Formulating a Problem: Map Coloring

Let's make this concrete by formulating a classic example: the map coloring problem. The task is to color a map of different regions such that no two adjacent regions have the same color.

We'll use a simplified map of Australia as our case study. The following article provides an excellent, beginner-friendly walkthrough of how to translate this problem into the CSP framework.

Unlocking Puzzles with AI: A Beginner's Guide to Constraint ...

This article, 'Unlocking Puzzles with AI', does a great job of breaking down the formulation process. It uses a course scheduling analogy before diving into map coloring.

Please read the first two main sections of the article: 'What Exactly is a Constraint Satisfaction Problem?': This will reinforce the definitions we just learned. 'Formulating Map Coloring as a CSP': This is the key section. Pay close attention to how the regions, colors, and adjacency rules are mapped to variables, domains, and constraints.

Here is the map that the article discusses. Seeing it visually helps solidify the concepts.

CSP Example: Map Coloring of Australia — A CSP formulation for coloring the map of Australia. The **variables** are the states/territories (WA, NT, SA, etc.). The **domain** for each variable is the set of available colors {red, green, blue}. The **constraints** are rules stating that adjacent regions cannot have the same color (e.g., WA ≠ NT).

As you can see, the process of formulation is about abstraction. We don't need to know about cartography or the history of Australia; we just need to identify the three core components. Once a problem is in this V, D, C format, we can apply general-purpose AI algorithms to solve it.

3. Broadening the Scope: Exam Scheduling and Sudoku

The CSP framework is not limited to geographical puzzles. Let's explore how it applies to a more practical problem like scheduling university exams.

The next video, from Harvard's CS50 Introduction to AI course, demonstrates how to model this scheduling problem as a CSP and introduces the idea of a constraint graph, where nodes are variables and edges represent constraints between them.

Optimization - Lecture 3 - CS50's Introduction to Artificial Intelligence with Python 2020

This excerpt from a CS50 lecture on Optimization provides another excellent walkthrough of CSP formulation, using exam scheduling and Sudoku as examples.

Watch the segment from 50:59 to 56:51. Focus on how the exam scheduling problem is broken down: What are the variables? What is the domain for each variable? What are the constraints, and how do they form a 'constraint graph'?

This video also touches on Sudoku, which is another perfect example of a CSP. Let's formalize that.

Test your understanding!

Try to formulate a standard 9x9 Sudoku puzzle as a Constraint Satisfaction Problem. What are the variables, domains, and constraints?

Show answer

Here is the formal breakdown of Sudoku as a CSP:

Variables (V): The 81 cells in the 9x9 grid. We can label them as $X_{ij}$ , where $i$ is the row (1-9) and $j$ is the column (1-9).
Domains (D): For each variable $X_{ij}$ , the domain is the set of numbers ${1, 2, 3, 4, 5, 6, 7, 8, 9}$ . If a cell is already filled in the initial puzzle, its domain is just that single number.
Constraints (C): There are three main types of constraints:
1. Row Constraints: For each row $i$ , all variables in that row must have different values: $X_{i 1}, X_{i 2}, ..., X_{i 9}$ must be all different.
2. Column Constraints: For each column $j$ , all variables in that column must have different values: $X_{1 j}, X_{2 j}, ..., X_{9 j}$ must be all different.
3. 3x3 Box Constraints: For each of the nine 3x3 boxes, all variables within that box must have different values.

4. A Closer Look at Constraints

As we've seen, constraints are the rules that define the problem. It can be useful to categorize them. The GeeksforGeeks article below provides clear, concise definitions for different types of constraints.

Constraint Satisfaction Problems (CSP) in Artificial Intelligence

This article, 'Constraint Satisfaction Problems (CSP) in Artificial Intelligence', offers a structured overview of CSPs. We'll focus on its classification of constraints.

Read the subsections under 'Components of Constraint Satisfaction Problems' and 'Types of Constraint Satisfaction Problems'. Specifically, find the definitions for: Unary constraints (involving one variable) Binary constraints (involving two variables) Higher-order constraints (involving more than two) Hard and Soft constraints

In the map coloring problem, the rule WA ≠ NT is a binary constraint because it involves two variables. The Sudoku rule that "all cells in a row must be different" is a higher-order constraint (specifically, an AllDiff constraint) involving nine variables. An example of a unary constraint could be adding a rule to the map coloring problem like "Victoria (V) cannot be blue".

Conclusion

In this lesson, you've learned how to see problems through the lens of a powerful AI framework. By moving beyond pathfinding, you've unlocked a new way to model a huge class of puzzles, planning, and allocation tasks.

Key Takeaways:

Constraint Satisfaction Problems (CSPs) are a way to model problems where the goal is to find a valid assignment of values to variables.
Every CSP is defined by three components: Variables, Domains, and Constraints.
Formulating a problem as a CSP is the process of identifying these three components from the problem description.
Common examples of CSPs include map coloring, Sudoku, and scheduling problems.
Constraints can be classified by the number of variables they involve (unary, binary, higher-order).

Preview of the Next Lesson:

Knowing how to formulate a problem is the essential first step. The natural next question is: how do we get the computer to solve it? In the next lesson, we will learn about a fundamental algorithm for solving CSPs called backtracking search. You will learn to apply the backtracking algorithm to solve Constraint Satisfaction Problems.

Recommended resources

1. The Three Pillars of a CSP

2. Formulating a Problem: Map Coloring

3. Broadening the Scope: Exam Scheduling and Sudoku

4. A Closer Look at Constraints

Conclusion