TRAVISTRA

from collections import deque  def water_jug_problem(capacity_x, capacity_y, target):  # Initialize the starting state (0, 0)  initial_state = (0, 0)  # Create a set to keep track of visited states  visited = set()  # Create a queue for Breadth-First Search  queue = deque()  queue.append(initial_state)  while queue:  current_state = queue.popleft()  # If the target amount is reached, return the solution  if current_state[0] == target or current_state[1] == target:  return current_state  x, y = current_state  # Fill jug X  if x < capacity_x:  fill_x = (capacity_x, y)  if fill_x not in visited:  queue.append(fill_x)  visited.add(fill_x)  # Fill jug Y  if y < capacity_y:  fill_y = (x, capacity_y)  if fill_y not in visited:  queue.append(fill_y)  visited.add(fill_y)  # Pour water from jug X to jug Y  if x > 0 and y < capacity_y:  pour_x_to_y = (max(0, x - (capacity_y - y)), min(y + x, capacity_y))  if pour_x_to_y not in visited:  queue.append(pour_x_to_y)  visited.add(pour_x_to

 def is_safe(graph, vertex, color, c):  # Check if the given color 'c' is safe for the 'vertex'  for neighbor in graph[vertex]:  if color[neighbor] == c:  return False  return True  def graph_coloring(graph, num_colors, color, vertex, V):  # Base case: If all vertices are colored  if vertex == V:  return True  for c in range(1,num_colors+1):  if is_safe(graph,vertex,color,c):  color[vertex] =c  if graph_coloring(graph, num_colors, color, vertex + 1, V):  return True  color[vertex] = 0  return False  def print_solution(color):  print("Solution exists: Following are the assigned colors:")  for c in color:  print(c, end=" ")  print()  if __name__=="__main__":  # Define the city's regions as a graph (adjacency list)  graph = {  0: [1, 2, 3],  1: [0, 2],  2: [0, 1, 3],  3: [0, 2],  }  num_colors = 3 # Number of colors available  V= len(graph) # Number of regions in the city  color = [0] * V # Initialize colors  if graph_coloring(graph, num_c

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

 def BFS_SP(graph,start,goal):  explored=[]  queue=[[start]]  if start==goal:  print("Same node")  return  while queue:  path=queue.pop(0)  node=path[-1]  if node not in explored:  neighbours=graph[node]  for neighbour in neighbours:  new_path=list(path)  new_path.append(neighbour)  queue.append(new_path)  if neighbour==goal:  print("Shortst path= ", *new_path)  return  explored.append(node)  print("So sorry connecting path doesn't exist :(")  if __name__ =="__main__":  graph = {'A': ['B', 'E', 'C'],  'B': ['A', 'D', 'E'],  'C': ['A', 'F', 'G'],  'D': ['B', 'E'],  'E': ['A', 'B', 'D'],  'F:': ['C'],  'G': ['C']}  BFS_SP(graph,'B','G')

from queue import PriorityQueue   graph = {  'A': [('B', 3), ('C', 6), ('D', 5)],  'B': [('E', 9), ('F', 8)],  'C': [('G', 12), ('H', 14)],  'D': [('I', 7)],  'E': [('G', 10)],  'F': [],  'G': [],  'H': [],  'I': [('J', 1), ('K', 10), ('L', 2)],  'J': [],  'K': [],  'L': []  }  heuristic = {  'A': 10,  'B': 8,  'C': 8,  'D': 6,  'E': 5,  'F': 6,  'G': 0,  'H': 0,  'I': 4,  'J': 1,  'K': 10,  'L': 2  }  def best_first_search(graph, start, goal, heuristic):  visited = set()  pq = PriorityQueue()  pq.put((heuristic[start], start))  while not pq.empty():  _, current_node = pq.get()  if current_node == goal:  print("Goal reached:", current_node)  return  if current_node not in visited:  print("