Program 1 – Write a program to implement Breadth first search using

python

from collections import deque

def bfs(graph, start):

visited = set()
queue = deque([start])

while queue:
vertex = queue.popleft()
if vertex not in visited:
print(vertex, end=' ')
visited.add(vertex)
queue.extend(graph[vertex] - visited)
print('\n')

# Example graph represented as an adjacency list

graph = {
'A': {'B', 'C'},
'B': {'A', 'D', 'E'},
'C': {'A', 'F', 'G'},
'D': {'B'},
'E': {'B', 'H'},
'F': {'C'},
'G': {'C'},
'H': {'E'}
}

start_vertex = 'A'
print(f"BFS starting from vertex {start_vertex}:")
bfs(graph, start_vertex)

Output -

1
Program 2 – Write a program to implement simple chatbot

import random

def simple_chatbot(input_text):
greetings = ['hello', 'hi', 'hey', 'greetings']
farewells = ['bye', 'goodbye', 'see you', 'farewell']
responses = {
'how are you': 'I am doing well, thank you!',
'tell me a joke': 'Why did the scarecrow win an award? Because he was
outstanding in his field!',
'default': "I'm sorry, I didn't understand that."
}

input_text = input_text.lower()

for greeting in greetings:

if greeting in input_text:
return random.choice(['Hello!', 'Hi there!', 'Hey!'])

for farewell in farewells:

if farewell in input_text:
return random.choice(['Goodbye!', 'See you!', 'Take care!'])

for key in responses:

if key in input_text:
return responses[key]

return responses['default']

# Main loop for chatting

print("Simple Chatbot: Hello! How can I help you?")
while True:
user_input = input("You: ")

if user_input.lower() == 'exit':
print("Simple Chatbot: Goodbye!")
break

bot_response = simple_chatbot(user_input)
print("Simple Chatbot:", bot_response)
2
Output -

3
Program 3 – Write a program to implement DFS using python

def dfs(graph, start, visited=None):

if visited is None:
visited = set()
print(start, end=' ')
visited.add(start)
for neighbor in graph[start] - visited:
dfs(graph, neighbor, visited)

# Example graph represented as an adjacency list

graph = {
'A': {'B', 'C'},
'B': {'A', 'D', 'E'},
'C': {'A', 'F', 'G'},
'D': {'B'},
'E': {'B', 'H'},
'F': {'C'},
'G': {'C'},
'H': {'E'}
}

start_vertex = 'A'
print(f"DFS starting from vertex {start_vertex}:")
dfs(graph, start_vertex)

Output -

4
Program 4 – Write a program to implement Tic-Tak-toe

import os
import time

board = [' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']
player = 1

# Win Flags
Win = 1
Draw = -1
Running = 0
Stop = 1

Game = Running
Mark = 'X'

def DrawBoard():
print(" %c | %c | %c " % (board[1], board[2], board[3]))
print("___|___|___")
print(" %c | %c | %c " % (board[4], board[5], board[6]))
print("___|___|___")
print(" %c | %c | %c " % (board[7], board[8], board[9]))
print(" | | ")

def CheckPosition(x):
if board[x] == ' ':
return True
else:
return False

def CheckWin():
global Game

if board[1] == board[2] and board[2] == board[3] and board[1] != ' ':

Game = Win
elif board[4] == board[5] and board[5] == board[6] and board[4] != ' ':

5
 Game = Win
elif board[7] == board[8] and board[8] == board[9] and board[7] != ' ':
Game = Win
elif board[1] == board[4] and board[4] == board[7] and board[1] != ' ':
Game = Win
elif board[2] == board[5] and board[5] == board[8] and board[2] != ' ':
Game = Win
elif board[3] == board[6] and board[6] == board[9] and board[3] != ' ':
Game = Win
elif board[1] == board[5] and board[5] == board[9] and board[5] != ' ':
Game = Win
elif board[3] == board[5] and board[5] == board[7] and board[5] != ' ':
Game = Win
elif board[1] != ' ' and board[2] != ' ' and board[3] != ' ' and \
board[4] != ' ' and board[5] != ' ' and board[6] != ' ' and \
board[7] != ' ' and board[8] != ' ' and board[9] != ' ':
Game = Draw
else:
Game = Running

print("Player 1 [X] --- Player 2 [O]\n")

print()
print()
print("Please Wait...")
time.sleep(3)

while Game == Running:

DrawBoard()

if player % 2 != 0:
print("Player 1's chance")
Mark = 'X'
else:
print("Player 2's chance")
Mark = 'O'

choice = int(input("Enter the position between [1-9] where you want to mark:
"))
if CheckPosition(choice):
board[choice] = Mark
player += 1
CheckWin()
6
DrawBoard()

if Game == Draw:
print("Game Draw")
elif Game == Win:
player -= 1
if player % 2 != 0:
print("Player 1 Won")
else:
print("Player 2 Won")

Output -

7
Program 5 – Write a program to implement 8 puzzle problem

from heapq import heappush, heappop

class PuzzleNode:
def __init__(self, state, parent=None, move=None, cost=0):
self.state = state
self.parent = parent
self.move = move
self.cost = cost
self.heuristic = self.calculate_heuristic()

def __lt__(self, other):

return (self.cost + self.heuristic) < (other.cost + other.heuristic)

def __eq__(self, other):

return self.state == other.state

def get_blank_position(self):
for i in range(3):
for j in range(3):
if self.state[i][j] == 0:
return i, j

def calculate_heuristic(self):
# Manhattan distance heuristic
total_distance = 0
for i in range(3):
for j in range(3):
value = self.state[i][j]
if value != 0:
goal_row, goal_col = divmod(value - 1, 3)
total_distance += abs(i - goal_row) + abs(j - goal_col)
return total_distance

def get_neighbors(self):
i, j = self.get_blank_position()
neighbors = []

for move_i, move_j in [(0, 1), (1, 0), (0, -1), (-1, 0)]:

8
 new_i, new_j = i + move_i, j + move_j
if 0 <= new_i < 3 and 0 <= new_j < 3:
new_state = [row[:] for row in self.state]
new_state[i][j], new_state[new_i][new_j] = new_state[new_i][new_j],
new_state[i][j]
neighbors.append(PuzzleNode(new_state, parent=self, move=(i, j)))
return neighbors

def print_solution(node):
path = []
while node:
path.append(node.state)
node = node.parent
path.reverse()

for state in path:

print_board(state)
print()

def print_board(board):
for row in board:
print(" ".join(map(str, row)))

def solve_8_puzzle(initial_state):
initial_node = PuzzleNode(initial_state)
frontier = [initial_node]
explored = set()

while frontier:
current_node = heappop(frontier)

if current_node.state == [[1, 2, 3], [4, 5, 6], [7, 8, 0]]:

print("Solution found!")
print_solution(current_node)
return

explored.add(current_node)

for neighbor in current_node.get_neighbors():

if neighbor not in explored and neighbor not in frontier:
heappush(frontier, neighbor)

9
if __name__ == "__main__":
# Example initial state (change this to your desired initial state)
initial_state = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 0]
]

solve_8_puzzle(initial_state)

Output -

10
Program 6 – Write a program to implement water jug problem

def pour_water(jug1, jug2, capacity1, capacity2, target):

stack = [(0, 0)] # Initial state: both jugs are empty
visited = set()

while stack:
current_state = stack.pop()
jug1_current, jug2_current = current_state

if current_state in visited:
continue

visited.add(current_state)

print(f"Jug 1: {jug1_current} | Jug 2: {jug2_current}")

# Check if the target amount is reached

if jug1_current == target or jug2_current == target:
print("Target amount reached!")
return

# Pour water from jug1 to jug2

stack.append((min(jug1_current + jug2_current, capacity1), max(0,
jug1_current + jug2_current - capacity1)))
# Pour water from jug2 to jug1
stack.append((max(0, jug1_current + jug2_current - capacity2),
min(jug1_current + jug2_current, capacity2)))
# Fill jug1
stack.append((capacity1, jug2_current))
# Fill jug2
stack.append((jug1_current, capacity2))
# Empty jug1
stack.append((0, jug2_current))
# Empty jug2
stack.append((jug1_current, 0))

print("Target amount not reachable.")

if __name__ == "__main__":

11
 # Example capacities and target amount (change these to your desired values)
jug1_capacity = 4
jug2_capacity = 3
target_amount = 2

print(f"Solving water jug problem for Jug 1 capacity: {jug1_capacity}, Jug 2

capacity: {jug2_capacity}, Target amount: {target_amount}")
pour_water(0, 0, jug1_capacity, jug2_capacity, target_amount)

Output -

12
Program 7 – Write a program to implement Travelling salesman
problem

from itertools import permutations

def calculate_total_distance(path, distances):

total_distance = 0
for i in range(len(path) - 1):
total_distance += distances[path[i]][path[i + 1]]
total_distance += distances[path[-1]][path[0]] # Return to the starting city
return total_distance

def traveling_salesman_bruteforce(distances):
num_cities = len(distances)
cities = list(range(num_cities))
shortest_path = None
shortest_distance = float('inf')

for path_permutation in permutations(cities):

current_distance = calculate_total_distance(path_permutation, distances)
if current_distance < shortest_distance:
shortest_distance = current_distance
shortest_path = path_permutation

return shortest_path, shortest_distance

if __name__ == "__main__":
# Example distance matrix (replace this with your own distances)
distances = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]

shortest_path, shortest_distance = traveling_salesman_bruteforce(distances)

print("Shortest Path:", shortest_path)

print("Shortest Distance:", shortest_distance)

13
Output -

14