Index

P. No.
S.No. Program
(a). Write a python program to print the multiplication table for the given
1.
number?
(b). Write a python program to check whether the given number is prime or
not?
(c). Write a python program to find factorial of the given number?
(a). Write a python program to implement list operations (Nested List,
2.
Length, Concatenation,Membership,Iteration,Indexing and Slicing)?
(b). Write a python program to implement list operations (add, append,
extend & delete)
3. Write a python program to Illustrate Different Set Operations?

4. Write a python program to implement simple Chatbot?

5. Write a python program to implement Breadth first search Traversal?

6. Write a program to inrplement Depth First Search Traversal.

7. Write a prcgram to implernent Water Jug problem.

8. Write a Program to lmplernent Tic-Tac-Toe game using python.

9. Write a python program to implement k-nearest neighbor algorithm.

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

11. Write a program to implement travelling salesman problem using python

12. Write a program to implement regression algorithm using python

13. write a python program to implement random forest algorithm

14. Write a program to implement tower of hanoi using python.

15. Write a program to implement monkey banana problem using python

16. Write a Program to Implement Alpha-Beta pruning using python

17. Write a program to implement 8 queens problem using python

1
1(a). Write a python program to print the multiplication table for the given number?

Code:

# Python program to find the multiplication table (from 1 to 10) of a number input by the user

# take input from the user

num = int(input("Display multiplication table of? "))

# use for loop to iterate 10 times for i in range(1,11):

for i in range(1,11):
print(num,'x',i,'=',num*i)

Output:
Display multiplication table of? 5
5x1=5
5 x 2 = 10
5 x 3 = 15
5 x 4 = 20
5 x 5 = 25
5 x 6 = 30
5 x 7 = 35
5 x 8 = 40
5 x 9 = 45
5 x 10 = 50

2
1(b). Write a python program to check whether the given number is prime or not?

Code:
# Python program to check if the input number is prime or not
#num = 407

# take input from the user

num = int(input("Enter a number: "))
temp=2;
# prime numbers are greater than 1 if num > 1:
rem=1

for i in range(2,num):
rem=num%i
if rem == 0:
temp=temp+1
if temp==2:
print(num,"is a prime number")
else:
print(num,"is not a prime number")

Output:

Enter a number: 5

5 is a prime number

3
1(c). Write a python program to find factorial of the given number?

Code:

def recur_factorial(n):

"""Function to return the factorial

of a number using recursion"""

if n == 1:

return n

else:

return n*recur_factorial(n-1)

# Change this value for a different result #num = 5

# uncomment to take input from the user num = int(input("Enter a number: "))
# check is the number is negative
num=int(input("Enter a number: "))
if num < 0:

print("Sorry, factorial does not exist for negative numbers")

elif num == 0:

print("The factorial of 0 is 1")

else:

print("The factorial of",num,"is",recur_factorial(num))

Output:

Enter a number: 5

The factorial of 5 is 120

4
2. (a) Write a python program to implement list operations (Nested List,
Length, Concatenation, Membership, Iteration, Indexing and Slicing)?

Code:
my_list = ['p','r','o','b','e']
# Output: p
print(my_list[0])
print("Length",my_list,":",len(my_list))
# Output: o
print(my_list[2])

# Output: e
print(my_list[4])

# Error! Only integer can be used for indexing #my_list[4.2]

# Nested List
n_list = [[1,3,5,7], [2,4,6,8,10]]

# Nested indexing
# Output: 3
print(n_list[0][1])

# Output: 8
print(n_list[1][3])

# Nested List2

n_list2 = ["Happy", [2,0,1,5]]

# Nested indexing
# Output: a
print(n_list2[0][1])

# Output: 5
print(n_list2[1][3])
concat1=[1,3,5]
concat2=[7,8,9]
print("Concatenation:",concat1,concat2,":",concat1+concat2)
repetion_string="Hello"
print("Repetition:",repetion_string,repetion_string * 4)

Output:
p
Length ['p', 'r', 'o', 'b', 'e']: 5
o
e
3
8
a
5

5
Concatenation: [1, 3, 5] [7, 8, 9] : [1, 3, 5, 7, 8, 9]
Repetition: Hello HelloHelloHelloHello

6
2 (b)Write a python program to implement list operations (add, append, extend
& delete)

Code:

myList = ["Earth", "revolves", "around", "Sun"]

print(myList)

print(len(myList))

print(myList[0])

print(myList[3])

#Slice elements from a list

print(myList[1:3])

#Use negative index

print(myList[-1])

#print(myList[4])

#add element to a list

myList.insert(0,"The")

print(myList)

print(len(myList))

myList.insert(4,"the")

print(myList)

#append an element to a list

myList.append("continuously")

print(myList)
print(len(myList))

#When use extend the argument should be another list #the elements of that list will
be added #to the current list as individual elements

myList.extend(["for", "sure"])

print(myList)

7
print(len(myList))

#you can append a sublist to the current list using append

myList.append(["The","earth","rotates"])

print(myList)

print(len(myList))

#delete a element in the list using element

myList.remove("The")

#delete a element in the list using index

myList.remove(myList[3])

print(myList)

Output

['Earth', 'revolves', 'around', 'Sun']

4
Earth
Sun
['revolves', 'around']

Sun
['The', 'Earth', 'revolves', 'around', 'Sun']
5
['The', 'Earth', 'revolves', 'around', 'the', 'Sun']
['The', 'Earth', 'revolves', 'around', 'the', 'Sun', 'continuously'] 7
['The', 'Earth', 'revolves', 'around', 'the', 'Sun', 'continuously', 'for', 'sure'] 9
['The', 'Earth', 'revolves', 'around', 'the', 'Sun', 'continuously', 'for', 'sure', ['The',
'earth', 'rotates']]
10

['Earth', 'revolves', 'around', 'Sun', 'continuously', 'for', 'sure', ['The', 'earth',

'rotates']]

8
3 Write a python program to Illustrate Different Set Operations?
Code:

# Program to perform different set operations like in

mathematics
# define three sets
E = {0, 2, 4, 6, 8};
N = {1, 2, 3, 4, 5};
# set union
print("Union of E and N is",E | N)
# set intersection
print("Intersection of E and N is",E & N)
# set difference
print("Difference of E and N is",E - N)
# set symmetric difference
print("Symmetric difference of E and N is",E ^ N)

Output:

Union of E and N is {0, 1, 2, 3, 4, 5, 6, 8}

Intersection of E and N is {2, 4}

Difference of E and N is {0, 8, 6}

Symmetric difference of E and N is {0, 1, 3, 5, 6, 8}

9
4. Write a python program to implement simple Chatbot?
Code:
print("Simple Question and Answering Program")
print("=====================================")
print(" You may ask any one of these questions")
print("Hi")
print("How are you?")
print("Are you working?")
print("What is your name?")
print("what did you do yesterday?")
print("Quit")
while True:
question = input("Enter one question from above list:")
question = question.lower()
if question in ['hi']:
print("Hello")
elif question in ['how are you?','how do you do?']:
print("I am fine")
elif question in ['are you working?','are you doing any
job?']:
print("yes. I'am working in KLU")
elif question in ['what is your name?']:
print("My name is Emilia")
name=input("Enter your name?")
print("Nice name and Nice meeting you",name)
elif question in ['what did you do yesterday?']:
print("I saw Bahubali 5 times")
elif question in ['quit']:
break

10
else:
print("I don't understand what you said")

Output:

Simple Question and Answering Program

==============================
You may ask any one of these questions
Hi
How are you?

Are you working?

What is your name?
what did you do yesterday?
Quit
Enter one question from above list:hi
Hello

Enter one question from above list:how are you?

I am fine
Enter one question from above list:are you working?
yes. I'am working in KLU
Enter one question from above list:what is your name?
My name is Emilia

Enter your name?sachin

Nice name and Nice meeting you sachin
Enter one question from above list:quit

11
5.Write a python program to implement Breadth first search Traversal?

Code:
graph = {
'A' : ['B','C'],
'B' : ['D', 'E'],
'C' : ['F'],
'D' : [],
'E' : ['F'],
'F' : []
}
visited = [] # List to keep track of visited nodes.
queue = [] #Initialize a queue
def bfs(visited, graph, node):
visited.append(node)
queue.append(node)
while queue:
s = queue.pop(0)
print (s, end = " ")
for neighbour in graph[s]:
if neighbour not in visited:
visited.append(neighbour)
queue.append(neighbour)
# Driver Code
bfs(visited, graph, 'A')

Output:
A B C D E F

12
6 Write a program to inrplement Depth First Search Traversal.

# Using a Python dictionary to act as an adjacency list

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

visited = set() # Set to keep track of visited nodes of graph.

def dfs(visited, graph, node): #function for dfs

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

# Driver Code
print("Following is the Depth-First Search")
dfs(visited, graph, '5')

output:
Following is the Depth-First Search
5
3
2
4
8
7

13
7 Write a prcgram to implernent Water Jug problem.
# This function is used to initialize the
# 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.

14
waterJugSolver(0, 0)

Output:

Steps:
00
40
43
03
30
33
42
02
True

15
8. Write a Program to lmplernent 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(np.array([[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:
l.append((i, j))
return(l)

# Select a random place for the player

def random_place(board, player):

selection = possibilities(board)
current_loc = random.choice(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

16
# 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 np.all(board != 0) and winner == 0:

winner = -1
return winner

# Main function to start the game

def play_game():

17
 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]
[0 1 0]]
Board after 2 move
[[0 0 0]
[2 0 0]
[0 1 0]]
Board after 3 move
[[1 0 0]
[2 0 0]
[0 1 0]]
Board after 4 move
[[1 0 0]
[2 2 0]
[0 1 0]]
Board after 5 move
[[1 1 0]
[2 2 0]
[0 1 0]]
Board after 6 move
[[1 1 0]
[2 2 2]
[0 1 0]]
Winner is: 2

18
9. Write a python program to implement k-nearest neighbor algorithm.

KNN
KNN is a simple, supervised machine learning (ML) algorithm that can be used for
classification or regression tasks - and is also frequently used in missing value imputation. It
is based on the idea that the observations closest to a given data point are the most "similar"
observations in a data set, and we can therefore classify unforeseen points based on the
values of the closest existing points. By choosing K, the user can select the number of nearby
observations to use in the algorithm.

Here, we will show you how to implement the KNN algorithm for classification, and show how
different values of K affect the results.

How does it work?

K is the number of nearest neighbors to use. For classification, a majority vote is used to
determined which class a new observation should fall into. Larger values of K are often more
robust to outliers and produce more stable decision boundaries than very small values
(K=3 would be better than K=1, which might produce undesirable results.

Example
Start by visualizing some data points:

import matplotlib.pyplot as plt

x = [4, 5, 10, 4, 3, 11, 14 , 8, 10, 12]

y = [21, 19, 24, 17, 16, 25, 24, 22, 21, 21]
classes = [0, 0, 1, 0, 0, 1, 1, 0, 1, 1]

plt.scatter(x, y, c=classes)
plt.show()

Result:

19
#Now we fit the KNN algorithm with K=1:

from sklearn.neighbors import KNeighborsClassifier

data = list(zip(x, y))

knn = KNeighborsClassifier(n_neighbors=1)

knn.fit(data, classes)

#And use it to classify a new data point:

#Example:

new_x = 8
new_y = 21
new_point = [(new_x, new_y)]

prediction = knn.predict(new_point)

plt.scatter(x + [new_x], y + [new_y], c=classes + [prediction[0]])

plt.text(x=new_x-1.7, y=new_y-0.7, s=f"new point, class: {prediction[0]}")
plt.show()

Result:

#Now we do the same thing, but with a higher K value which changes the prediction:
#Example

knn = KNeighborsClassifier(n_neighbors=5)

knn.fit(data, classes)

prediction = knn.predict(new_point)

plt.scatter(x + [new_x], y + [new_y], c=classes + [prediction[0]])

plt.text(x=new_x-1.7, y=new_y-0.7, s=f"new point, class: {prediction[0]}")
plt.show()

20
21
10. write a program to implement 8-puzzle problem using python
# Python3 program to print the path from root
# node to destination node for N*N-1 puzzle
# algorithm using Branch and Bound
# The solution assumes that instance of
# puzzle is solvable

# Importing copy for deepcopy function

import copy

# Importing the heap functions from python

# library for Priority Queue
from heapq import heappush, heappop

# This variable can be changed to change

# the program from 8 puzzle(n=3) to 15
# puzzle(n=4) to 24 puzzle(n=5)...
n = 3

# bottom, left, top, right

row = [ 1, 0, -1, 0 ]
col = [ 0, -1, 0, 1 ]

# A class for Priority Queue

class priorityQueue:

# Constructor to initialize a
# Priority Queue
def __init__(self):
self.heap = []

# Inserts a new key 'k'

def push(self, k):
heappush(self.heap, k)

# Method to remove minimum element

# from Priority Queue
def pop(self):
return heappop(self.heap)

# Method to know if the Queue is empty

def empty(self):
if not self.heap:
return True
else:
return False

# Node structure
class node:

def __init__(self, parent, mat, empty_tile_pos,

cost, level):

# Stores the parent node of the

# current node helps in tracing
# path when the answer is found
self.parent = parent

22
 # Stores the matrix
self.mat = mat

# Stores the position at which the

# empty space tile exists in the matrix
self.empty_tile_pos = empty_tile_pos

# Stores the number of misplaced tiles

self.cost = cost

# Stores the number of moves so far

self.level = level

# This method is defined so that the

# priority queue is formed based on
# the cost variable of the objects
def __lt__(self, nxt):
return self.cost < nxt.cost

# Function to calculate the number of

# misplaced tiles ie. number of non-blank
# tiles not in their goal position
def calculateCost(mat, final) -> int:

count = 0
for i in range(n):
for j in range(n):
if ((mat[i][j]) and
(mat[i][j] != final[i][j])):
count += 1

return count

def newNode(mat, empty_tile_pos, new_empty_tile_pos,

level, parent, final) -> node:

# Copy data from parent matrix to current matrix

new_mat = copy.deepcopy(mat)

# Move tile by 1 position

x1 = empty_tile_pos[0]
y1 = empty_tile_pos[1]
x2 = new_empty_tile_pos[0]
y2 = new_empty_tile_pos[1]
new_mat[x1][y1], new_mat[x2][y2] = new_mat[x2][y2], new_mat[x1][y1]

# Set number of misplaced tiles

cost = calculateCost(new_mat, final)

new_node = node(parent, new_mat, new_empty_tile_pos,

cost, level)
return new_node

# Function to print the N x N matrix

def printMatrix(mat):

for i in range(n):
for j in range(n):

23
 print("%d " % (mat[i][j]), end = " ")

print()

# Function to check if (x, y) is a valid

# matrix coordinate
def isSafe(x, y):

return x >= 0 and x < n and y >= 0 and y < n

# Print path from root node to destination node

def printPath(root):

if root == None:
return

printPath(root.parent)
printMatrix(root.mat)
print()

# Function to solve N*N - 1 puzzle algorithm

# using Branch and Bound. empty_tile_pos is
# the blank tile position in the initial state.
def solve(initial, empty_tile_pos, final):

# Create a priority queue to store live

# nodes of search tree
pq = priorityQueue()

# Create the root node

cost = calculateCost(initial, final)
root = node(None, initial,
empty_tile_pos, cost, 0)

# Add root to list of live nodes

pq.push(root)

# Finds a live node with least cost,

# add its children to list of live
# nodes and finally deletes it from
# the list.
while not pq.empty():

# Find a live node with least estimated

# cost and delete it from the list of
# live nodes
minimum = pq.pop()

# If minimum is the answer node

if minimum.cost == 0:

# Print the path from root to

# destination;
printPath(minimum)
return

# Generate all possible children

for i in range(4):

24
 new_tile_pos = [
minimum.empty_tile_pos[0] + row[i],
minimum.empty_tile_pos[1] + col[i], ]

if isSafe(new_tile_pos[0], new_tile_pos[1]):

# Create a child node

child = newNode(minimum.mat,
minimum.empty_tile_pos,
new_tile_pos,
minimum.level + 1,
minimum, final,)

# Add child to list of live nodes

pq.push(child)

# Driver Code

# Initial configuration
# Value 0 is used for empty space
initial = [ [ 1, 2, 3 ],
[ 5, 6, 0 ],
[ 7, 8, 4 ] ]

# Solvable Final configuration

# Value 0 is used for empty space
final = [ [ 1, 2, 3 ],
[ 5, 8, 6 ],
[ 0, 7, 4 ] ]

# Blank tile coordinates in

# initial configuration
empty_tile_pos = [ 1, 2 ]

# Function call to solve the puzzle

solve(initial, empty_tile_pos, final)

# This code is contributed by Kevin Joshi

Output:
1 2 3
5 6 0
7 8 4

1 2 3
5 0 6
7 8 4

1 2 3
5 8 6
7 0 4

1 2 3
5 8 6
0 7 4

25
11. Write a program to implement travelling salesman problem using python

# Python program to find the shortest possible route

# that visits every city exactly once and returns to
# the starting point

from itertools import permutations

def tsp(cost):

# Number of nodes
numNodes = len(cost)
nodes = list(range(1, numNodes))

minCost = float('inf')

# Generate all permutations of the

# remaining nodes
for perm in permutations(nodes):
currCost = 0
currNode = 0

# Calculate the cost of the current permutation

for node in perm:
currCost += cost[currNode][node]
currNode = node

# Add the cost to return to the starting node

currCost += cost[currNode][0]

# Update the minimum cost if the current cost

# is lower
minCost = min(minCost, currCost)

return minCost

if __name__ == "__main__":

cost = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]

res = tsp(cost)
print(res)

Output:
80

26
12. Write a program to implement regression algorithm using python

import matplotlib.pyplot as plt

x = [5,7,8,7,2,17,2,9,4,11,12,9,6]
y = [99,86,87,88,111,86,103,87,94,78,77,85,86]

plt.scatter(x, y)
plt.show()

import matplotlib.pyplot as plt

from scipy import stats

x = [5,7,8,7,2,17,2,9,4,11,12,9,6]
y = [99,86,87,88,111,86,103,87,94,78,77,85,86]

slope, intercept, r, p, std_err = stats.linregress(x, y)

def myfunc(x):
return slope * x + intercept

mymodel = list(map(myfunc, x))

plt.scatter(x, y)
plt.plot(x, mymodel)
plt.show()

27
13. write a python program to implement random forest algorithm

import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import accuracy_score, classification_report
import warnings
warnings.filterwarnings('ignore')

# Corrected URL for the dataset

url =
"https://raw.githubusercontent.com/datasciencedojo/datasets/master/titanic.csv"
titanic_data = pd.read_csv(url)

# Drop rows with missing 'Survived' values

titanic_data = titanic_data.dropna(subset=['Survived'])

# Features and target variable

X = titanic_data[['Pclass', 'Sex', 'Age', 'SibSp', 'Parch', 'Fare']]
y = titanic_data['Survived']

# Encode 'Sex' column

X.loc[:, 'Sex'] = X['Sex'].map({'female': 0, 'male': 1})

# Fill missing 'Age' values with the median

X.loc[:, 'Age'].fillna(X['Age'].median(), inplace=True)

# Split data into training and testing sets

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2,
random_state=42)

# Initialize RandomForestClassifier
rf_classifier = RandomForestClassifier(n_estimators=100, random_state=42)

# Fit the classifier to the training data

rf_classifier.fit(X_train, y_train)

# Make predictions
y_pred = rf_classifier.predict(X_test)

# Calculate accuracy and classification report

accuracy = accuracy_score(y_test, y_pred)
classification_rep = classification_report(y_test, y_pred)

# Print the results

print(f"Accuracy: {accuracy:.2f}")
print("\nClassification Report:\n", classification_rep)

# Sample prediction
sample = X_test.iloc[0:1] # Keep as DataFrame to match model input format
prediction = rf_classifier.predict(sample)

# Retrieve and display the sample

sample_dict = sample.iloc[0].to_dict()
print(f"\nSample Passenger: {sample_dict}")
print(f"Predicted Survival: {'Survived' if prediction[0] == 1 else 'Did Not
Survive'}")

28
output:
Accuracy: 0.80

Classification Report:
precision recall f1-score support

0 0.82 0.85 0.83 105

1 0.77 0.73 0.75 74

accuracy 0.80 179

macro avg 0.79 0.79 0.79 179
weighted avg 0.80 0.80 0.80 179

Sample Passenger: {'Pclass': 3, 'Sex': 1, 'Age': 28.0, 'SibSp': 1, 'Parch': 1,

'Fare': 15.2458}
Predicted Survival: Did Not Survive

29
14. Write a program to implement tower of hanoi using python.
# Recursive Python function to solve the tower of hanoi

def TowerOfHanoi(n , source, destination, auxiliary):

if n==1:
print ("Move disk 1 from source",source,"to destination",destination)
return
TowerOfHanoi(n-1, source, auxiliary, destination)
print ("Move disk",n,"from source",source,"to destination",destination)
TowerOfHanoi(n-1, auxiliary, destination, source)

# Driver code
n = 4
TowerOfHanoi(n,'A','B','C')
# A, C, B are the name of rods

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

30
15. Write a program to implement monkey banana problem using python

class State:
def __init__(self, monkey, box, banana):
self.monkey = monkey # Position of the monkey
self.box = box # Position of the box
self.banana = banana # Position of the banana

def __str__(self):
return f"Monkey: {self.monkey}, Box: {self.box}, Banana: {self.banana}"

def push_box(state):
if not state.box and not state.monkey:
return State(state.monkey, True, state.banana)
return state

def climb_box(state):
if state.box and not state.monkey:
return State(True, state.box, state.banana)
return state

def grab_banana(state):
if state.monkey and state.banana:
print("Banana grabbed!")
return State(state.monkey, state.box, True)
return state

def monkey_banana_problem():
initial_state = State(False, False, False)
print("Initial State:", initial_state)

state = push_box(initial_state)
print("After pushing the box:", state)

state = climb_box(state)
print("After climbing the box:", state)

state = grab_banana(state)

if __name__ == "__main__":
monkey_banana_problem()

Output:
Initial State: Monkey: False, Box: False, Banana: False
After pushing the box: Monkey: False, Box: True, Banana: False
After climbing the box: Monkey: True, Box: True, Banana: False

31
16. Write a Program to Implement Alpha-Beta pruning using python
# Python3 program to demonstrate
# working of Alpha-Beta Pruning

# Initial values of Alpha and Beta

MAX, MIN = 1000, -1000

# Returns optimal value for current player

#(Initially called for root and maximizer)
def minimax(depth, nodeIndex, maximizingPlayer,
values, alpha, beta):

# Terminating condition. i.e

# leaf node is reached
if depth == 3:
return values[nodeIndex]

if maximizingPlayer:

best = MIN

# Recur for left and right children

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)

# Alpha Beta Pruning

if beta <= alpha:
break

return best

else:
best = MAX

# Recur for left and

# right children
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)

# Alpha Beta Pruning

if beta <= alpha:
break

return best

# Driver Code
if __name__ == "__main__":

values = [3, 5, 6, 9, 1, 2, 0, -1]

print("The optimal value is :", minimax(0, 0, True, values, MIN, MAX))

32
# This code is contributed by Rituraj Jain

Output:
The optimal value is : 5

33
17. Write a program to implement 8 queens problem using python

N = 8 # (size of the chessboard)

def solveNQueens(board, col):

if col == N:
print(board)
return True
for i in range(N):
if isSafe(board, i, col):
board[i][col] = 1
if solveNQueens(board, col + 1):
return True
board[i][col] = 0
return False

def isSafe(board, row, col):

for x in range(col):
if board[row][x] == 1:
return False
for x, y in zip(range(row, -1, -1), range(col, -1, -1)):
if board[x][y] == 1:
return False
for x, y in zip(range(row, N, 1), range(col, -1, -1)):
if board[x][y] == 1:
return False
return True

board = [[0 for x in range(N)] for y in range(N)]

if not solveNQueens(board, 0):
print("No solution found")

Output:
[[1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0], [0, 0, 0, 0, 1, 0, 0, 0], [0,
0, 0, 0, 0, 0, 0, 1], [0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0,
0, 0, 1, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0]]

34