ARTIFICIAL INTELLIGENCE LAB

DAVANGERE UNIVERSITY
DAVANGERE-577007, KARNATAKA

ARTIFICIAL INTELLIGENCE LAB

BACHELOR OF COMPUTER APPLICATIONS

BAPUJI INSTITUTE OF HI-TECH EDUCATION

DAVANGERE – 577 004

BCA, BIHE Davangere

 ARTIFICIAL INTELLIGENCE LAB

PART A:
1. write a program to implement Breadth first search using python

2. write a program to implement Depth first search using python

3. write a program to implement Tic-Tac-Toe game using python
4. write a program to implement 8-Puzzale problem using python
5. write a program to implement Water-Jug problem using python
6. write a program to implement Travelling Salesman problem using python
7. write a program to implement Tower of Hanoi problem using python
8. write a program to implement Monkey Banana problem using python
9. write a program to implement Alpha-Beta Pruning problem using python
10. write a program to implement 8-Queens problem using python

PART B:
1.write a program to implement hill climbing algorithm in python
2.write a program to implement a* algorithm in python
3.Implementation of Python Basic Libraries such as Math, Numpy and Scipy
4.Implementation of Python Libraries for ML application such as Pandas and
Matplotlib
5.Creation AND Loading different datasets in Python
6.Write a Python program to compute Mean, Median, Mode, Variance and
Standard deviation using datasets.
7.Implementation of Find S algorithm
8. Implementation of Candidate elimination algorithm
9.Write a program to implement Simple Linear Regression and plot the graph
10.Write a Python program to implement Stemming for a given sentence using
NLTK

BCA, BIHE Davangere

 ARTIFICIAL INTELLIGENCE LAB

PART A:
1. write a program to implement Breadth first search using python
graph = {
'5' : ['3','7'],
'3' : ['2', '4'],
'7' : ['8'],
'2' : [],
'4' : ['8'],
'8' : []
}

visited = []
queue = []
def bfs(visited, graph, node):
visited.append(node)
queue.append(node)

while queue:
m = queue.pop(0)
print (m, end = " ")

for neighbour in graph[m]:

if neighbour not in visited:
visited.append(neighbour)
queue.append(neighbour)

print("Following is the Breadth-First Search")

bfs(visited, graph, '5')

output:
Following is the Breadth-First Search
537248

2. write a program to implement Depth first search using python

graph = {
'5' : ['3','7'],
'3' : ['2', '4'],
'7' : ['8'],
'2' : [],
'4' : ['8'],
'8' : []
}

visited = set()

def dfs(visited, graph, node):

if node not in visited:

BCA, BIHE Davangere

 ARTIFICIAL INTELLIGENCE LAB

print (node)
visited.add(node)
for neighbour in graph[node]:
dfs(visited, graph, neighbour)

print("Following is the Depth-First Search")

dfs(visited, graph, '5')

Output:
Following is the Depth-First Search
532487
3. write a program to implement Tic-Tac-Toe game using python
board = [" " for x in range(9)]
def print_board():
row1 = "| {} | {} | {} |".format(board[0], board[1], board[2])
row2 = "| {} | {} | {} |".format(board[3], board[4], board[5])
row3 = "| {} | {} | {} |".format(board[6], board[7], board[8])
print()
print(row1)
print(row2)
print(row3)
print()
def player_move(icon):
if icon == "X":
number = 1
elif icon == "O":
number = 2
print("Your turn player {}".format(number))
choice = int(input("Enter your move (1-9): ").strip())
if board[choice - 1] == " ":
board[choice - 1] = icon
else:
print()
print("That space is taken!")
def is_victory(icon):
if (board[0] == icon and board[1] == icon and board[2] == icon) or \
(board[3] == icon and board[4] == icon and board[5] == icon) or \
(board[6] == icon and board[7] == icon and board[8] == icon) or \
(board[0] == icon and board[3] == icon and board[6] == icon) or \
(board[1] == icon and board[4] == icon and board[7] == icon) or \
(board[2] == icon and board[5] == icon and board[8] == icon) or \
(board[0] == icon and board[4] == icon and board[8] == icon) or \
(board[2] == icon and board[4] == icon and board[6] == icon):
return True
else:
return False
def is_draw():
if " " not in board:
return True
else:

BCA, BIHE Davangere

 ARTIFICIAL INTELLIGENCE LAB

return False
while True:
print_board()
player_move("X")
print_board()
if is_victory("X"):
print("X wins! Congratulations!")
break
elif is_draw():
print("It's a draw!")
break
player_move("O")
if is_victory("O"):
print_board()
print("O wins! Congratulations!")
break
elif is_draw():
print("It's a draw!")
break
Output:

| | | |
| | | |
| | | |

Your turn player 1

Enter your move (1-9): 1

|X| | |
| | | |
| | | |

Your turn player 2

Enter your move (1-9): 5

|X| | |
| |O| |
| | | |

Your turn player 1

Enter your move (1-9): 2

|X|X| |
| |O| |
| | | |

Your turn player 2

Enter your move (1-9): 7

|X|X| |

BCA, BIHE Davangere

 ARTIFICIAL INTELLIGENCE LAB

| |O| |
|O| | |

Your turn player 1

Enter your move (1-9): 3

|X|X|X|
| |O| |
|O| | |

X wins! Congratulations!

4. write a program to implement 8-Puzzale problem using python

def getInvCount(arr):
inv_count = 0
empty_value = -1
for i in range(0, 9):
for j in range(i + 1, 9):
if arr[j] != empty_value and arr[i] != empty_value and arr[i] > arr[j]:
inv_count += 1
return inv_count

def isSolvable(puzzle) :

inv_count = getInvCount([j for sub in puzzle for j in sub])

return (inv_count % 2 == 0)

puzzle = [[8, 1, 2],[-1, 4, 3],[7, 6, 5]]

if(isSolvable(puzzle)) :
print("Solvable")
else :
print("Not Solvable")

Output:
Solvable

BCA, BIHE Davangere

 ARTIFICIAL INTELLIGENCE LAB

5. write a program to implement Water-Jug problem using python

from collections import defaultdict

jug1, jug2, aim = 4, 3, 2
visited = defaultdict(lambda: False)
def waterJugSolver(amt1, amt2):
if (amt1 == aim and amt2 == 0) or (amt2 == aim and amt1 == 0):
print(amt1, amt2)
return True
if visited[(amt1, amt2)] == False:
print(amt1, amt2)
visited[(amt1, amt2)] = True
return (waterJugSolver(0, amt2) or
waterJugSolver(amt1, 0) or
waterJugSolver(jug1, amt2) or
waterJugSolver(amt1, jug2) or
waterJugSolver(amt1 + min(amt2, (jug1-amt1)),
amt2 - min(amt2, (jug1-amt1))) or
waterJugSolver(amt1 - min(amt1, (jug2-amt2)),
amt2 + min(amt1, (jug2-amt2))))
return False
print("Steps: ")
waterJugSolver(0, 0)

Output:
Steps:
00
40
43
03
30
33
42
02

6. write a program to implement Travelling Salesman problem using

python
from sys import maxsize
from itertools import permutations
V=4
def travellingSalesmanProblem(graph, s):
vertex = []
for i in range(V):
if i != s:

BCA, BIHE Davangere

 ARTIFICIAL INTELLIGENCE LAB

vertex.append(i)

min_path = maxsize
next_permutation=permutations(vertex)
for i in next_permutation:
current_pathweight = 0
k=s
for j in i:
current_pathweight += graph[k][j]
k=j
current_pathweight += graph[k][s]
min_path = min(min_path, current_pathweight)
return min_path
if __name__ == "__main__":
graph = [[0, 10, 15, 20], [10, 0, 35, 25],
[15, 35, 0, 30], [20, 25, 30, 0]]
s=0
print(travellingSalesmanProblem(graph, s))

Output:
80

7. write a program to implement Tower of Hanoi problem using python

def TowerOfHanoi(n , source, destination, auxiliary):
if n==1:
print ("Move disk 1 from source",source,"todestination",destination)
return
TowerOfHanoi(n-1, source, auxiliary, destination)
print ("Move disk",n,"fromsource",source,"todestination",destination)
TowerOfHanoi(n-1, auxiliary, destination, source)
n=4
TowerOfHanoi(n,'A','B','C')

Output:
Move disk 1 from source A to destination C
Move disk 2 from source A to destination B
Move disk 1 from source C to destination B
Move disk 3 from source A to destination C
Move disk 1 from source B to destination A
Move disk 2 from source B to destination C
Move disk 1 from source A to destination C
Move disk 4 from source A to destination B
Move disk 1 from source C to destination B
Move disk 2 from source C to destination A
Move disk 1 from source B to destination A
Move disk 3 from source C to destination B
Move disk 1 from source A to destination C
Move disk 2 from source A to destination B
Move disk 1 from source C to destination B

BCA, BIHE Davangere

 ARTIFICIAL INTELLIGENCE LAB

8. write a program to implement Monkey Banana problem using python

i=0
def Monkey_go_box(x,y):
global i
i=i+1
print('step:',i,'monkey slave',x,'Go to '+y)
def Monkey_move_box(x,y):
global i
i=i+1
print('step:', i, 'monkey take the box from', x, 'deliver to ' + y)
def Monkey_on_box():
global i
i=i+1
print('step:', i, 'Monkey climbs up the box')
def Monkey_get_banana():
global i
i=i+1
print('step:', i, 'Monkey picked a banana')
codeIn=['monkey', 'banana','box']
monkey=codeIn[0]
banana=codeIn[1]
box=codeIn[2]
print('The steps are as follows:')
Monkey_go_box(monkey, box)
Monkey_move_box(box, banana)
Monkey_on_box()
Monkey_get_banana()

Output:
The steps are as follows:
step: 1 monkey slave monkey Go to boxs
step: 2 monkey take the box from box deliver to banana
step: 3 Monkey climbs up the box
step: 4 Monkey picked a banana

BCA, BIHE Davangere

 ARTIFICIAL INTELLIGENCE LAB

9. write a program to implement Alpha-Beta Pruning problem using

python
MAX, MIN = 1000, -1000
def minimax(depth, nodeIndex, maximizingPlayer, values, alpha, beta):
if depth == 3:
return values[nodeIndex]
if maximizingPlayer:
best = MIN
for i in range(0, 2):
val = minimax(depth + 1, nodeIndex * 2 + i, False, values, alpha, beta)
best = max(best, val)
alpha = max(alpha, best)
if beta <= alpha:
break
return best
else:
best = MAX
for i in range(0, 2):
val = minimax(depth + 1, nodeIndex * 2 + i, True, values, alpha, beta)
best = min(best, val)
beta = min(beta, best)
if beta <= alpha:
break
return best
if __name__ == "__main__":
values = [3, 5, 6, 9, 1, 2, 0, -1]
print("The optimal value is :", minimax(0, 0, True, values, MIN, MAX))

Output:The optimal value is : 5

10. write a program to implement 8-Queens problem using python

print ("Enter the number of queens")
N = int(input())
board = [[0]*N for _ in range(N)]
def attack(i, j):
for k in range(0,N):
if board[i][k]==1 or board[k][j]==1:
return True
for k in range(0,N):
for l in range(0,N):
if (k+l==i+j) or (k-l==i-j):
if board[k][l]==1:
return True
return False
def N_queens(n):
if n==0:
return True
for i in range(0,N):

BCA, BIHE Davangere

 ARTIFICIAL INTELLIGENCE LAB

for j in range(0,N):
if (not(attack(i,j))) and (board[i][j]!=1):
board[i][j] = 1
if N_queens(n-1)==True:
return True
board[i][j] = 0
return False
N_queens(N)
for i in board:
print (i)

Output:
Enter the number of queens
8
[1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 1, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 1, 0]
[0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0]

BCA, BIHE Davangere

 ARTIFICIAL INTELLIGENCE LAB

PART B:
1.write a program to implement hill climbing algorithm in python
from numpy import arange
from matplotlib import pyplot
def objective(x):
return x[0]**2.0
r_min, r_max = -5.0, 5.0
inputs = arange(r_min, r_max, 0.1)
results = [objective([x]) for x in inputs]
pyplot.plot(inputs, results)
x_optima = 0.0
pyplot.axvline(x=x_optima, ls='--', color='red')
pyplot.show()

Output:

2.write a program to implement a* algorithm in python

def aStarAlgo(start_node, stop_node):

open_set = set(start_node)
closed_set = set()
g = {}
parents = {}

g[start_node] = 0

parents[start_node] = start_node

while len(open_set) > 0:

n = None

for v in open_set:
if n == None or g[v] + heuristic(v) < g[n] + heuristic(n):
n=v

BCA, BIHE Davangere

 ARTIFICIAL INTELLIGENCE LAB

if n == stop_node or Graph_nodes[n] == None:

pass
else:
for (m, weight) in get_neighbors(n):

if m not in open_set and m not in closed_set:

open_set.add(m)
parents[m] = n
g[m] = g[n] + weight

else:
if g[m] > g[n] + weight:

g[m] = g[n] + weight

parents[m] = n

if m in closed_set:
closed_set.remove(m)
open_set.add(m)

if n == None:
print('Path does not exist!')
return None

if n == stop_node:
path = []

while parents[n] != n:
path.append(n)
n = parents[n]

path.append(start_node)

path.reverse()

print('Path found: {}'.format(path))

return path

open_set.remove(n)
closed_set.add(n)

print('Path does not exist!')

return None

BCA, BIHE Davangere

 ARTIFICIAL INTELLIGENCE LAB

def get_neighbors(v):
if v in Graph_nodes:
return Graph_nodes[v]
else:
return None

def heuristic(n):
H_dist = {
'A': 11,
'B': 6,
'C': 99,
'D': 1,
'E': 7,
'G': 0,

return H_dist[n]

Graph_nodes = {
'A': [('B', 2), ('E', 3)],
'B': [('C', 1),('G', 9)],
'C': None,
'E': [('D', 6)],
'D': [('G', 1)],

}
aStarAlgo('A', 'G')
Output:
Path found: ['A', 'F', 'G', 'I', 'J']

3.Implementation of Python Basic Libraries such as Math, Numpy and Scipy

a.Math Function
import math
A = 16
print("square root of A")
print(math.sqrt(A))

Output:
square root of A 4.0

b. Numpy Function
import math
import numpy as np
A = 16

BCA, BIHE Davangere

 ARTIFICIAL INTELLIGENCE LAB

print("square root of A")

print(math.sqrt(A))
array1 = np.array([1, 2, 3])
array2 = np.array([4, 5, 6])
result_addition = array1 + array2
print("Display the original arrays and the results")
print("Array 1:", array1)
print("Array 2:", array2)
print("Element-wise Addition:", result_addition)

Output:
Display the original arrays and the results
Array 1: [1 2 3]
Array 2: [4 5 6]
Element-wise Addition: [5 7 9]

c. Scipy Function
import numpy as np
from scipy import linalg
two_d_array=np.array([[4,5],[3,2]])
print(linalg.det(two_d_array))
Output:
-7.0

4.Implementation of Python Libraries for ML application such as Pandas and

Matplotlib

a.Pandas
import pandas as pd
data ={"country": ["Brazil", "Russia", "India", "China", "South Africa"],
"capital": ["Brasilia", "Moscow", "New Delhi", "Beijing", "Pretoria"],
"area": [8.516, 17.10, 3.286, 9.597, 1.221],
"population": [200.4, 143.5, 1252, 1357, 52.98] }
data_table =pd.DataFrame(data)
print(data_table)

Output:

BCA, BIHE Davangere

 ARTIFICIAL INTELLIGENCE LAB

b.Matplotlib

import matplotlib.pyplot as plt

import numpy as np
x =np.linspace(0, 10, 100)
plt.plot(x, x, label ='linear')
plt.legend()
plt.show()

Output:

5.Creation AND Loading different datasets in Python

import pandas as pd
df1 = pd.read_excel("C:\\Users\\BCA42\\Desktop\\Book1.xlsx")
df2 = pd.read_csv("C:\\Users\\BCA42\\Desktop\\Book3.csv")

Output:

6.Write a Python program to compute Mean, Median, Mode, Variance and Standard
deviation using datasets.
a.Mean
import numpy as np
list=[2, 4, 4, 4, 5, 5, 7, 9]
print(np.mean(list))

Output:
5.0

BCA, BIHE Davangere

 ARTIFICIAL INTELLIGENCE LAB

b.Median

import numpy as np
list=[2, 4, 4, 4, 5, 5, 7, 9]
print(np.median(list))

Output:
4.5

c.Mode
import statistics
list = [2, 4, 4, 4, 5, 5, 7, 9]
print(statistics.mode(list))

Output:
4

d.Variance

import numpy as np
list = [2, 4, 4, 4, 5, 5, 7, 9]
print(np.var(list))

Output:
4.0

e.Standard deviation
import numpy as np
list = [2, 4, 4, 4, 5, 5, 7, 9]
print(np.std(list))

Output:
2.0

7.Implementation of Find S algorithm

training_data = [
(['Yes', 'Yes'], 'Dog'),
(['Yes', 'No'], 'Cat'),
(['No'
, 'Yes'], 'Dog'),
(['No', 'No'], 'Cat'),
(['Yes', 'Yes'], 'Dog')
]
# Initial hypothesis
h = ['∅', '∅']
# Find-S algorithm
for example, label in training_data:
if label == 'Dog':
for i in range(len(example)):
if h[i] == '∅':
h[i] = example[i]

BCA, BIHE Davangere

 ARTIFICIAL INTELLIGENCE LAB

elif h[i] != example[i]:

h[i] = '?'
print("Final hypothesis:", h)

Output:
Final hypothesis: ['?', 'Yes']

8. Implementation of Candidate elimination algorithm

import csv
with open("C:\\Users\\BCA74\\Desktop\\trainingdata.csv") as f:
csv_file=csv.reader(f)
data=list(csv_file)

s=data[1][:-1]
g=[['?' for i in range(len(s))] for j in range(len(s))]

for i in data:
if i[-1]=="Yes":
for j in range(len(s)):
if i[j]!=s[j]:
s[j]='?'
g[j][j]='?'

elif i[-1]=="No":
for j in range(len(s)):
if i[j]!=s[j]:
g[j][j]=s[j]
else:
g[j][j]="?"
print("\nSteps of Candidate Elimination Algorithm",data.index(i)+1)
print(s)
print(g)
gh=[]
for i in g:
for j in i:
if j!='?':
gh.append(i)
break
print("\nFinal specific hypothesis:\n",s)

print("\nFinal general hypothesis:\n",gh)

Output:
Steps of Candidate Elimination Algorithm 1
['Sunny', 'Warm', '?', 'Strong', 'Warm', 'Same']
[['?', '?', '?', '?', '?', '?'], ['?', '?', '?', '?', '?', '?'], ['?', '?', '?', '?', '?', '?'], ['?', '?', '?', '?', '?', '?'], ['?', '?', '?', '?', '?',
'?'], ['?', '?', '?', '?', '?', '?']]

Steps of Candidate Elimination Algorithm 2

['Sunny', 'Warm', '?', 'Strong', 'Warm', 'Same']
[['?', '?', '?', '?', '?', '?'], ['?', '?', '?', '?', '?', '?'], ['?', '?', '?', '?', '?', '?'], ['?', '?', '?', '?', '?', '?'], ['?', '?', '?', '?', '?',
'?'], ['?', '?', '?', '?', '?', '?']]

BCA, BIHE Davangere

 ARTIFICIAL INTELLIGENCE LAB

Steps of Candidate Elimination Algorithm 3

['Sunny', 'Warm', '?', 'Strong', 'Warm', 'Same']
[['Sunny', '?', '?', '?', '?', '?'], ['?', 'Warm', '?', '?', '?', '?'], ['?', '?', '?', '?', '?', '?'], ['?', '?', '?', '?', '?', '?'], ['?',
'?', '?', '?', '?', '?'], ['?', '?', '?', '?', '?', 'Same']]

Steps of Candidate Elimination Algorithm 4

['Sunny', 'Warm', '?', 'Strong', '?', '?']
[['Sunny', '?', '?', '?', '?', '?'], ['?', 'Warm', '?', '?', '?', '?'], ['?', '?', '?', '?', '?', '?'], ['?', '?', '?', '?', '?', '?'], ['?',
'?', '?', '?', '?', '?'], ['?', '?', '?', '?', '?', '?']]

Final specific hypothesis:

['Sunny', 'Warm', '?', 'Strong', '?', '?']

Final general hypothesis:

[['Sunny', '?', '?', '?', '?', '?'], ['?', 'Warm', '?', '?', '?', '?']]

9.Write a program to implement Simple Linear Regression and plot the graph

import numpy as nmp

import numpy as np
import matplotlib.pyplot as mtplt

def estimate_coeff(p, q):

n1 = nmp.size(p)
m_p = nmp.mean(p)
m_q = nmp.mean(q)
SS_pq = nmp.sum(q * p) - n1 * m_q * m_p
SS_pp = nmp.sum(p * p) - n1 * m_p * m_p
b_1 = SS_pq / SS_pp
b_0 = m_q - b_1 * m_p
return (b_0, b_1)
def plot_regression_line(p, q, b):
mtplt.scatter(p, q, color = "m",
marker = "o", s = 30)
q_pred = b[0] + b[1] * p
mtplt.plot(p, q_pred, color = "g")
mtplt.xlabel('p')
mtplt.ylabel('q')
mtplt.show()
def main():
p = np.array([10, 11, 12, 13, 14, 15, 16, 17, 18, 19])
q = np.array([11, 13, 12, 15, 17, 18, 18, 19, 20, 22])
b = estimate_coeff(p, q)
print("Estimated coefficients are :\nb_0 = {} \
\nb_1 = {}".format(b[0], b[1]))
plot_regression_line(p, q, b)
if __name__ == "__main__":
main()

BCA, BIHE Davangere

 ARTIFICIAL INTELLIGENCE LAB

Output:
Estimated coefficients are :
b_0 = -0.4606060606060609
b_1 = 1.1696969696969697

10.Write a Python program to implement Stemming for a given sentence using NLTK

from nltk.stem import PorterStemmer

from nltk.tokenize import word_tokenize

ps = PorterStemmer()
words = ["program", "programs", "programmer", "programming", "programmers"]
for w in words:
print(w, " : ", ps.stem(w))

Output:
program : program
programs : program
programmer : program
programming : program
programmers : program

BCA, BIHE Davangere