Unit IV
Constraint
Satisfaction Problems
Dr. Praveen Kumar Loharkar
Introduction
• The goal of AI is to create intelligent machines that can perform tasks
that usually require human intelligence, such as reasoning, learning,
and problem-solving.
• Constraint Satisfaction Problem (CSP) is a fundamental topic in
artificial intelligence (AI) that deals with solving problems by
identifying constraints and finding solutions that satisfy those
constraints.
Introduction
• One of the key approaches in AI is the use of constraint satisfaction
techniques to solve complex problems.
• CSP is a specific type of problem-solving approach that involves
identifying constraints that must be satisfied and finding a solution
that satisfies all the constraints.
• CSP has been used in a variety of applications, including scheduling,
planning, resource allocation, and automated reasoning.
Introduction
• Sudoku: Each cell in the grid must be filled with a number from 1 to 9 without
repeating in any row, column, or 3x3 subgrid.
• Map Coloring: Assigning colors to regions on a map such that no adjacent regions
share the same color.
• Scheduling: Allocating time slots for classes, meetings, or exams without conflicts.
• Resource Allocation: Distributing resources like staff or equipment to tasks while
meeting various constraints3.
• N-Queens Problem: Placing N queens on an N×N chessboard so that no two
queens threaten each other.
• Cryptography: Solving puzzles and breaking codes by satisfying constraints on
possible solutions.
Introduction: Examples
Introduction:Basics
• CSP is defined by a set of variables X1, X2…………Xn and set of conditions C1,
C2……….Cn such that each of the variables Xi has a non-empty domain Di of
possible values.
• Variables- A finite set of Variables V1,V2……….Vn
• Domain- Each Variable has a domain D1,D2…..Dn from which it can take a
value.
• Constraints- A finite set of satisfaction constraints C1,C2….Cn
• For example, We need to color each country as Red, Green, Blue in such a
way that no neighboring country has the same colors.
• Identify Variable, Domain and constraint
Introduction: Examples
• Variables: (C1, C2, Cn) (each country)
• Domain: {Red, Green, Blue} (possible colors for each country)
• Constraints: For any two neighboring countries (Ci) and (Cj), (Ci is not
equal to Cj).
Student:
4
Student: Taking classes:
1 A B
C
2 B D E
3 C E F
4 E F G
Student: Taking classes: Exam slots:
1 A B
C Monday
Tuesday
2 B D E Wednesday
3 C E F
4 E F G
A
1 A B C
B C
2 B D E
D F
3 C E F
E
4 E F G
G
A
1 A B C
B C
2 B D E
D F
3 C E F
E
4 E F G
G
A
1 A B C
B C
2 B D E
D F
3 C E F
E
4 E F G
G
A
1 A B C
B C
2 B D E
D F
3 C E F
E
4 E F G
G
A
1 A B C
B C
2 B D E
D F
3 C E F
E
4 E F G
G
A
1 A B C
B C
2 B D E
D F
3 C E F
E
4 E F G
G
A
1 A B C
B C
2 B D E
D F
3 C E F
E
4 E F G
G
A
1 A B C
B C
2 B D E
D F
3 C E F
E
4 E F G
G
A
1 A B C
B C
2 B D E
D F
3 C E F
E
4 E F G
G
Constraint Satisfaction Problem
• Set of variables {X1, X2, ..., Xn}
• Set of domains for each variable {D1, D2, ..., Dn}
• Set of constraints C
• Variables
5 3 7 • {(0, 2), (1, 1), (1, 2), (2,
0), ...}
6 1 9 5
9 8 6 • Domains
8 6 3 • {1, 2, 3, 4, 5, 6, 7, 8, 9}
4 8 3 1 • for each variable
7 2 6 • Constraints
6 2 8 • {(0, 2) ≠ (1, 1) ≠ (1, 2) ≠
4 1 9 5 (2, 0), ...}
8 7 9
A Variables
{A, B, C, D, E, F,
G}
B C Domains
• {Monday, Tuesday, Wednesday}
• for each variable
D F
Constraints
E {A≠B, A≠C, B≠C, B≠D, B≠E,
G
C≠E, C≠F, D≠E, E≠F, E≠G,
F≠G}
hard
constraints
constraints that must be satisfied in
a correct solution
soft
constraints
constraints that express some notion of
which solutions are preferred over
others
unary
constraint
constraint involving only one
variable
unary
constraint
{A ≠ Monday}
binary
constraint
constraint involving t w o variables
binary
constraint
{A ≠ B}
node
consistency
when all the values in a variable's
domain satisfy the variable's unary
constraints
A B
{Mon, Tue, Wed} {Mon, Tue, Wed}
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
A B
{Mon, Tue, Wed} {Mon, Tue, Wed}
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
A B
{Tue, Wed} {Mon, Tue, Wed}
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
A B
{Tue, Wed} {Mon, Tue, Wed}
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
A B
{Tue, Wed} {Mon, Wed}
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
A B
{Tue, Wed} {Mon, Wed}
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
A B
{Tue, Wed} {Wed
}
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
A B
{Tue, Wed} {Wed
}
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
arc
consistency
when all the values in a variable's
domain satisfy the variable's binary
constraints
A B
{Tue, Wed} {Wed
}
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
A B
{Tue, Wed} {Wed
}
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
A B
{Tue {Wed
} }
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
A B
{Tue {Wed
} }
{A ≠ Mon, B ≠ Tue, B ≠ Mon, A ≠ B}
{Mon, Tue, Wed}
A
{Mon, Tue, Wed} B C {Mon, Tue, Wed}
{Mon, Tue, Wed} D F {Mon, Tue, Wed}
E G
{Mon, Tue, Wed} {Mon, Tue, Wed}
Types of Constraints in CSP
Unary Constraints:
• A unary constraint is a constraint on a single variable. For example, Variable A not
equal to “Red”.
Binary Constraints:
• A binary constraint involves two variables and specifies a constraint on their values.
For example, a constraint that two tasks cannot be scheduled at the same time
would be a binary constraint.
Global Constraints:
• Global constraints involve more than two variables and specify complex
relationships between them. For example, a constraint that no two tasks can be
scheduled at the same time if they require the same resource would be a global
constraint.
Identifying Variables, Domain
and Constraints: Map Colouring
Identifying Variables, Domain
and Constraints :Sudoku
Identifying Variables, Domain
and Constraints :Crossword
Home Assignment
• Determine Variables, Domain and Constraints for the following type
of Problems:
• N-Queens Problem
• Class Time-Table
• Knapsack Problem
Solving CSP Problems
• In the context of constraint satisfaction problems (CSP), backtracking typically comes before Forward
Checking:
• Backtracking: This is a basic search algorithm used to solve CSPs. It involves assigning values to
variables one at a time and checking if the current assignment violates any constraints.
• If a violation occurs, the algorithm backtracks to the previous variable and tries a different value. This
process continues until a solution is found or all possibilities are exhausted.
• Forward Checking: This technique is used to enhance the efficiency of backtracking.
• After assigning a value to a variable, forward checking looks ahead to see if the current assignment will
lead to any future conflicts.
• It does this by temporarily reducing the domains of the remaining variables. If forward checking detects
that a future variable has no valid values left, it triggers backtracking immediately, thus preventing the
algorithm from pursuing fruitless paths.
• in practice, backtracking is the foundational method, and forward checking is an enhancement that
helps to prune the search space and avoid unnecessary computations. They work hand-in-hand to solve
CSPs more efficiently.
Backtracking search example-
Australia map
Backtracking search example-
Australia map
Backtracking search example-
Australia map
What’s the Problem?
Improving backtracking
efficiency
• Which variable should be assigned next?
• In what order should its values be tried?
• Can we detect inevitable failure early?
Improving backtracking efficiency: Most
Constrained Variable
• Choose variables with fewest legal values
For example
• After the assignments for WA = red and NT = green, there is only one possible value for SA
• So it makes sense to assign SA = blue next rather than assigning Q
• In fact, after SA is assigned, the choices for Q, NSW , and V are all forced
• This intuitive idea of choosing the variable with the fewest “legal” values is called the
Minimum Remaining Values (MRV) heuristic
• It also has been called the “most constrained variable” or “fail-first” heuristic
Improving backtracking
efficiency: Least constraining
value
• The least constraining value (LCV) heuristic is a strategy used in
solving Constraint Satisfaction Problems (CSPs).
• It involves selecting the value for a variable that imposes the fewest
constraints on the remaining variables. In other words, it chooses the
value that leaves the most options open for the other variables
Forward checking
• Forward checking detects the inconsistency earlier than simple
backtracking and thus it allows branches of the search tree that will
lead to failure to be pruned earlier than with simple backtracking.
• Keep track of remaining legal values for unassigned variables
• Terminate the search when any variable has no legal values.
• Basically it involves:
• Assigning a variable with some value and then check if it still allows
remaining assignments to the future variables
• Keep track of remaining legal values for unassigned variables
• Terminate search when any variable has no legal values
Forward checking: Australian
Map Example
Forward checking
Forward checking
No assignment left for SA! Time to backtrack
Intelligent backtracking
• Intelligent backtracking is an enhanced version of the standard backtracking
algorithm used in solving Constraint Satisfaction Problems (CSPs).
• It aims to optimize the search process by focusing on the points where
conflicts occur, rather than blindly backtracking one step at a time.
• Example in CSP
• Consider a CSP like the N-Queens problem, where the goal is to place N
queens on an N×N chessboard such that no two queens threaten each
other.
• If a conflict arises (e.g., two queens are in the same row), intelligent
backtracking would directly address the variables (positions of the queens)
causing the conflict, rather than simply undoing the last move.
Intelligent backtracking
Example: N-Queens Problem
• The N-Queens problem involves placing N queens on an N×N chessboard such that no two queens threaten each other. Here’s
how intelligent backtracking can be applied:
• Initial Setup: Start placing queens one by one in different rows, ensuring no two queens are in the same column or diagonal.
• Conflict Detection: Suppose you place a queen in a position that leads to a conflict (e.g., two queens threaten each other).
• Identify Conflict Set: Instead of backtracking to the previous queen, intelligent backtracking identifies the specific queens
causing the conflict. For instance, if placing a queen in row 4 causes a conflict with queens in rows 1 and 3, these queens form
the conflict set.
• Backtrack to Conflict Source: The algorithm backtracks directly to the queens in the conflict set (rows 1 and 3) and tries different
positions for them, rather than just undoing the last move.
• Resolve Conflict: By addressing the root cause of the conflict, the algorithm finds a new position for the queens in the conflict
set that resolves the issue.
Benefits
• Efficiency: By targeting the source of conflicts, intelligent backtracking reduces unnecessary steps, making the search process
faster.
• Reduced Redundancy: It avoids re-exploring paths that are known to lead to conflicts, thus saving computational resources.
Local Search through CSP
• Why Use Local Search?
• Many search spaces are too big for systematic search.
• For CSPs, we only need to find a goal node. The path to a goal is irrelevant.
• Solution: local search
• Keep track of a single node, which is a complete assignment of
values to variables.
• Move to a neighbour of the node based on how good the neighbour
is.
Local Search through CSP
Example: N-Queens Problem
• The N-Queens problem involves placing N queens on an N×N chessboard such that no two queens threaten
each other. This means no two queens can be in the same row, column, or diagonal.
Variables:
• Each queen represents a variable, and there are N variables.
Domains:
• The domain of each variable is the set of possible positions in its respective column (i.e., {1, 2, …, N}).
Constraints:
• No two queens can be in the same row.
• No two queens can be in the same column.
• No two queens can be on the same diagonal.
Local Search through CSP
Local Search Approach:
• Initial State: Start with a random placement of N queens on the board.
• Objective Function: Minimize the number of pairs of queens that are attacking each other.
• Neighborhood: Generate neighboring states by moving a queen to a different position in
its column.
• Search Algorithm: Use a local search algorithm like Hill Climbing or Genetic Algorithms to
explore the state space and find a solution that satisfies all constraints.
Local Search through CSP
Steps:
Initialization: Start with a random configuration of queens on the board.
Evaluation: Calculate the number of attacking pairs of queens.
Move: Select a neighboring state by moving a queen to a different position
in its column.
Acceptance: Decide whether to accept the new state based on the objective
function and the search algorithm’s criteria.
Iteration: Repeat the evaluation and move steps until a solution is found or
a stopping criterion is met.
This approach can be adapted to various other CSPs, such as job-shop
scheduling, vehicle routing, and more.
Crypt-arthimetic Problems
• Crypt-arithmetic is a mathematical genre, where all the digits are replaced by any
other symbol or the letters of an alphabet, and if the same letter reappears in a
word, then it must be allotted the similar digit or a number, each time when it is
being used.
Points related Crypt-arithmetic:
• Each letter will be assigned with an individual digit, and no two letters will have the
same number.
• Now the main challenge here is to find the unique digit assigned to each
corresponding letter.
• Crypt-arithmetic is considered to be, both a science as well as an art.
• Hence apart from logic, one requires presence of mind and a little bit of common
sense to solve the problems.
Crypt-arthimetic
Problems:Approach
Understand the Problem:
• Carefully read the crypt-arithmetic puzzle to understand the given equations and constraints.
• Identify the letters that represent unique digits in the equation.
List the Letters:
• List all the distinct letters involved in the puzzle.
• Assign a placeholder for each letter (e.g., A, B, C, … Z) to represent digits.
Formulate the Equation:
• Convert the given words into a mathematical equation.
• Ensure that the equation follows standard mathematical rules (addition, subtraction,
multiplication, or division).
Identify Constraints:
• Identify any constraints or relationships given in the puzzle. For example, if a letter cannot be zero
(0), note it down.
Crypt-arthimetic
Problems:Approach
• Start with the Easiest Part:
• Look for parts of the equation that are straightforward to solve. This may involve finding single-digit
additions or subtractions.
• Trial and Error:
• Begin assigning possible digits to the letters, starting with the constraints and parts of the equation
with the fewest possibilities.
• Use a systematic approach, making sure to keep track of your assignments.
• Check for Consistency:
• After making an assignment, check if it maintains consistency within the equation and adheres to
the constraints.
• If a digit becomes inconsistent with other assignments, backtrack and try a different digit.
• Iterate and Refine:
• Continue the process of assigning digits, checking for consistency, and refining your assignments.
• Use logical deductions and process of elimination to narrow down possibilities.
Crypt-arthimetic Problems
Note: While studying also refer to the video : https://
[Link]/watch?v=Pnxu0vsKBT0
L46: CryptArithmetic
Problem in Artificial Intelligence | TO+GO = OUT & SEND+MORE= MON
EY Solutions - YouTube
Find the value of B + A + D if each alphabet represent an unique single
digit from 0 - 9:
Crypt-arthimetic Problems
Solution:
Step 1:
We know that sum of two single digit alphabets should not cross 18, and maximum difference between two
alphabets is 9.
If we add two maximum 4 digit numbers the sum is maximum 19998.
So the digit in the 5th left is 1.
Now from the 1st column 1 + E = 1F; if there is any carry over from the 2nd column 1 (carryover)+ 1 + E = 1F
But 1F is a two digit number in alphanumeric is equal to 10 + F
So 1+E=10+F⇒E−F=9
From this relation we know that E = 9, F = 0
or alternatively, 1+1+E=10+F⇒E−F=8
E = 9, F = 1 or E = 8, F = 0
Crypt-arthimetic Problems
From this, we can infer that F = 0 but we don’t know whether E is either equal to 8 or 9.
But surely F is not equal to 1 as we fixed already A = 1
Now from the 3rd column,
2C= 1 ⇒ C = 1/2
1 + 2C = 1 ⇒ C = 0
If the sum is a two digit number then
2C = 11 ⇒ C= 11/2
1 + 2C = 11 ⇒ C = 5
From the above C = 1/2 and 11/2 are not possible nor is 0 possible as we fixed F = 0
If C = 5 the the A = 1 and there is a carry over to the left column. and also there must be
carry over from the first column, but we dont know 1 + 2B is a single digit or two digit
number.
Crypt-arthimetic Problems
From the second and fourth columns
1+2B = G - - - - (1) or 1 + 2B = 10 + G - - - (2)
D + B = 10 + G - - - (3)
Solving (1) and (3) we get D - B = 11 which is not possible
But If we solve (2) and (3) then we get D - B = 1
So D and B are consecutive numbers and their sum is more than 10.
So acceptable values are D = 7 and B = 6
Crypt-arthimetic Problems
This completes our problem so final table looks like the following
Thank You