Amity School of Engineering and Technology

MODULE 1

Problem Solving

Programme: B. Tech-IT,
Semester: VIth
Course: Artificial Intelligence (CSE401)
Name of Faculty: Dr. Deepti Mehrotra
1
Learning objective
• Understand the concept of problem
solving

2
Problem solving

3
Solving Problems
• Define the problem
• Analyse the problem
• Isolate and represent the task knowledge
to solve the problem
• Choose the best problem solving
techniques and apply them to solve the
particular problem..

4
Problem representation

5
States

6
State modification:
successor function

7
State space

8
Problem solution

9
Problem description

10
Well Defined Problems and
Solutions

0 11
3
/
Example: Water Pouring

0 12
3
/
A Water Jug Problem
Puzzle-Solving as Search
Example: Water Pouring

0 15
3
/
Example: Water Pouring

0 16
3
/
Production Rules for the Water
Jug Problem
Fill the 4-gallon jug
1 (x,y)  (4,y)
if x < 4 Fill the 3-gallon jug
2 (x,y)  (x,3)
if y < 3
3 (x,y)  (x – d,y) Pour some water out of the 4-gallon jug
if x > 0
4 (x,y)  (x,y – d) Pour some water out of the 3-gallon jug
if x > 0
5 (x,y)  (0,y) Empty the 4-gallon jug on the ground
if x > 0
6 (x,y)  (x,0) Empty the 3-gallon jug on the ground
if y > 0
7 (x,y)  (4,y – (4 – x)) Pour water from the 3-gallon jug into
if x + y ≥ 4 and y > 0 the 4-gallon jug until the 4-gallon jug
is full
The Water Jug Problem (cont’d)

8 (x,y)  (x – (3 – y),3) Pour water from the 4-gallon jug

if x + y ≥ 3 and x > 0 into the 3-gallon jug until the
3-gallon jug is full
9 (x,y)  (x + y, 0)
if x + y ≤ 4 and y > 0 Pour all the water from the 3-
gallon jug into the 4-gallon jug
10 (x,y)  (0, x + y)
Pour all the water from the 4-
if x + y ≤ 3 and x > 0 gallon jug into the 3-gallon jug
11 (0,2)  (2,0) Pour the 2 gallons from the 3-
gallon jug into the 4-gallon jug
12 (x,2)  (0,2)
Empty the 4-gallon jug on the
ground
One Solution to the Water Jug
Problem
Gallons in the Gallons in Rule
4-Gallon Jug the 3-Gallon Applied
Jug
0 0 2
0 3 9
3 0 2
3 3 7
4 2 5 or 12
0 2 9 or 11
2 0
Example: Water Pouring
(0,0)

(4,0) (0,3)

(1,3) (4,3) (3,0)

(1,0) (0,1)
(3,3) (4,2)

(4,1)
(2,3)

(2,0) (0,2)

0 20
3
/
• Given:
• a five gallon jug
• a seven gallon jug
• a way to fill up the jugs
• a way to pour out water
• End up with:
• exactly 1 gallon of water in one of the jugs.

21
water space water space
start with both
0 5 0 7
jugs empty
fill the 7 0 5 7 0
pour 7 into 5 5 0 2 5
empty the 5 0 5 2 5
pour 7 into 5 2 3 0 7
fill the 7 2 3 7 0
pour 7 into 5 5 0 4 3
empty the 5 0 5 4 3
pour 7 into 5 4 1 0 7
fill the 7 4 1 7 0
pour 7 into 5 5 0 6 1
empty the 5 0 5 6 1
pour 7 into 5
5 0 1 6
(done)
empty the 5
(just to be 0 5 1 6 22
tidy)
• We've filled the 7 gallon jug three times, and
emptied the 5 gallon jug four times.
• Each time we filled the 7 gallon jug, it started
out empty.
• Each time we emptied the 5 gallon jug, we
emptied it at a time that it was full.
• That can be expressed as:
• (7⋅3) + (5⋅(-4)) = 21 - 20 = 1

23
• at various times there was 2, 4 and 6 in the
seven gallon jug.
• How can we make 3?
• That is, can we find integers a and b such
that 7a + 5b = 3?
• If we solve the equation for b, we get:
• b = (3 -7a)/5
• Since m and n both have to be integers, we can
just try some different integers for a until we
24
get a result for b that is also an integer.
• That is, we need (3-7a) to be divisible by 5:
• So, if b is -5, and a is 4, then we have our answer: 7(4) + 5(-5)
=3
• So, this would suggest that if we just continue the process we
used to get 1 gallon just one more step, we can get three
gallons:
a 3-7a
0 3-0=3
1 3-7=-4
2 3-14=-11
3 3-21=-18
4 3-28=-25
25
• So we repeat the last two lines of the table above:
water space water space
start with both
0 5 0 7
jugs empty
⋮
many steps omitted here (see table above)
here next are the last two lines of the previous table:

pour 7 into 5
5 0 1 6

empty the 5
0 5 1 6

and we continue from here:

pour 7 into 5 1 4 0 7
fill the 7 1 4 7 0
pour 7 into 5
5 0 3 7
(done)
empty the 5
0 5 3 7
(just to be tidy) 26
• Now, the real reason for emptying the five at
the end should become more clear—it makes
the math work out. We can use the
equation ap + bq = x, where:
• p and q are the sizes of the jugs
• x is the amount of water we are looking for
• a and b represent how many times we fill up or
empty the jugs

27
Example: Eight Puzzle
• States:
– Description of the eight
tiles and location of the 7 2 4
blank tile
• Successor Function: 5 6
– Generates the legal states 8 3 1
from trying the four actions
{Left, Right, Up, Down}
• Goal Test:
– Checks whether the state
matches the goal 1 2 3
configuration
• Path Cost: 4 5 6
– Each step costs 1
7 8

03/18/2024 28
Example: Eight Puzzle

0 29
3
/
Example: Eight Queens
• Place eight queens on a Q
chess board such that no
queen can attack another Q
queen
Q
• No path cost because Q
only the final state
counts! Q
Q
• Incremental formulations
• Complete state Q
formulations Q
03/18/2024 30
Example: Eight Queens
• States:
– Any arrangement of 0 to 8
Q
queens on the board
• Initial state:
Q
– No queens on the board Q
• Successor function:
– Add a queen to an empty Q
square
• Goal Test: Q
– 8 queens on the board and
none are attacked Q
• 64*63*…*57 = 1.8*1014
possible sequences Q
– Ouch!
Q
03/18/2024 31
Example: Eight Queens
• States: Q
– Arrangements of n queens,
one per column in the Q
leftmost n columns, with no
queen attacking another Q
are states
• Successor function: Q
– Add a queen to any square
in the leftmost empty Q
column such that it is not
attacked by any other Q
queen.
• 2057 sequences to Q
investigate Q
03/18/2024 32
Amity School of Engineering and Technology

Thank You

33