1. Write a Program to Implement Breadth First Search using Python.

# Function to find BFS of Graph from given source s

def bfsOfGraph(adj, s):

# get number of vertices

V = len(adj)

# create an array to store the traversal

res = [ ]

# Create a queue for BFS

from collections import deque
q = deque()

# Initially mark all the vertices as not visited

visited = [False] * V

# Mark source node as visited and enqueue it

visited[s] = True
q.append(s)

# Iterate over the queue

while q:

# Dequeue a vertex from queue and store it

curr = q.popleft()
res.append(curr)

# Get all adjacent vertices of the dequeued

# vertex curr If an adjacent has not been
# visited, mark it visited and enqueue it
for x in adj[curr]:
if not visited[x]:
visited[x] = True
q.append(x)
 return res

if __name__ == "__main__":

# create the adjacency list

# [ [2, 3, 1], [0], [0, 4], [0], [2] ]
adj = [ [2, 3, 1], [0], [0, 4], [0], [2] ]
src = 0
ans = bfsOfGraph(adj, src)
for i in ans:
print(i, end=" ")

2. Write a Program to Implement Depth First Search using Python

def dfs_rec(adj, visited, s):

# Mark the current vertex as visited
visited[s] = True

# Print the current vertex

print(s, end=" ")

# Recursively visit all adjacent vertices

# that are not visited yet
for i in adj[s]:
if not visited[i]:
dfs_rec(adj, visited, i)

def dfs(adj, s):

visited = [False] * len(adj)
# Call the recursive DFS function
dfs_rec(adj, visited, s)
def add_edge(adj, s, t):
# Add edge from vertex s to t
adj[s].append(t)
# Due to undirected Graph
adj[t].append(s)

if __name__ == "__main__":
V=5

# Create an adjacency list for the graph

adj = [[] for _ in range(V)]

# Define the edges of the graph

edges = [[1, 2], [1, 0], [2, 0], [2, 3], [2, 4]]

# Populate the adjacency list with edges

for e in edges:
add_edge(adj, e[0], e[1])

source = 1
print("DFS from source:", source)
dfs(adj, source)

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(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

# 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():
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()))
4. Write a Program to Implement 8-Puzzle problem using Python

import heapq
from termcolor import colored

# Class to represent the state of the 8-puzzle

class PuzzleState:
def __init__(self, board, parent, move, depth, cost):
self.board = board # The puzzle board configuration
self.parent = parent # Parent state
self.move = move # Move to reach this state
self.depth = depth # Depth in the search tree
self.cost = cost # Cost (depth + heuristic)

def __lt__(self, other):

return self.cost < other.cost

# Function to display the board in a visually appealing format

def print_board(board):
print("+---+---+---+")
for row in range(0, 9, 3):
row_visual = "|"
for tile in board[row:row + 3]:
if tile == 0: # Blank tile
row_visual += f" {colored(' ', 'cyan')} |"
else:
row_visual += f" {colored(str(tile), 'yellow')} |"
print(row_visual)
print("+---+---+---+")

# Goal state for the puzzle

goal_state = [1, 2, 3, 4, 5, 6, 7, 8, 0]

# Possible moves for the blank tile (up, down, left, right)
moves = {
'U': -3, # Move up
 'D': 3, # Move down
'L': -1, # Move left
'R': 1 # Move right
}

# Function to calculate the heuristic (Manhattan distance)

def heuristic(board):
distance = 0
for i in range(9):
if board[i] != 0:
x1, y1 = divmod(i, 3)
x2, y2 = divmod(board[i] - 1, 3)
distance += abs(x1 - x2) + abs(y1 - y2)
return distance

# Function to get the new state after a move

def move_tile(board, move, blank_pos):
new_board = board[:]
new_blank_pos = blank_pos + moves[move]
new_board[blank_pos], new_board[new_blank_pos] = new_board[new_blank_pos],
new_board[blank_pos]
return new_board

# A* search algorithm
def a_star(start_state):
open_list = []
closed_list = set()
heapq.heappush(open_list, PuzzleState(start_state, None, None, 0, heuristic(start_state)))

while open_list:
current_state = heapq.heappop(open_list)

if current_state.board == goal_state:
return current_state

closed_list.add(tuple(current_state.board))
 blank_pos = current_state.board.index(0)

for move in moves:

if move == 'U' and blank_pos < 3: # Invalid move up
continue
if move == 'D' and blank_pos > 5: # Invalid move down
continue
if move == 'L' and blank_pos % 3 == 0: # Invalid move left
continue
if move == 'R' and blank_pos % 3 == 2: # Invalid move right
continue

new_board = move_tile(current_state.board, move, blank_pos)

if tuple(new_board) in closed_list:
continue

new_state = PuzzleState(new_board, current_state, move, current_state.depth + 1, current_state.depth

+ 1 + heuristic(new_board))
heapq.heappush(open_list, new_state)

return None

# Function to print the solution path

def print_solution(solution):
path = [ ]
current = solution
while current:
path.append(current)
current = current.parent
path.reverse()

for step in path:

print(f"Move: {step.move}")
print_board(step.board)
# Initial state of the puzzle
initial_state = [1, 2, 3, 4, 0, 5, 6, 7, 8]

# Solve the puzzle using A* algorithm

solution = a_star(initial_state)

# Print the solution

if solution:
print(colored("Solution found:", "green"))
print_solution(solution)
else:
print(colored("No solution exists.", "red"))

5. Write a Program to Implement Water-Jug problem using Python

# Function to perform DFS to solve the water jug problem

def water_jug_dfs(capacity1, capacity2, target):
visited = set() # To track visited states
path = [] # To store the solution path

def dfs(jug1, jug2):

# If we have already visited this state, return False (avoid cycles)
if (jug1, jug2) in visited:
return False

# Mark the state as visited

visited.add((jug1, jug2))

# Append the current state to the path

path.append((jug1, jug2))

# If the target is achieved in either jug, return True

if jug1 == target or jug2 == target:
return True
 # Explore all possible transitions (DFS recursive calls)
# Fill 3-liter jug
if dfs(3, jug2):
return True
# Fill 5-liter jug
if dfs(jug1, 5):
return True
# Empty 3-liter jug
if dfs(0, jug2):
return True
# Empty 5-liter jug
if dfs(jug1, 0):
return True
# Pour water from 3-liter jug into 5-liter jug
if dfs(max(0, jug1 - (5 - jug2)), min(5, jug1 + jug2)):
return True
# Pour water from 5-liter jug into 3-liter jug
if dfs(min(3, jug1 + jug2), max(0, jug2 - (3 - jug1))):
return True

# If none of the transitions lead to the goal, backtrack

path.pop()
return False

# Start DFS from the initial state (0, 0)

dfs(0, 0)

# If we found a solution, return the path

return path

# Example Usage
capacity1 = 3 # Capacity of the 3-liter jug
capacity2 = 5 # Capacity of the 5-liter jug
target = 4 # Target amount to measure
solution = water_jug_dfs(capacity1, capacity2, target)

if solution:
print("Solution steps:")
for step in solution:
print(step)
else:
print("No solution found.")

import matplotlib.pyplot as plt

import networkx as nx

# Function to create and visualize the state space transitions for DFS
def visualize_dfs_solution(solution):
G = nx.DiGraph()

# Add the nodes and edges based on the DFS solution path
for i in range(len(solution) - 1):
G.add_edge(solution[i], solution[i + 1])

pos = nx.spring_layout(G) # Position the nodes for visualization

plt.figure(figsize=(8, 6))

# Draw the graph with nodes and labels

nx.draw(G, pos, with_labels=True, node_color='lightgreen', node_size=1500, font_size=12,
font_weight='bold')
nx.draw_networkx_edges(G, pos, edgelist=list(G.edges()), edge_color='blue', width=2)

plt.title("Water Jug Problem - DFS Solution Path")

plt.show()

# Visualize the DFS solution

if solution:
visualize_dfs_solution(solution)
6. Write a Program to Implement Travelling Salesman Problem using Python

n = 4 # there are four nodes in example graph (graph is 1-based)

# dist[i][j] represents shortest distance to go from i to j

# this matrix can be calculated for any given graph using
# all-pair shortest path algorithms
dist = [[0, 0, 0, 0, 0], [0, 0, 10, 15, 20], [
0, 10, 0, 25, 25], [0, 15, 25, 0, 30], [0, 20, 25, 30, 0]]

# memoization for top down recursion

memo = [[-1]*(1 << (n+1)) for _ in range(n+1)]
def fun(i, mask):
# base case
# if only ith bit and 1st bit is set in our mask,
# it implies we have visited all other nodes already
if mask == ((1 << i) | 3):
return dist[1][i]

# memoization
if memo[i][mask] != -1:
return memo[i][mask]

res = 10**9 # result of this sub-problem

 # we have to travel all nodes j in mask and end the path at ith node
# so for every node j in mask, recursively calculate cost of
# travelling all nodes in mask
# except i and then travel back from node j to node i taking
# the shortest path take the minimum of all possible j nodes
for j in range(1, n+1):
if (mask & (1 << j)) != 0 and j != i and j != 1:
res = min(res, fun(j, mask & (~(1 << i))) + dist[j][i])
memo[i][mask] = res # storing the minimum value
return res

# Driver program to test above logic

ans = 10**9
for i in range(1, n+1):
# try to go from node 1 visiting all nodes in between to i
# then return from i taking the shortest route to 1
ans = min(ans, fun(i, (1 << (n+1))-1) + dist[i][1])

print("The cost of most efficient tour = " + str(ans))

7. 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

8. 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()
9. Write a Program to Implement Alpha-Beta Pruning using Python

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

10. Write a Program to Implement 8-Queens Problem using Python

global N
N=8

def printSolution(board):
for i in range(N):
for j in range(N):
print(board[i][j], end=' ')
print()

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
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

board[i][col] = 0

return False

def solveNQ():
board = [[0]*N for _ in range(N)]

if solveNQUtil(board, 0) == False:
print("Solution does not exist")
return False
 printSolution(board)
return True

# driver program to test above function

solveNQ()