SHAMBHUNATH INSTITUTE OF ENGINEERING &
TECHNOLOGY
Session - 2023-24
Department of Computer Science and Engineering
Year: 4th year Semester: 7th
ARTIFICIAL INTELLIGENCE Lab- KCS-751A
LAB MANUAL
Index
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-Puzzle 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 Monkey Banana Problem using
Python.
8 Write a Program to Implement N-Queens Problem using Python. #
Python program to solve N Queen
Experiment 01
1. Write a Program to Implement Breadth First Search using Python.
# Program to print BFS traversal
# from a given source vertex. BFS(int s) # traverses vertices reachable from s. from collections
import defaultdict
# This class represents a directed graph # using adjacency list representation class Graph:
# Constructor
def __init (self):
# default dictionary to store graph [Link] = defaultdict(list)
# function to add an edge to graph def addEdge(self,u,v):
[Link][u].append(v)
# Function to print a BFS of graph def BFS(self, s):
# Mark all the vertices as not visited visited = [False] * (max([Link]) + 1)
# Create a queue for BFS queue = []
# Mark the source node as # visited and enqueue it [Link](s) visited[s] = True
while queue:
# Dequeue a vertex from # queue and print it
s = [Link](0) print (s, end = " ")
# Get all adjacent vertices of the # dequeued vertex s. If a adjacent
# has not been visited, then mark it # visited and enqueue it
for i in [Link][s]:
if visited[i] == False: [Link](i) visited[i] = True
# Driver code
# Create a graph given in # the above diagram
g = Graph() [Link](0, 1)
[Link](0, 2)
[Link](1, 2)
[Link](2, 0)
[Link](2, 3)
[Link](3, 3)
print ("Following is Breadth First Traversal" " (starting from vertex 2)")
[Link](2)
Output:
Following is Breadth First
Traversal (starting from
vertex 2)
>3
20313
>
Experiment 02
2. Write a Program to Implement Depth First Search using Python.
# program to print DFS traversal # from a given given graph
from collections import defaultdict
# This class represents a directed graph using # adjacency list representation
class Graph:
# Constructor
def __init (self):
# default dictionary to store graph [Link] = defaultdict(list)
# function to add an edge to graph def addEdge(self, u, v):
[Link][u].append(v)
# A function used by DFS def DFSUtil(self, v, visited):
# Mark the current node as visited # and print it
[Link](v) print(v, end=' ')
# Recur for all the vertices # adjacent to this vertex
for neighbour in [Link][v]: if neighbour not in visited:
[Link](neighbour, visited)
# The function to do DFS traversal. It uses # recursive DFSUtil()
def DFS(self, v):
# Create a set to store visited vertices visited = set()
# Call the recursive helper function # to print DFS traversal [Link](v, visited)
# Driver code
# Create a graph given # in the above diagram
g = Graph() [Link](0, 1)
[Link](0, 2)
[Link](1, 2)
[Link](2, 0)
[Link](2, 3)
[Link](3, 3)
print("Following is DFS from (starting from vertex 2)") [Link](2)
Output:
Following is Depth First Traversal (starting from
vertex 2) 2 0 1 9 3
Experiment 03
3. Write a Program to Implement Tic-Tac-Toe game using Python.
# Tic-Tac-Toe Program using # random number in Python
# importing all necessary libraries import numpy as np
import random
from time import sleep
# Creates an empty board def create_board():
return([Link]([[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]))
# Check for empty places on board def possibilities(board):
l = []
for i in range(len(board)): for j in range(len(board)):
if board[i][j] == 0: [Link]((i, j))
return(l)
# Select a random place for the player def random_place(board, player):
selection = possibilities(board) current_loc = [Link](selection) board[current_loc] =
player return(board)
# Checks whether the player has three # of their marks in a horizontal row def
row_win(board, player):
for x in range(len(board)): win = True
for y in range(len(board)): if board[x, y] != player:
win = False continue
if win == True: return(win)
return(win)
# Checks whether the player has three # of their marks in a vertical row
def col_win(board, player): for x in range(len(board)):
win = True
for y in range(len(board)): if board[y][x] != player:
win = False continue
if win == True: return(win)
return(win)
# Checks whether the player has three # of their marks in a diagonal row
def diag_win(board, player): win = True
y=0
for x in range(len(board)): if board[x, x] != player:
win = False if win:
return win win = True if win:
for x in range(len(board)): y = len(board) - 1 - x
if board[x, y] != player: win = False
return win
# Evaluates whether there is # a winner or a tie
def evaluate(board): winner = 0
for player in [1, 2]:
if (row_win(board, player) or col_win(board,player) or diag_win(board,player)):
winner = player
if [Link](board != 0) and winner == 0: winner = -1
return winner
# Main function to start the game def play_game():
board, winner, counter = create_board(), 0, 1 print(board)
sleep(2)
while winner == 0: for player in [1, 2]:
board = random_place(board, player) print("Board after " + str(counter) + " move")
print(board)
sleep(2) counter += 1
winner = evaluate(board) if winner != 0:
break return(winner)
# Driver Code
print("Winner is: " + str(play_game()))
Output:
[[0 0 0]
[0 0 0]
[0 0 0]]
Board after 1 move
[[0 0 0]
[0 0 0]
[1 0 0]]
Board after 2 move
[[0 0 0]
[0 2 0]
[1 0 0]]
Board after 3 move
[[0 1 0]
[0 2 0]
[1 0 0]]
Board after 4 move
[[0 1 0]
[2 2 0]
[1 0 0]]
Board after 5 move
[[1 1 0]
[2 2 0]
[1 0 0]]
Board after 6 move
[[1 1 0]
[2 2 0]
[1 2 0]]
Board after 7 move
[[1 1 0]
[2 2 0]
[1 2 1]]
Board after 8 move
[[1 1 0]
[2 2 2]
[1 2 1]]
Winner is: 2
Experiment 04
4. Write a Program to Implement 8-Puzzle problem using Python
def solve(self, board): dict = {}
flatten = []
for i in range(len(board)): flatten += board[i]
flatten = tuple(flatten)
dict[flatten] = 0
if flatten == (0, 1, 2, 3, 4, 5, 6, 7, 8):
return 0
return self.get_paths(dict)
def get_paths(self, dict):
cnt = 0 while True:
current_nodes = [x for x in dict if dict[x] == cnt] if len(current_nodes) == 0:
return -1
for node in current_nodes: next_moves = self.find_next(node) for move in next_moves:
if move not in dict: dict[move] = cnt + 1
if move == (0, 1, 2, 3, 4, 5, 6, 7, 8):
return cnt + 1
cnt += 1
def find_next(self, node): moves = {
0: [1, 3],
1: [0, 2, 4],
2: [1, 5],
3: [0, 4, 6],
4: [1, 3, 5, 7],
5: [2, 4, 8],
6: [3, 7],
7: [4, 6, 8],
8: [5, 7],
}
results = []
pos_0 = [Link](0)
for move in moves[pos_0]:
new_node = list(node)
new_node[move], new_node[pos_0] = new_node[pos_0], new_node[move]
[Link](tuple(new_node))
return results ob = Solution() matrix = [
[3, 1, 2],
[4, 7, 5],
[6, 8, 0]
]
print([Link](matrix))
Input:
matrix = [ [3, 1, 2],
[4, 7, 5],
[6, 8, 0] ]
Output:
4
Experiment 05
5. Write a Program to Implement Water-Jug problem using Python
# dictionary elements with a default value.
from collections import defaultdict
# jug1 and jug2 contain the value
# for max capacity in respective jugs
# and aim is the amount of water to be measured. jug1, jug2, aim = 4, 3, 2
# Initialize dictionary with # default value as false.
visited = defaultdict(lambda: False)
# Recursive function which prints the # intermediate steps to reach the final # solution and
return boolean value
# (True if solution is possible, otherwise False). # amt1 and amt2 are the amount of water
present # in both jugs at a certain point of time.
def waterJugSolver(amt1, amt2):
# Checks for our goal and # returns true if achieved.
if (amt1 == aim and amt2 == 0) or (amt2 == aim and amt1 == 0): print(amt1, amt2)
return True
# Checks if we have already visited the
# combination or not. If not, then it proceeds further. if visited[(amt1, amt2)] == False:
print(amt1, amt2)
# Changes the boolean value of # the combination as it is visited. visited[(amt1, amt2)] = True
# Check for all the 6 possibilities and
# see if a solution is found in any one of them. 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 if the combination is
# already visited to avoid repetition otherwise # recursion will enter an infinite loop.
else:
return False
print("Steps: ")
# Call the function and pass the
# initial amount of water present in both jugs. waterJugSolver(0, 0)
Output:
Steps:
00
40
43
03
30
33
42
02
Experiment 06
6. Write a Program to Implement Travelling Salesman Problem using Python.
# program to implement traveling salesman # problem using naive approach.
from sys import maxsize
from itertools import permutations V = 4
# implementation of traveling Salesman Problem def travellingSalesmanProblem(graph, s):
# store all vertex apart from source vertex vertex = []
for i in range(V): if i != s:
[Link](i)
# store minimum weight min_path = maxsize
next_permutation=permutations(vertex) for i in next_permutation:
# store current Path weight(cost) current_pathweight = 0
# compute current path weight k = s
for j in i:
current_pathweight += graph[k][j] k = j
current_pathweight += graph[k][s]
# update minimum
min_path = min(min_path, current_pathweight)
return min_path # Driver Code
if name == " main ":
# matrix representation of graph
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
Write a Program to Implement Tower of Hanoi using Python.
# Recursive Python function to solve tower of hanoi
def TowerOfHanoi(n , from_rod, to_rod, aux_rod): if n == 1:
print("Move disk 1 from rod",from_rod,"to rod",to_rod) return
TowerOfHanoi(n-1, from_rod, aux_rod, to_rod) print("Move disk",n,"from rod",from_rod,"to
rod",to_rod) TowerOfHanoi(n-1, aux_rod, to_rod, from_rod)
# Driver code n = 4
TowerOfHanoi(n, 'A', 'C', 'B') # A, C, B are the name of rods
Output
Move disk 1 from rod A to rod B Move disk 2 from rod A to rod C Move disk 1 from rod
B to rod C Move disk 3 from rod A to rod B Move disk 1 from rod C to rod A Move disk 2
from rod C to rod B Move disk 1 from rod A to rod B Move disk 4 from rod A to rod C
Move disk 1 from rod B to rod C Move disk 2 from rod B to rod A Move disk 1 from rod
C to rod A Move disk 3 from rod B to rod C Move disk 1 from rod A to rod B Move disk
2 from rod A to rod C Move disk 1 from rod B to rod C Output:
Tower of Hanoi Solution for 4
disks: A: [4, 3, 2, 1] B: [] C: []
Move disk from rod A to rod
B A: [4, 3, 2] B: [1] C: []
Move disk from rod A to rod
C A: [4, 3] B: [1] C: [2]
Move disk from rod B to rod
C A: [4, 3] B: [] C: [2, 1]
Move disk from rod A to rod
B A: [4] B: [3] C: [2, 1]
Move disk from rod C to rod
A A: [4, 1] B: [3] C: [2]
Move disk from rod C to rod
B A: [4, 1] B: [3, 2] C: []
Move disk from rod A to rod
B A: [4] B: [3, 2, 1] C: []
Move disk from rod A to rod
C A: [] B: [3, 2, 1] C: [4]
Move disk from rod B to rod
C A: [] B: [3, 2] C: [4, 1]
Move disk from rod B to rod
A A: [2] B: [3] C: [4, 1]
Move disk from rod C to rod
A A: [2, 1] B: [3] C: [4]
Move disk from rod B to rod
C A: [2, 1] B: [] C: [4, 3]
Move disk from rod A to rod
B A: [2] B: [1] C: [4, 3]
Move disk from rod A to rod
C A: [] B: [1] C: [4, 3, 2]
Move disk from rod B to rod
C A: [] B: [] C: [4, 3, 2, 1]
Experiment 07
7. Write a Program to Implement Monkey Banana Problem using Python.
from poodle import Object, schedule from typing import Set
class Position(Object):
def str (self):
if not hasattr(self, "locname"): return "unknown"
return [Link]
class HasHeight(Object):
height: int
class HasPosition(Object):
at: Position
class Monkey(HasHeight, HasPosition): pass
class PalmTree(HasHeight, HasPosition):
def init (self, *args, **kwargs):
super(). init (*args, **kwargs)
[Link] = 2
class Box(HasHeight, HasPosition): pass
class Banana(HasHeight, HasPosition):
owner: Monkey
attached: PalmTree
class World(Object):
locations: Set[Position]
p1 = Position()
[Link] = "Position A"
p2 = Position()
[Link] = "Position B"
p3 = Position()
[Link] = "Position C"
w = World()
[Link](p1)
[Link](p2)
[Link](p3)
m = Monkey()
[Link] = 0 # ground
[Link] = p1
box = Box()
[Link] = 2
[Link] = p2
p = PalmTree()
[Link] = p3
b = Banana()
[Link] = p
def go(monkey: Monkey, where: Position):
assert where in [Link]
assert [Link] < 1, "Monkey can only move while on the ground"
[Link] = where
return f"Monkey moved to {where}"
def push(monkey: Monkey, box: Box, where: Position):
assert [Link] == [Link]
assert where in [Link]
assert [Link] < 1, "Monkey can only move the box while on the ground"
[Link] = where
[Link] = where
return f"Monkey moved box to {where}"
def climb_up(monkey: Monkey, box: Box):
assert [Link] == [Link]
[Link] += [Link]
return "Monkey climbs the box"
def grasp(monkey: Monkey, banana: Banana):
assert [Link] == [Link]
assert [Link] == [Link]
[Link] = monkey
return "Monkey takes the banana"
def infer_owner_at(palmtree: PalmTree, banana: Banana):
assert [Link] == palmtree
[Link] = [Link]
return "Remembered that if banana is on palm tree, its location is where palm tree is"
def infer_banana_height(palmtree: PalmTree, banana: Banana):
assert [Link] == palmtree
[Link] = [Link]
return "Remembered that if banana is on the tree, its height equals tree's height"
print('\n'.join(x() for x in schedule(
print('\n'.join(x() for x in schedule(
[go, push, climb_up, grasp, infer_banana_height, infer_owner_at],
[w,p1,p2,p3,m,box,p,b],
goal=lambda: [Link] == m)))
Result:
$ pip install poodle
$ python ./[Link]
Monkey moved to Position B
Remembered that if banana is on the tree, its height equals tree's height
Remembered that if banana is on palm tree, its location is where palm tree is
Monkey moved box to Position C
Monkey climbs the box
Monkey takes the banana
Experiment 08
8. Write a Program to Implement N-Queens Problem using Python. # Python program to
solve N Queen
# Problem using backtracking
global N N = 4
def printSolution(board): for i in range(N):
for j in range(N): print board[i][j],
print
# A utility function to check if a queen can
# be placed on board[row][col]. Note that this # function is called when "col" queens are
# already placed in columns from 0 to col -1. # So we need to check only left side for
# attacking queens
def isSafe(board, row, col):
# Check this row on left side for i in range(col):
if board[row][i] == 1: return False
# Check upper diagonal on left side
for i, j in zip(range(row, -1, -1), range(col, -1, -1)): if board[i][j] == 1:
return False
# Check lower diagonal on left side
for i, j in zip(range(row, N, 1), range(col, -1, -1)): if board[i][j] == 1:
return False return True
def solveNQUtil(board, col):
# base case: If all queens are placed # then return true
if col >= N: return True
# Consider this column and try placing # this queen in all rows one by one
for i in range(N):
if isSafe(board, i, col):
# Place this queen in board[i][col] board[i][col] = 1
# recur to place rest of the queens
if solveNQUtil(board, col + 1) == True: return True
# If placing queen in board[i][col # doesn't lead to a solution, then # queen from board[i][col]
board[i][col] = 0
# if the queen can not be placed in any row in # this colum col then return false
return False
# This function solves the N Queen problem using # Backtracking. It mainly uses solveNQUtil()
to
# solve the problem. It returns false if queens # cannot be placed, otherwise return true and #
placement of queens in the form of 1s.
# note that there may be more than one
# solutions, this function prints one of the # feasible solutions.
def solveNQ():
board = [ [0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0]
]
if solveNQUtil(board, 0) == False: print "Solution does not exist" return False
printSolution(board) return True
# driver program to test above function solveNQ()
Output:
0010
1000
0001
0100