Syllabus and reference

Reference:

Stuart Russel and Peter Norvig, Artificial Intelligence: A Modern Approach, 4th edition, Pearson Education,
2021. Elaine Rich, Kavin Knight, Shivshankar Nair, Artificial intelligence, 3rd edition, Tata McGraw Hill
2019
Introduction-Recap of unit 2
The problem that we have discussed till now is whether it is an informed or
uninformed search technique in which we discussed state space.

In that, we explore our problems and go to different states. There we use the
tree method or graph method to explore the problem further.

But CSP is a totally different way. There are so many problems that we
represent in a different way.
Overview
• 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
1. 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.
2. One of the key approaches in AI is the use of constraint satisfaction
techniques to solve complex problems.
3. 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.
4. CSP has been used in a variety of applications, including scheduling,
planning, resource allocation, and automated reasoning.
What is the Constraint Satisfaction Problem in AI
In artificial intelligence and operations research, constraint satisfaction
is the process of finding a solution to a set of constraints that impose
conditions that the variables must satisfy.
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
Types of Constraints in CSP
Several types of constraints can be used in a Constraint satisfaction problem in
artificial intelligence, including:
 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.
 CSP Example- Map Coloring
• Map of Australia showing each of its states
and territories

• Task - To color each region either red, green,

or blue in such a way that no two neighboring
regions have the same color

• To formulate this as a CSP

• Identify variables, domain and constraints
There are many possible
solutions to this problem
Map Coloring-One possible solution

There are many

possible solutions
to this problem

One of the
solution
 Formulating CSPs: Sudoku
• Identify Variables,Domain,Constraints in Sudoku problem

Variables: Cells
Domain: each variable is {1,2,3,4,5,6,7,8,9}
Constraints: rows,columns,boxes contain all different numbers
Formulating CSPs: 8-Queen problem
• Variables-Position of each queen
• Domain- 64 squared of the chess board
• Constraint- Single queen in each row,
column and diagonal

• The 4-Queens Problem consists in placing

four queens on a 4 x 4 chessboard so that
no two queens can capture each other.
That is, no two queens are allowed to be
placed on the same row, the same column
or the same diagonal.
What Kinds of Algorithms are used for CSP?
1. Backtracking Tree Search
2. Tree Search with Forward Checking
3. Tree Search with Discrete Relaxation (arc consistency)
4. Local Search using Complete State Formulation
 Backtracking search
 It chooses values for one variable at a time and backtracks when a
variable has no legal values left to assign.
 Variable assignments are commutative, i.e., [ WA = red then NT =
green ] same as [ NT = green then WA = red ]
 Only need to consider assignments to a single variable at each
node.
 Depth-first search for CSPs with single-variable assignments is
called backtracking search
Backtracking search example

SA has no option to assign color so perform

backtracking
Back tracking search example Australia map
Back tracking search example-4 queen problem
Back tracking search example-4 queen problem
"What are some effective strategies and techniques for solving
Constraint Satisfaction Problems”?
Solution-
 Variable ordering heuristics
 Value ordering heuristics
 Constraint tightening
 Improving backtracking efficiency
How to improve backtracking?
 Backtracking can be improved by using heuristics, such as choosing
the most constrained variable or the least constraining value, to
guide the search and reduce the number of backtracks.
 Backtracking improved by-
1. Which variable should be assigned next?
2. In what order should its values be tried?
3. Can we detect inevitable failure early?
 Most Constrained Variable
• Choose variables with fewest legal values

For example
 After the assignments for WA = red and NT = 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
 Most constraining variable

 A good idea is to use it as a tie-breaker among most constrained variables.

• Most constrained variable: Choose the variable with the fewest legal
values.
 Least constraining value

• Given a variable to assign the least constraining value:

-The one that rules out the fewest values in the remaining variables.
 Least constraining value
• Once a variable has been selected, the algorithm must decide on
the order in which to examine its values
• For this, the least-constraining-value heuristic can be effective in
some cases.
• It prefers the value that rules out the fewest choices for the
neighboring variables in the constraint graph
For example:
• We have generated the partial assignment with WA = red and
NT = green and that our next choice is for Q
• Blue would be a bad choice because it eliminates the last legal
value left for Q’s neighbor, SA
• Least-constraining-value heuristic therefore prefers red to blue
 Forward checking
Idea:
 To assign a variable with some value and then check if it still allows
remaining assignments to the future variables
 Keep a track of remaining legal values for unassigned variables
 Terminate search when any variable has no legal values
Forward checking example
Forward checking example
Forward checking example
 Forward checking example

No assignment left for SA! Time to backtrack

Forward checking example
Forward checking example

One of the
solution
 Summary of forward checking in the above example
• There are two important points to notice
about this example
• First, notice that after WA = red and
Q = green are assigned, the domains of NT
and SA are reduced to a single value; we have
eliminated branching on these variables
altogether by propagating information from
WA and Q
• A second point to notice is that after V
= blue, the domain of SA is empty Hence,
forward checking has detected that the
partial assignment {WA = red, Q = green, V =
blue} is inconsistent with the constraints of
the problem, and the algorithm will therefore
backtrack immediately
 Forward checking with MRV
• For many problems the search will be more effective if we combine the MRV heuristic with forward check
• Consider in figure after assigning {WA = red}
• Intuitively, it seems that that assignment constrains its neighbors, NT and SA
• So we should handle those variables next, and then all the other variables will fall into place
• That’s exactly what happens with MRV
• NT and SA have two values, so one of them is chosen first
• Then the other, then Q, NSW , and V in order
• Finally T still has three values, and any one of them works
 Problem with Forward checking
Forward checking propagates information from assigned to unassigned
variables, but doesn't provide early detection for all failures.
 NT and SA cannot both be blue!
 Constraint propagation repeatedly enforces constraints locally.
 Arc Consistency
 Arc consistency eliminates values from domain of variable that can
never be part of a consistent solution.
 We can achieve consistency on arc by deleting values form Di (domain
of variable at tail of constraint arc) that fail this condition.
 Arc Consistency
1

7
 Comparison of Methods
• Backtracking tree search is a blind search.
• Forward checking checks constraints between the
current variable and all future ones.
• Arc consistency then checks constraints between all pairs
of future (unassigned) variables.
 Summary
 CSPs are a special kind of problem
 states defined by values of a fixed set of variables
 goal test defined by constraints on variable values
 Backtracking = depth-first search with one variable assigned per node
 Variable ordering and value selection heuristics help significantly
 Forward checking prevents assignments that guarantee later failure
 Constraint propagation (e.g., arc consistency) does additional work to
constrain values and detect inconsistencies
Practice Questions
Practice Questions
Practice Questions
 8 Queen Problem
 The eight queens problem is the problem of placing eight queens on an 8×8 chessboard such
that none of them attack one another (no two are in the same row, column, or diagonal). More
generally, the n queens problem places n queens on an n×n chessboard.

There are different

solutions for the
problem.
 Exploring Crypt Arithmetic:

(Solving the Mystery of Numbers and

Letters)
Outline
• Introduction
• What is Crypt Arithmetic?
• Rules or constraints on a crypt arithmetic
problem
• Strategies for Solving Crypt Arithmetic Puzzles
• Examples of crypt arithmetic puzzles
Introduction

 Crypt arithmetic Problem is a type of constraint satisfaction

problem where the game is about digits and its unique

replacement either with alphabets or other symbols.

In crypt arithmetic problem, the digits (0-9) get substituted by
some possible alphabets or symbols.
The task in crypt arithmetic problem is to substitute each digit
with an alphabet to get the result arithmetically correct.
 What is Crypt Arithmetic?
 Crypt arithmetic problems are mathematical puzzles in which the digits
are replaced by letters of the alphabet

The rules or constraints on a crypt arithmetic problem are as follows:

 There should be a unique digit to be replaced with a unique alphabet.
 The result should satisfy the predefined arithmetic rules, i.e., 2+2 =4
 Digits should be from 0-9 only.
 There should be only one carry forward, while performing the addition
operation on a problem.
 The problem can be solved from both sides, i.e., left hand side (L.H.S),
or right hand side (R.H.S)
Strategies for Solving Crypt Arithmetic
Puzzles

 Understanding basic arithmetic operations.

 Identifying unique digits and restrictions.

 Creating equations and solving step by

step.

 Applying trial and error method.

Examples of crypt arithmetic puzzles

Let’s try to solve this examples

1. Consider the following crypt arithmetic problem

Determine the values for variables {S,E,N,D,M,O,R,Y}.

2. Consider the following crypt arithmetic problem
3. Consider the following crypt arithmetic problem
4. Consider the following crypt arithmetic problem
5. Consider the following crypt arithmetic problem

As Homework