Posts

Showing posts from December, 2023

4 queen

N = 4 ld = [0] * 30 rd = [0] * 30 cl = [0] * 30 def printSolution(board):     for i in range(N):         for j in range(N):             print(" Q " if board[i][j] == 1 else " . ", end="")         print() def solveNQUtil(board, col):     if col >= N:         return True     for i in range(N):         if (ld[i - col + N - 1] != 1 and rd[i + col] != 1) and cl[i] != 1:             board[i][col] = 1             ld[i - col + N - 1] = rd[i + col] = cl[i] = 1             if solveNQUtil(board, col + 1):                 return True             board[i][col] = 0 # BACKTRACK             ld[i - col + N - 1] = rd[i + col] = cl[i] = 0     return False def solveNQ():     board = [[0 for _ in range(N)] for _ in range(N)]     if not solveNQUtil(board, 0):         print("Solution does not exist")         return False     printSolution(board)     return True if __name__ == "__main__":     solveNQ()

alpha beta

 tree = [[[5, 1, 2], [8, -8, -9]], [[9, 4, 5], [-3, 4, 3]]] root = 0 pruned = 0 def children(branch, depth, alpha, beta):  global tree  global root  global pruned  i = 0  for child in branch:  if type(child) is list:  (nalpha, nbeta) = children(child, depth + 1, alpha, beta)  if depth % 2 == 1:  beta = nalpha if nalpha < beta else beta  else:  alpha = nbeta if nbeta > alpha else alpha  branch[i] = alpha if depth % 2 == 0 else beta  i += 1  else:  if depth % 2 == 0 and alpha < child:  alpha = child  if depth % 2 == 1 and beta > child:  beta = child  if alpha >= beta:  pruned += 1  break  if depth == root:  tree = alpha if root == 0 else beta  return (alpha, beta) def alphabeta(in_tree=tree, start=root, upper=-15, lower=15):  global tree global pruned  global root  (alpha, beta) = children(tree, start, upper, lower)  if __name__ == "__main__":  print ("(alpha, beta): ", alpha, beta)  print ("Result: ", tree)  print ("Times pruned: ",

water jug

 from collections import deque def water_jug_bfs(capacity_a, capacity_b, target):     visited = set()     queue = deque([(0, 0)])     while queue:         current_state = queue.popleft()         a, b = current_state         if current_state in visited:             continue         visited.add(current_state)         if a == target or b == target:             print("Target amount reached:", current_state)             return         queue.append((0, b))         queue.append((a, 0))         queue.append((capacity_a, b))         queue.append((a, capacity_b))         queue.append((a - min(a, capacity_b - b), b + min(a, capacity_b - b)))         queue.append((a + min(b, capacity_a - a), b - min(b, capacity_a - a)))     print("Target amount not reachable with the given jug capacities.") # Example usage: jug_capacity_a = 4 jug_capacity_b = 3 target_amount = 2 print(f"Solving Water Jug problem for capacities ({jug_capacity_a}, {jug_capacity_b}) to measure {target_amount}