lOMoARcPSD|39 351231

VISVESVARAYA
COLLEGE OF ENGINEERING AND TECHNOLOGY

LABORATORY MANUAL

&

ARTIFICIAL INTELLIGENCE LAB

III-B.TECH-2nd SEM

Department of CSE 1
 lOMoARcPSD|39 351231

INSTITUTE VISION & MISSION

VISION

To emerge as the best among the institutes of technology and research in the country dedicated to
the cause of promoting quality technical education.

MISSION

Empowerment of women engineers and technocrats with emphasis on academic excellence, life
skills and human values.

DEPARTMENT VISION & MISSION

VISION

Produce competent technocrats, researchers, and entrepreneurs in Artificial Intelligence &

Machine Learning to build an ecosystem that significantly contributes to the nation.

MISSION

M1: To impart skills through various learning methodologies and value-added courses to be
technically competent.

M2: To build the research culture through participations in innovative projects and publications

M3: To inculcate ethics, leadership skills, life skills and lifelong learning

M4: To expose the students to real time environment by internships and mentorships through
collaborations with industries and premier institutions.
 lOMoARcPSD|39 351231

Program Outcomes (POs)

1. Engineering Knowledge: Apply the knowledge of mathematics, science, engineering

fundamentals and an engineering specialization to the solution of complex engineering
problems.
2. Problem Analysis: Identify, formulate, review research literature, and analyze complex
engineering problems reaching substantiated conclusions using first principles of mathematics,
natural sciences, and engineering sciences.
3. Design / Development of solutions: Design solutions for complex engineering problems and
design system components or processes that meet the specified needs with appropriate
consideration for the public health and safety, and the cultural, societal, and environmental
considerations.
4. Conduct investigations of complex problems: Use research-based knowledge and research
methods including design of experiments, analysis and interpretation of data, and synthesis of
the information to provide valid conclusions.
5. Modern tool usage: Create, select, and apply appropriate techniques, resources, and modern
engineering and IT tools including prediction and modeling to complex engineering activities
with an understanding of the limitations.
6. The engineer and society: Apply reasoning informed by the contextual knowledge to assess
societal, health, safety, legal and cultural issues and the consequent responsibilities relevant to
the professional engineering practice.
7. Environment and sustainability: Understand the impact of the professional engineering
solutions in societal and environmental contexts, and demonstrate the knowledge of, and need
for sustainable development.
8. Ethics: Apply ethical principles and commit to professional ethics and responsibilities and
norms of the engineering practice.
9. Individual and team work: Function effectively as an individual and as a member or leader
in diverse teams, and in multidisciplinary settings.
10. Communication: Communicate effectively on complex engineering activities with the
engineering community and with society at large, such as, being able to comprehend and write
effective reports and design documentation, make effective presentations, and give and receive
clear instructions.
11. Project management and finance: Demonstrate knowledge and understanding of the
engineering management principles and apply these to one’s own work, as a member and
leader in a team, to manage projects and in multidisciplinary environments.
12. Life-long learning: Recognize the need for and have the preparation and ability to engage in
independent and lifelong learning in the broadest context of technological change.

Department of CSE 3
 lOMoARcPSD|39 351231

Program Educational Objectives (PEOs)

PEO-1: Adapt emerging technologies to contribute to the technical innovations for the progressive
development in their respective fields.

PEO-2: Productively engage in multidisciplinary research areas by applying the basic principles
of engineering sciences.

PEO-3: Demonstrate strong technical skills to bring out novel designs/products to address social
& environmental issues.

PEO-4: Exhibit professional attitude, teamwork and practice code of ethics.

Program Specific Objectives (PSOs)

PSO 1: Ability to apply learned skills to build optimized solutions pertaining to Computer &
Communication Systems, Data Processing and Artificial Intelligence.

PSO 2: Employ standard strategies and practices in project development using FOSS (Free Open-
Source Software)

Department of CSE 4
 lOMoARcPSD|39 351231

Course Outcomes:

CO NO. Course Outcomes Blooms level

Apply basic principles of AI in solutions that require problem Apply
C326.1
solving, knowledge representation, and learning
Show sensitivity to linguistic phenomena and an ability to model Apply
C326.2
them with formal grammars.

CO-PO Mapping:

CO/PO PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2
C326.1 3 3 2 3 3

C326.2 3 3 3 3 3 2 3 3

C326.3 3 3 3 3 3 2 3 3

C326.4 3 3 3 3 3 2 3 3

Mean 3 3 2.25 2.25 2.75 0.5 1 3 3

Department of CSE 5
 lOMoARcPSD|39 351231

CONTENTS

S. No Contents Page No
1 Objectives
2 Syllabus
3 Lab Cycles
4 Instructions to students
5 Program Development Environment
6 Programs
7 Other Programs
8 Viva Questions with Solutions

Department of CSE 6
 lOMoARcPSD|39 351231

OBJECTIVES

Students are able to:

 Become familiar with basic principles of AI toward problem solving, knowledge

representation, and learning.
 Knowledge on basic Language processing features, design an innovative application
using NLP components
 Apply basic principles of AI in solutions that require problem solving, Knowledge
representation, and learning.
 Show sensitivity to linguistic phenomena and an ability to model them with formal
grammars.

Department of CSE 7
 lOMoARcPSD|39 351231

SYLLABUS

List of Experiments (AI)

Write a Program to Implement the following using Python.
1. Breadth First Search
2. Depth First Search
3. Tic-Tac-Toe game
4. 8-Puzzle problem
5. Water-Jug problem
6. Travelling Salesman Problem
7. Tower of Hanoi
8. Monkey Banana Problem
9. Alpha-Beta Pruning
10. 8-Queens Problem
 lOMoARcPSD|39 351231

INSTRUCTIONS TO STUDENTS

1. On entering the lab, you should make an entry in the log book available with the details
regarding student name, roll no, system no and signature.

2. You must bring Observation notebook for every lab session. Observation book should be
duly signed by your faculty, failing which your report will not be graded. You must
complete all experimental programs allotted during the session.

3. You should shut down the system properly and leave the lab neat and tidy.
GRADING :

 The overall lab examination is for 100 marks. In those 75 marks for External
examination at the endof the year and remaining 25 marks will be awarded for the
internal examinations and Continuous evaluation.

 Lab internal examination will carry 10 marks and Continuous evaluation will carry
remaining 15marks for each experiment.

 In Continuous evaluation:

A. Experimentation 5 marks

B. Viva – voce 5 marks

C. Record 5 marks

Department of CSE 10
 Program Development Environment

In today’s world, a computer is used to solve various types of problems, because it takes very less
time as compared to a human being.
The following steps are performed while solving a problem:

Define the problem

Outline the solution

Develop the outline into an algorithm

Test the algorithm into a programming language
Code the algorithm into a programming language.
Run the program on the computer

Document and maintain the program

R22 B.Tech. CSE Syllabus JNTU Hyderabad

CS605PC: ARTIFICIAL INTELLIGENCE LABB.Tech. III Year II Sem.

Course Objectives:

 Become familiar with basic principles of AI toward problem solving, knowledge representation, and
learning.

Course Outcomes:

 Apply basic principles of AI in solutions that require problem solving, knowledge representation, and
learning.

LIST OF EXPERIMENTS

Write a Program to Implement the following using Python.

1. Breadth First Search

2. Depth First Search
3. Tic-Tac-Toe game
4. 8-Puzzle problem
5. Water-Jug problem
6. Travelling Salesman Problem
7. Tower of Hanoi
8. Monkey Banana Problem
9. Alpha-Beta Pruning
10. 8-Queens Problem

TEXT BOOK:

1. Artificial Intelligence a Modern Approach, Third Edition, Stuart Russell and Peter Norvig,
Pearson Education.

REFERENCE BOOKS:

1. Artificial Intelligence, 3rd Edn, E. Rich and K. Knight (TMH)

2. Artificial Intelligence, 3rd Edn., Patrick Henny Winston, Pearson Education.
Artificial Intelligence, Shivani Goel, Pearson Education
AI LAB PROGRAMS
 1. Write a Program to Implement Breadth First Search Problem using Python.

# Input Graph
graph = {
'A' : ['B','C'],
'B' : ['A','C','D'],
'C' : ['A','B','E'],
'D' : ['B','E'],
'E' : ['C','D']
}
# To store visited nodes.
visitedNodes = []
# To store nodes in queue
queueNodes = []
# function
def bfs(visitedNodes, graph, snode):
visitedNodes.append(snode)
queueNodes.append(snode)
print()
print("RESULT :")
while queueNodes:
s = queueNodes.pop(0)
print (s, end = " ")
for neighbour in graph[s]:
if neighbour not in visitedNodes:
visitedNodes.append(neighbour)
queueNodes.append(neighbour)

# Main Code
snode = input("Enter Starting Node(A, B, C, D, or E) :").upper()
# calling bfs function
bfs(visitedNodes, graph, snode)

Output:
Sample Output 1:
-------------------
Enter Starting Node(A, B, C, D, or E) :A

RESULT :
ABCDE
------------------------------------------------------------------
Sample Output 2:
-------------------
Enter Starting Node(A, B, C, D, or E) :B

RESULT :
BACDE

# Input Graph
graph = {
'A' : ['B','C'],
'B' : ['A','C','D'],
'C' : ['A','B','E'],
'D' : ['B','E'],
'E' : ['C','D']
}
2. Write a Program to Implement Depth First Search Problem using Python.

# Set used to store visited nodes.

visitedNodes = list()
# function
def dfs(visitedNodes, graph, node):
if node not in visitedNodes:
print (node,end=" ")
visitedNodes.append(node)
for neighbour in graph[node]:
dfs(visitedNodes, graph, neighbour)
# Driver Code
snode = input("Enter Starting Node(A, B, C, D, or E) :").upper()
# calling bfs function
print("RESULT :")
print("-"*20)
dfs(visitedNodes, graph, snode)

Output:
Sample Output 1:

Enter Starting Node(A, B, C, D, or E) :A

RESULT :
--------------------
ABCED

------------------------------------------------------------------
Sample Output 2:

Enter Starting Node(A, B, C, D, or E) :B

RESULT :
--------------------
BACED
3. Write a Program to Implement Tic-Tac-Toe Game Problem using Python.

# Tuple to store winning positions.

win_positions = (
(0, 1, 2), (3, 4, 5), (6, 7, 8),
(0, 3, 6), (1, 4, 7), (2, 5, 8),
(0, 4, 8), (2, 4, 6)
)

def game(player):
# diplay current mesh
print("\n", " | ".join(mesh[:3]))
print("---+---+---")
print("", " | ".join(mesh[3:6]))
print("---+---+---")
print("", " | ".join(mesh[6:]))

# Loop until player valid input cell number.

while True:
try:
ch = int(input(f"Enter player {player}'s choice : "))
if str(ch) not in mesh:
raise ValueError
mesh[ch-1] = player
break
except ValueError:
print("Invalid position number.")

# Return winning positions if player wins, else None.

for wp in win_positions:
if all(mesh[pos] == player for pos in wp):
return wp
return None

player1 = "X"
player2 = "O"
player = player1
mesh = list("123456789")

for i in range(9):
won = game(player)
if won:
print("\n", " | ".join(mesh[:3]))
print("---+---+---")
print("", " | ".join(mesh[3:6]))
print("---+---+---")
print("", " | ".join(mesh[6:]))
 print(f"*** Player {player} won! ***")
break
player = player1 if player == player2 else player2
else:
# 9 moves without a win is a draw.
print("Game ends in a draw.")

Output:
Sample Output:
1|2|3
---+---+---
4|5|6
---+---+---
7|8|9
Enter player X's choice : 5

1|2|3
---+---+---
4|X|6
---+---+---
7|8|9
Enter player O's choice : 3

1|2|O
---+---+---
4|X|6
---+---+---
7|8|9
Enter player X's choice : 1

X|2|O
---+---+---
4|X|6
---+---+---
7|8|9
Enter player O's choice : 6

X|2|O
---+---+---
4|X|O
---+---+---
7|8|9
Enter player X's choice : 9

X|2|O
---+---+---
4|X|O
---+---+---
7|8|X
*** Player X won! ***
4. Write a Program to Implement 8-Puzzle game Problem using Python.

from collections import deque

def bfs(start_state):
target = [1, 2, 3, 4, 5, 6, 7, 8 , 0]
dq = deque([start_state])
visited = {tuple(start_state): None}

while dq:
state = dq.popleft()
if state == target:
path = []
while state:
path.append(state)
state = visited[tuple(state)]
return path[::-1]

zero = state.index(0)
row, col = divmod(zero, 3)
for move in (-3, 3, -1, 1):
new_row, new_col = divmod(zero + move, 3)
if 0 <= new_row < 3 and 0 <= new_col < 3 and abs(row - new_row) + abs(col - new_col) ==
1:
neighbor = state[:]
neighbor[zero], neighbor[zero + move] = neighbor[zero + move], neighbor[zero]
if tuple(neighbor) not in visited:
visited[tuple(neighbor)] = state
dq.append(neighbor)

def printSolution(path):
for state in path:
print("\n".join(' '.join(map(str, state[i:i+3])) for i in range(0, 9, 3)), end="\n-----\n")

# Example Usage
startState = [1, 3, 0 , 6, 8, 4, 7, 5, 2]
solution = bfs(startState)
if solution:
printSolution(solution)
print(f"Solved in {len(solution) - 1} moves.")
else:
print("No solution found.")
Output:
130
684
752
-----
134
680
752
-----
134
682
750
-----
134
682
705
-----
.
.
.
-----
123
450
786
-----
123
456
780
-----
Solved in 20 moves.
5. Write a Program to Implement Water-Jug Game Problem using Python.

# jug1 and jug2 contain the value

jug1, jug2, goal = 4, 3, 2

# Initialize a 2D list for visited states

# The list will have dimensions (jug1+1) x (jug2+1) to cover all possible states
visited = [[False for _ in range(jug2 + 1)] for _ in range(jug1 + 1)]

def waterJug(vol1, vol2):

# Check if we reached the goal state
if (vol1 == goal and vol2 == 0) or (vol2 == goal and vol1 == 0):
print(vol1,"\t", vol2)
print("Solution Found")
return True

# If this state has been visited, return False

if visited[vol1][vol2]:
return False
# Mark this state as visited
visited[vol1][vol2] = True
# Print the current state
print(vol1,"\t", vol2)
# Try all possible moves:
return (
waterJug(0, vol2) or # Empty jug1
waterJug(vol1, 0) or # Empty jug2
waterJug(jug1, vol2) or # Fill jug1
waterJug(vol1, jug2) or # Fill jug2
waterJug(vol1 + min(vol2, (jug1 - vol1)), vol2 - min(vol2, (jug1 - vol1))) or # Pour water from
jug2 to jug1
waterJug(vol1 - min(vol1, (jug2 - vol2)), vol2 + min(vol1, (jug2 - vol2))) # Pour water from
jug1 to jug2
)

print("Steps: ")
print("Jug1 \t Jug2 ")
print("----- \t ------")
waterJug(0, 0)
Output:
Steps:
Jug1 Jug2
----- ------
0 0
4 0
4 3
0 3
3 0
3 3
4 2
0 2
Solution Found
6. Write a Program to Implement Travelling Salesman Problem using Python.

from collections import deque

def tsp_bfs(graph):

n = len(graph) # Number of cities

startCity = 0 # Starting city
min_cost = float('inf') # Initialize minimum cost as infinity
opt_path = [] # To store the optimal path

# Queue for BFS: Each element is (cur_path, cur_cost)

dq = deque([([startCity], 0)])

print("Path Traversal:")

while dq:
cur_path, cur_cost = dq.popleft()
cur_city = cur_path[-1]

# Print the current path and cost

print(f"Current Path: {cur_path}, Current Cost: {cur_cost}")

# If all cities are visited and we are back at the startCity

if len(cur_path) == n and cur_path[0] == startCity:
total_cost = cur_cost + graph[cur_city][startCity]
if total_cost < min_cost:
min_cost = total_cost
opt_path = cur_path + [startCity]
continue

# Explore all neighboring cities (add in BFS manner)

for next_city in range(n):
if next_city not in cur_path: # Visit unvisited cities
new_path = cur_path + [next_city]
new_cost = cur_cost + graph[cur_city][next_city]
dq.append((new_path, new_cost))

return min_cost, opt_path

# Example graph as a 2D adjacency matrix

graph = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
# Solve TSP using BFS
min_cost, opt_path = tsp_bfs(graph)

print("\nOptimal Solution:")
print(f"Minimum cost: {min_cost}")
print(f"Optimal path: {opt_path}")

Output:
Path Traversal:
Current Path: [0], Current Cost: 0
Current Path: [0, 1], Current Cost: 10
Current Path: [0, 2], Current Cost: 15
Current Path: [0, 3], Current Cost: 20
Current Path: [0, 1, 2], Current Cost: 45
Current Path: [0, 1, 3], Current Cost: 35
Current Path: [0, 2, 1], Current Cost: 50
Current Path: [0, 2, 3], Current Cost: 45
Current Path: [0, 3, 1], Current Cost: 45
Current Path: [0, 3, 2], Current Cost: 50
Current Path: [0, 1, 2, 3], Current Cost: 75
Current Path: [0, 1, 3, 2], Current Cost: 65
Current Path: [0, 2, 1, 3], Current Cost: 75
Current Path: [0, 2, 3, 1], Current Cost: 70
Current Path: [0, 3, 1, 2], Current Cost: 80
Current Path: [0, 3, 2, 1], Current Cost: 85

Optimal Solution:
Minimum cost: 80
Optimal path: [0, 1, 3, 2, 0]
7. Write a Program to Implement Tower of Hanoi Problem using Python.

def tower_of_hanoi(num, source, aux, target):

"""
num (int): Number of disks.
source (str): The name of the source tower.
aux (str): The name of the auxiliary tower.
target (str): The name of the target tower.
"""
if num == 1:
print(f"Move disk 1 from {source} to {target}")
return
# Move num-1 disks from source to auxiliary
tower_of_hanoi(num - 1, source, target, aux)
print(f"Move disk {num} from {source} to {target}")
# Move the num-1 disks from auxiliary to target
tower_of_hanoi(num - 1, aux, source, target)

Output:
# Example usage
num_disks = 3
tower_of_hanoi(num_disks, "A", "B", "C")

Move disk 1 from A to C

Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
8. Write a Program to Implement Monkey Banana Problem using Python.

def monkey_banana_problem():
# Initial state
initial_state = ('Far-Chair', 'Chair-Not-Under-Banana', 'Off-Chair', 'Empty') # (Monkey's
Location, Monkey's Position on Chair, Chair's Location, Monkey's Status)
print(f"\n Initial state is {initial_state}")
goal_state = ('Near-Chair', 'Chair-Under-Banana', 'On-Chair', 'Holding') # The goal state when
the monkey has the banana

# Possible actions and their effects

actions = {
"Move to Chair": lambda state: ('Near-Chair', state[1], state[2], state[3]) if state[0] != 'Near-
Chair' else None,
"Push Chair under Banana": lambda state: ('Near-Chair', 'Chair-Under-Banana', state[2],
state[3]) if state[0] == 'Near-Chair' and state[1] != 'Chair-Under-Banana' else None,
"Climb Chair": lambda state: ('Near-Chair', 'Chair-Under-Banana', 'On-Chair', state[3]) if
state[0] == 'Near-Chair' and state[1] == 'Chair-Under-Banana' and state[2] != 'On-Chair' else
None,
"Grasp Banana": lambda state: ('Near-Chair', 'Chair-Under-Banana', 'On-Chair', 'Holding') if
state[0] == 'Near-Chair' and state[1] == 'Chair-Under-Banana' and state[2] == 'On-Chair' and
state[3] !='Holding' else None
}

# BFS to explore states

from collections import deque
dq = deque([(initial_state, [])]) # Each element is (current_state, actions_taken)
visited = set()

while dq:
current_state, actions_taken = dq.popleft()

# Check if we've reached the goal

if current_state == goal_state:
print("\nSolution Found!")
print("Actions to achieve goal:")
for action in actions_taken:
print(action)
print(f"Final State: {current_state}")
return

# Mark the current state as visited

if current_state in visited:
continue
visited.add(current_state)
 # Try all possible actions
for action_name, action_func in actions.items():
next_state = action_func(current_state)
if next_state and (next_state not in visited):
dq.append((next_state, actions_taken + [f"Action: {action_name}, Resulting State:
{next_state}"]))

print("No solution found.")

# Run the program

monkey_banana_problem()

Output:
Initial state is ('Far-Chair', 'Chair-Not-Under-Banana', 'Off-Chair', 'Empty')

Solution Found!
Actions to achieve goal:
Action: Move to Chair, Resulting State: ('Near-Chair', 'Chair-Not-Under-Banana', 'Off-Chair',
'Empty')
Action: Push Chair under Banana, Resulting State: ('Near-Chair', 'Chair-Under-Banana', 'Off-
Chair', 'Empty')
Action: Climb Chair, Resulting State: ('Near-Chair', 'Chair-Under-Banana', 'On-Chair', 'Empty')
Action: Grasp Banana, Resulting State: ('Near-Chair', 'Chair-Under-Banana', 'On-Chair', 'Holding')
Final State: ('Near-Chair', 'Chair-Under-Banana', 'On-Chair', 'Holding')
9. Write a Program to Implement Alpha- Beta Problem using Python.

Alpha Beta Pruning :

-------------------
depth (int): Current depth in the game tree.
node_index (int): Index of the current node in the values array.
maximizing_player (bool): True if the current player is maximizing, False otherwise.
values (list): List of leaf node values.
alpha (float): Best value for the maximizing player.
beta (float): Best value for the minimizing player.

Returns:
int: The optimal value for the current player.
"""
import math

def alpha_beta_pruning(depth, node_index, maximizing_player, values, alpha, beta):

# Base case: leaf node
if depth == 0 or node_index >= len(values):
return values[node_index]

if maximizing_player:
max_eval = -math.inf
for i in range(2): # Each node has two children
eval = alpha_beta_pruning(depth - 1, node_index * 2 + i, False, values, alpha, beta)
max_eval = max(max_eval, eval)
alpha = max(alpha, eval)
if beta <= alpha:
break # Beta cutoff
return max_eval
else:
min_eval = math.inf
for i in range(2): # Each node has two children
eval = alpha_beta_pruning(depth - 1, node_index * 2 + i, True, values, alpha, beta)
min_eval = min(min_eval, eval)
beta = min(beta, eval)
if beta <= alpha:
break # Alpha cutoff
return min_eval
# Example usage
if __name__ == "__main__":
# Leaf node values for a complete binary tree
values = [3, 5, 6, 9, 1, 2, 0, -1]
depth = 3 # Height of the tree
optimal_value = alpha_beta_pruning(depth, 0, True, values, -math.inf, math.inf)
print(f"The optimal value is: {optimal_value}")
Output:
The optimal value is: 5
10. Write a Program to Implement 8-Queens Problem using Python.

def printSolution(board):
"""Print the chessboard configuration."""
for row in board:
print(" ".join("Q" if col else "." for col in row))
print("\n")

def isSafe(board, row, col, n):

"""Check if placing a queen at board[row][col] is safe."""
# Check column
for i in range(row):
if board[i][col]:
return False

# Check upper-left diagonal

i, j = row, col
while i >= 0 and j >= 0:
if board[i][j]:
return False
i -= 1
j -= 1

# Check upper-right diagonal

i, j = row, col
while i >= 0 and j < n:
if board[i][j]:
return False
i -= 1
j += 1

return True

def solveNQueens(board, row, n):

"""Use backtracking to solve the N-Queens problem."""
if row == n:
printSolution(board)
return True

result = False
for col in range(n):
if isSafe(board, row, col, n):
# Place the queen
board[row][col] = 1
# Recur to place the rest of the queens
result = solveNQueens(board, row + 1, n) or result
 # Backtrack
board[row][col] = 0

return result

def nQueens(n):
"""Driver function to solve the N-Queens problem."""
board = [[0] * n for _ in range(n)]
if not solveNQueens(board, 0, n):
print("No solution exists.")
else:
print("Solutions printed above.")
Output:
# Solve the 8-Queens problem
nQueens(8)

Q.......
....Q...
.......Q
.....Q..
..Q.....
......Q.
.Q......
...Q....

Q.......
.....Q..
.......Q
..Q.....
......Q.
...Q....
.Q......
....Q...

.
.

.......Q
...Q....
Q.......
..Q.....
.....Q..
.Q......
......Q.
....Q...

Solutions printed above.