DFS
graph1={
'A':set(['B','C']),
'B':set(['A','D','E']),
'C':set(['A','F']),
'D':set(['B']),
'E':set(['B','F']),
'F':set(['C','E'])
def dfs(graph,node,visited):
if node not in visited:
visited.append(node)
for n in graph[node]:
dfs(graph,n,visited)
return visited
visited=dfs(graph1,'A',[])
print(visited)
BFS
from collections import deque
class Graph:
def __init__(self):
self.adj_list={}
def add_edge(self,u,v):
if u in self.adj_list:
self.adj_list[u].append(v)
else:
self.adj_list[u]=[v]
if v in self.adj_list:
self.adj_list[v].append(u)
else:
self.adj_list[v]=[u]
def bfs(self,start):
visited={}
queue=deque()
for vertex in self.adj_list:
visited[vertex]=False
visited[start]=True
queue.append(start)
while queue:
current=queue.popleft()
print(current,end=" ")
for neighbor in self.adj_list[current]:
if not visited[neighbor]:
visited[neighbor]=True
queue.append(neighbor)
#example
g=Graph()
g.add_edge(0,1)
g.add_edge(0,2)
g.add_edge(1,2)
g.add_edge(2,0)
g.add_edge(2,3)
g.add_edge(3,3)
print("BFS starting from vertex 2")
g.bfs(2)
BFS 2 ANOTHER
from collections import deque
def bfs(graph,start):
visited = set()
queue=deque([start])
visited.add(start)
while queue:
vertex=queue.popleft()
print(vertex,end=' ')
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
if __name__== "__main__":
graph={
'A':['B','C'],
'B':['A','D','E'],
'C':['A','F'],
'D':['B'],
'E':['B','F'],
'F':['C','E']
print("BFS traversal starting from vertex 'A':")
bfs(graph,'A')
TOWER OF HANOI
def moveTower(height,fromPole,toPole,withPole):
if height>=1:
moveTower(height-1,fromPole,withPole,toPole)
moveDisk(fromPole,toPole)
moveTower(height-1,withPole,toPole,fromPole)
def moveDisk(fp,tp):
print("moving disk from",fp,"to",tp)
moveTower(3,"A","B","C")
N QUEEN
def is_Safe(board,row,col):
for i in range(row):
if board[i][col]==1:
return False
for i,j in zip(range(row,-1,-1),range(col,-1,-1)):
if j<0:
break
if board[i][j]==1:
return False
for i,j in zip(range(row,-1,-1),range(col,len(board))):
if j>=len(board):
break
if board[i][j]==1:
return False
return True
def solve_n_queens_util(board,row):
if row>=len(board):
return True
for col in range(len(board)):
if is_Safe(board,row,col):
board[row][col]=1
if solve_n_queens_util(board,row+1):
return True
board[row][col]=0
return False
def solve_n_queens(n):
board=[[0 for _ in range(n)] for _ in range(n)]
if not solve_n_queens_util(board,0):
print("solution does not exist")
return
for row in board:
print(" ".join("Q" if col else "." for col in row))
solve_n_queens(4)
JUG PROBLEM
capacity = (12, 8, 5)
x = capacity[0]
y = capacity[1]
z = capacity[2]
memory = {}
ans = []
def get_all_states(state):
# Let the 3 jugs be called a, b, c
a = state[0]
b = state[1]
c = state[2]
# Base case: if we have reached the final state (6,6,0)
if (a == 6 and b == 6):
ans.append(state)
return True
# If the current state has already been visited, return False
if (a, b, c) in memory:
return False
# Mark the current state as visited
memory[(a, b, c)] = 1
# Empty jug A into jug B
if a > 0:
if a + b <= y:
if get_all_states((0, a + b, c)):
ans.append(state)
return True
else:
if get_all_states((a - (y - b), y, c)):
ans.append(state)
return True
# Empty jug A into jug C
if a > 0:
if a + c <= z:
if get_all_states((0, b, a + c)):
ans.append(state)
return True
else:
if get_all_states((a - (z - c), b, z)):
ans.append(state)
return True
# Empty jug B into jug A
if b > 0:
if a + b <= x:
if get_all_states((a + b, 0, c)):
ans.append(state)
return True
else:
if get_all_states((x, b - (x - a), c)):
ans.append(state)
return True
# Empty jug B into jug C
if b > 0:
if b + c <= z:
if get_all_states((a, 0, b + c)):
ans.append(state)
return True
else:
if get_all_states((a, b - (z - c), z)):
ans.append(state)
return True
# Empty jug C into jug A
if c > 0:
if a + c <= x:
if get_all_states((a + c, b, 0)):
ans.append(state)
return True
else:
if get_all_states((x, b, c - (x - a))):
ans.append(state)
return True
# Empty jug C into jug B
if c > 0:
if b + c <= y:
if get_all_states((a, b + c, 0)):
ans.append(state)
return True
else:
if get_all_states((a, y, c - (y - b))):
ans.append(state)
return True
return False
# Initial state
initial_state = (12, 0, 0)
print("Starting work...\n")
get_all_states(initial_state)
ans.reverse()
for i in ans:
print(i)
A STAR ALGO
def aStarAlgo(start_node, stop_node):
open_set = set([start_node]) # Corrected initialization of open_set
closed_set = set()
g = {} # Cost from start to the current node
parents = {} # Parents map to reconstruct the path
# Initialize starting values
g[start_node] = 0
parents[start_node] = start_node
while len(open_set) > 0:
n = None
# Find the node with the lowest f(n) = g(n) + h(n)
for v in open_set:
if n == None or g[v] + heuristic(v) < g[n] + heuristic(n):
n=v
if n == None:
print("Path does not exist!")
return None
# If the goal node is reached, reconstruct the path
if n == stop_node:
path = []
while parents[n] != n:
path.append(n)
n = parents[n]
path.append(start_node)
path.reverse()
print('Path found: {}'.format(path))
return path
# Check if neighbors exist for the current node
for (m, weight) in get_neighbors(n):
# If the neighbor hasn't been visited yet, add it to open_set
if m not in open_set and m not in closed_set:
open_set.add(m)
parents[m] = n
g[m] = g[n] + weight
# If the new path to the neighbor is shorter, update its cost and parent
else:
if g[m] > g[n] + weight:
g[m] = g[n] + weight
parents[m] = n
# If the neighbor is in closed_set, move it back to open_set
if m in closed_set:
closed_set.remove(m)
open_set.add(m)
# Remove n from open_set and add it to closed_set after processing
open_set.remove(n)
closed_set.add(n)
# If the loop finishes without finding the stop_node, no path exists
print("Path does not exist!")
return None
def get_neighbors(v):
if v in Graph_nodes:
return Graph_nodes[v]
else:
return None
def heuristic(n):
H_dist = {
'A': 11,
'B': 6,
'C': 5,
'D': 7,
'E': 3,
'F': 6,
'G': 5,
'H': 3,
'I': 1,
'J': 0
return H_dist[n]
Graph_nodes = {
'A': [('B', 2), ('E', 7)],
'B': [('A', 6), ('C', 3), ('D', 2)],
'C': [('B', 3), ('D', 1), ('E', 5)],
'D': [('B', 2), ('C', 1), ('E', 8)],
'E': [('C', 5), ('D', 8), ('I', 5), ('J', 5)],
'F': [('A', 3), ('G', 1), ('H', 7)],
'G': [('F', 1), ('I', 3)],
'H': [('F', 7), ('I', 2)],
'I': [('E', 5), ('G', 3), ('H', 2), ('J', 3)]
aStarAlgo('A', 'J')
TIC TAC TOE
# write a python program to design the sitmulation of tic tac toe game
import os
import time
board = [' ',' ',' ',' ',' ',' ',' ',' ',' ',' '] # Initialize with spaces instead of empty strings
player = 1
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 Cheackposition(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] != ' '):
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("Tic-Tac-Toe Game")
print("Player 1 [X] --- Player 2 [O]\n")
print()
print("Please Wait...")
time.sleep(1)
while(game == running):
os.system('cls')
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(Cheackposition(choice)):
board[choice] = Mark
player+=1
Checkwin()
os.system('cls')
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")
Cards
import random
suits =['Hearts','Diamonds','Spades','Clubs']
ranks =['2','3','4','5','6','7','8','9','10','Jack','Queen','King','Ace']
deck=[(rank,suit) for suit in suits for rank in ranks]
def shuffle_deck(deck):
random.shuffle(deck)
return deck
shuffle_deck=shuffle_deck(deck)
for card in shuffle_deck:
print(f'{card[0]} of {card[1]}')
AO ALGO
class Graph:
def __init__(self, graph, heuristic, start_node): # Changed _init_ to __init__
self.graph = graph # AND-OR graph (problem space)
self.heuristic = heuristic # Heuristic values for each node
self.start_node = start_node # Starting node
self.status = {} # Status of nodes (solved, not solved)
self.solution_graph = {} # Solution graph (final solution graph)
def get_min_cost_child(self, node):
"""Get the child node with the minimum heuristic cost."""
return min(self.graph.get(node, []), key=lambda child: sum(self.heuristic.get(c, 0) for c in child))
def ao_star(self, node):
"""Performs the AO* algorithm recursively."""
if node not in self.graph or not self.graph[node]:
# If the node has no children, return
return
# Get the minimum cost child or set of children (AND nodes)
min_child = self.get_min_cost_child(node)
# Recursively solve the child nodes
for child in min_child:
self.ao_star(child)
# Update the heuristic value of the node
self.heuristic[node] = sum(self.heuristic.get(c, 0) for c in min_child)
# Mark node as solved and update the solution graph
self.status[node] = "Solved"
self.solution_graph[node] = min_child
def display_solution(self):
"""Display the solution path derived by the AO* algorithm."""
print("Solution graph:")
for node, child in self.solution_graph.items():
print(f"{node} -> {child}")
# Define the graph (AND-OR graph)
graph = {
'A': [['B', 'C'], ['D']], # Node A has two children
'B': [['E'], ['F']],
'C': [['G']],
'D': [['H']],
'E': [],
'F': [],
'G': [],
'H': []
# Heuristic values for each node
heuristic = {
'A': 1,
'B': 6,
'C': 2,
'D': 12,
'E': 2,
'F': 4,
'G': 0,
'H': 3
}
# Starting node
start_node = 'A'
# Initialize the Graph
g = Graph(graph, heuristic, start_node)
# Run AO* algorithm
g.ao_star(start_node)
# Display the solution graph
g.display_solution()
HILL Climbing
import math
increment = 0.1
starting_Point = [1, 1]
point1 = [1,5]
point2 = [6,4]
point3 = [5,2]
point4 = [2,1]
def distance(x1, y1, x2, y2):
dist = math.pow(x2-x1, 2) + math.pow(y2-y1, 2)
return dist
def sumOfDistances(x1, y1, px1, py1, px2, py2, px3, py3, px4, py4):
d1 = distance(x1, y1, px1, py1)
d2 = distance(x1, y1, px2, py2)
d3 = distance(x1, y1, px3, py3)
d4 = distance(x1, y1, px4, py4)
return d1 + d2 + d3 + d4
def newDistance(x1, y1, point1, point2, point3, point4):
d1 = [x1, y1]
d1temp = sumOfDistances(x1, y1, point1[0],point1[1], point2[0],point2[1], point3[0],point3[1],
point4[0],point4[1])
d1.append(d1temp)
return d1
minDistance = sumOfDistances (starting_Point[0], starting_Point[1], point1[0],point1[1],
point2[0],point2[1], point3[0],point3[1], point4[0],point4[1])
flag = True
def newPoints(minimum, d1, d2, d3, d4):
if d1 [2] == minimum:
return [d1[0], d1[1]]
elif d2[2] == minimum:
return [d2[0], d2[1]]
elif d3[2] == minimum:
return [d3[0], d3[1]]
elif d4[2] == minimum:
return [d4[0], d4[1]]
i=1
while flag:
d1 = newDistance(starting_Point[0]+increment, starting_Point[1], point1, point2, point3, point4)
d2 = newDistance(starting_Point[0]-increment, starting_Point[1], point1, point2,point3, point4)
d3 = newDistance(starting_Point[0], starting_Point[1]+increment, point1, point2, point3, point4)
d4 = newDistance(starting_Point[0], starting_Point[1]-increment, point1, point2, point3, point4)
print (i,'', round(starting_Point[0], 2), round(starting_Point[1], 2))
minimum = min(d1[2], d2[2], d3[2], d4[2])
if minimum <minDistance:
starting_Point = newPoints(minimum, d1, d2, d3, d4)
minDistance = minimum
else:
flag = False
