🤖 AI Search Algorithms in Python

from collections import deque

def bfs(graph, start, goal):
    """
    Breadth-First Search implementation
    Returns: path from start to goal
    """
    visited = set()
    queue = deque([(start, [start])])
    
    while queue:
        node, path = queue.popleft()
        
        if node == goal:
            return path
        
        if node not in visited:
            visited.add(node)
            
            for neighbor in graph.get(node, []):
                if neighbor not in visited:
                    queue.append((neighbor, path + [neighbor]))
    
    return None  # No path found

# Example usage
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

path = bfs(graph, 'A', 'F')
print(f"BFS Path: {path}")  # Output: ['A', 'C', 'F']

def dfs(graph, start, goal, visited=None, path=None):
    """
    Depth-First Search implementation (recursive)
    Returns: path from start to goal
    """
    if visited is None:
        visited = set()
    if path is None:
        path = []
    
    visited.add(start)
    path = path + [start]
    
    if start == goal:
        return path
    
    for neighbor in graph.get(start, []):
        if neighbor not in visited:
            result = dfs(graph, neighbor, goal, visited, path)
            if result:
                return result
    
    return None

# Iterative version
def dfs_iterative(graph, start, goal):
    stack = [(start, [start])]
    visited = set()
    
    while stack:
        node, path = stack.pop()
        
        if node == goal:
            return path
        
        if node not in visited:
            visited.add(node)
            
            for neighbor in reversed(graph.get(node, [])):
                if neighbor not in visited:
                    stack.append((neighbor, path + [neighbor]))
    
    return None

# Example usage
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

path = dfs(graph, 'A', 'F')
print(f"DFS Path: {path}")  # Output: ['A', 'B', 'E', 'F']

import heapq

def uniform_cost_search(graph, start, goal):
    """
    Uniform Cost Search (Dijkstra's Algorithm)
    Returns: (cost, path) tuple
    """
    frontier = [(0, start, [start])]
    explored = set()
    
    while frontier:
        cost, node, path = heapq.heappop(frontier)
        
        if node == goal:
            return cost, path
        
        if node not in explored:
            explored.add(node)
            
            for neighbor, edge_cost in graph.get(node, []):
                if neighbor not in explored:
                    new_cost = cost + edge_cost
                    heapq.heappush(frontier, (new_cost, neighbor, path + [neighbor]))
    
    return float('inf'), None

# Example usage with weighted graph
weighted_graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('D', 5), ('C', 1)],
    'C': [('D', 8), ('E', 10)],
    'D': [('E', 2), ('F', 6)],
    'E': [('F', 3)],
    'F': []
}

cost, path = uniform_cost_search(weighted_graph, 'A', 'F')
print(f"UCS - Cost: {cost}, Path: {path}")  # Output: Cost: 13, Path: ['A', 'B', 'D', 'E', 'F']

import heapq
import math

def astar(graph, start, goal, heuristic):
    """
    A* Search Algorithm
    Returns: (cost, path) tuple
    """
    frontier = [(heuristic(start, goal), 0, start, [start])]
    explored = set()
    
    while frontier:
        f, g, node, path = heapq.heappop(frontier)
        
        if node == goal:
            return g, path
        
        if node not in explored:
            explored.add(node)
            
            for neighbor, edge_cost in graph.get(node, []):
                if neighbor not in explored:
                    new_g = g + edge_cost
                    new_f = new_g + heuristic(neighbor, goal)
                    heapq.heappush(frontier, (new_f, new_g, neighbor, path + [neighbor]))
    
    return float('inf'), None

# Example with 2D grid and Manhattan distance heuristic
def manhattan_distance(node, goal):
    return abs(node[0] - goal[0]) + abs(node[1] - goal[1])

# Grid-based graph example
def create_grid_graph(width, height, obstacles=[]):
    graph = {}
    for x in range(width):
        for y in range(height):
            if (x, y) not in obstacles:
                neighbors = []
                for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < width and 0 <= ny < height and (nx, ny) not in obstacles:
                        neighbors.append(((nx, ny), 1))
                graph[(x, y)] = neighbors
    return graph

# Example usage
grid = create_grid_graph(5, 5, obstacles=[(2, 2), (2, 3)])
cost, path = astar(grid, (0, 0), (4, 4), manhattan_distance)
print(f"A* - Cost: {cost}, Path: {path}")

import heapq

def greedy_best_first_search(graph, start, goal, heuristic):
    """
    Greedy Best-First Search
    Returns: path from start to goal
    """
    frontier = [(heuristic(start, goal), start, [start])]
    explored = set()
    
    while frontier:
        h, node, path = heapq.heappop(frontier)
        
        if node == goal:
            return path
        
        if node not in explored:
            explored.add(node)
            
            for neighbor in graph.get(node, []):
                if neighbor not in explored:
                    h_value = heuristic(neighbor, goal)
                    heapq.heappush(frontier, (h_value, neighbor, path + [neighbor]))
    
    return None

# Example with straight-line distance heuristic
def euclidean_distance(node, goal):
    return math.sqrt((node[0] - goal[0])**2 + (node[1] - goal[1])**2)

# Graph with coordinates
coord_graph = {
    (0, 0): [(1, 0), (0, 1)],
    (1, 0): [(0, 0), (2, 0), (1, 1)],
    (2, 0): [(1, 0), (2, 1)],
    (0, 1): [(0, 0), (0, 2), (1, 1)],
    (1, 1): [(1, 0), (0, 1), (2, 1), (1, 2)],
    (2, 1): [(2, 0), (1, 1), (2, 2)],
    (0, 2): [(0, 1), (1, 2)],
    (1, 2): [(0, 2), (1, 1), (2, 2)],
    (2, 2): [(2, 1), (1, 2)]
}

path = greedy_best_first_search(coord_graph, (0, 0), (2, 2), euclidean_distance)
print(f"Greedy Path: {path}")

class CSP:
    """Constraint Satisfaction Problem solver"""
    
    def __init__(self, variables, domains, constraints):
        self.variables = variables
        self.domains = domains
        self.constraints = constraints
    
    def is_consistent(self, assignment, var, value):
        """Check if assigning value to var is consistent"""
        assignment[var] = value
        
        for constraint in self.constraints:
            if not constraint(assignment):
                del assignment[var]
                return False
        
        del assignment[var]
        return True
    
    def backtrack(self, assignment={}):
        """Backtracking search for CSP"""
        if len(assignment) == len(self.variables):
            return assignment
        
        # Select unassigned variable
        var = None
        for v in self.variables:
            if v not in assignment:
                var = v
                break
        
        # Try each value in domain
        for value in self.domains[var]:
            if self.is_consistent(assignment, var, value):
                assignment[var] = value
                result = self.backtrack(assignment)
                if result:
                    return result
                del assignment[var]
        
        return None
    
    def solve(self):
        """Solve the CSP"""
        return self.backtrack()

# Example: Map Coloring Problem
def map_coloring_example():
    # Australian states
    variables = ['WA', 'NT', 'SA', 'Q', 'NSW', 'V', 'T']
    domains = {var: ['red', 'green', 'blue'] for var in variables}
    
    # Adjacency constraints
    def constraint(assignment):
        edges = [('WA', 'NT'), ('WA', 'SA'), ('NT', 'SA'), ('NT', 'Q'),
                ('SA', 'Q'), ('SA', 'NSW'), ('SA', 'V'), ('Q', 'NSW'),
                ('NSW', 'V')]
        
        for v1, v2 in edges:
            if v1 in assignment and v2 in assignment:
                if assignment[v1] == assignment[v2]:
                    return False
        return True
    
    csp = CSP(variables, domains, [constraint])
    solution = csp.solve()
    return solution

# N-Queens Problem
def n_queens_csp(n=8):
    variables = list(range(n))  # Columns
    domains = {col: list(range(n)) for col in variables}  # Possible rows
    
    def constraint(assignment):
        for c1 in assignment:
            for c2 in assignment:
                if c1 < c2:
                    r1, r2 = assignment[c1], assignment[c2]
                    # Same row or diagonal
                    if r1 == r2 or abs(r1 - r2) == abs(c1 - c2):
                        return False
        return True
    
    csp = CSP(variables, domains, [constraint])
    return csp.solve()

# Example usage
print("Map Coloring Solution:")
print(map_coloring_example())

print("\n8-Queens Solution (row positions for each column):")
print(n_queens_csp(8))

import random

def min_conflicts(csp, max_steps=1000):
    """
    Min-conflicts algorithm for CSP
    Local search approach
    """
    # Generate random complete assignment
    assignment = {}
    for var in csp.variables:
        assignment[var] = random.choice(csp.domains[var])
    
    for _ in range(max_steps):
        # Check if current assignment is solution
        if all(constraint(assignment) for constraint in csp.constraints):
            return assignment
        
        # Find conflicted variable
        conflicted = []
        for var in csp.variables:
            # Check if var is in conflict
            temp = assignment[var]
            for constraint in csp.constraints:
                if not constraint(assignment):
                    conflicted.append(var)
                    break
        
        if not conflicted:
            return assignment
        
        # Pick random conflicted variable
        var = random.choice(conflicted)
        
        # Find value that minimizes conflicts
        min_conflicts_count = float('inf')
        best_values = []
        
        for value in csp.domains[var]:
            assignment[var] = value
            conflicts = sum(1 for c in csp.constraints if not c(assignment))
            
            if conflicts < min_conflicts_count:
                min_conflicts_count = conflicts
                best_values = [value]
            elif conflicts == min_conflicts_count:
                best_values.append(value)
        
        # Choose random best value
        assignment[var] = random.choice(best_values)
    
    return None  # No solution found

# Example: Sudoku solver
def sudoku_csp():
    """Create a simple 4x4 Sudoku CSP"""
    variables = [(i, j) for i in range(4) for j in range(4)]
    domains = {var: [1, 2, 3, 4] for var in variables}
    
    def constraint(assignment):
        # Check rows
        for i in range(4):
            row = [assignment.get((i, j)) for j in range(4) if (i, j) in assignment]
            if len(row) != len(set(row)):  # Duplicates
                return False
        
        # Check columns
        for j in range(4):
            col = [assignment.get((i, j)) for i in range(4) if (i, j) in assignment]
            if len(col) != len(set(col)):
                return False
        
        # Check 2x2 boxes
        for box_r in range(0, 4, 2):
            for box_c in range(0, 4, 2):
                box = []
                for i in range(box_r, box_r + 2):
                    for j in range(box_c, box_c + 2):
                        if (i, j) in assignment:
                            box.append(assignment[(i, j)])
                if len(box) != len(set(box)):
                    return False
        
        return True
    
    class SudokuCSP:
        def __init__(self):
            self.variables = variables
            self.domains = domains
            self.constraints = [constraint]
    
    return min_conflicts(SudokuCSP())

print("4x4 Sudoku solution using Min-Conflicts:")
solution = sudoku_csp()
if solution:
    for i in range(4):
        print([solution[(i, j)] for j in range(4)])
else:
    print("No solution found")

def solve_n_queens(n):
    """Solve N-Queens problem using backtracking"""
    def is_safe(board, row, col):
        # Check column
        for i in range(row):
            if board[i] == col:
                return False
        
        # Check diagonals
        for i in range(row):
            if abs(board[i] - col) == abs(i - row):
                return False
        
        return True
    
    def backtrack(board, row):
        if row == n:
            return board[:]
        
        for col in range(n):
            if is_safe(board, row, col):
                board[row] = col
                result = backtrack(board, row + 1)
                if result:
                    return result
                board[row] = -1
        
        return None
    
    board = [-1] * n
    solution = backtrack(board, 0)
    
    if solution:
        # Print the board
        for row in range(n):
            line = ['Q' if solution[row] == col else '.' for col in range(n)]
            print(' '.join(line))
        return solution
    return None

# Solve 8-Queens
print("8-Queens Solution:")
solve_n_queens(8)

import random

def hill_climbing(problem, max_iterations=1000):
    """Hill climbing local search algorithm"""
    current = problem.initial_state()
    
    for _ in range(max_iterations):
        neighbors = problem.get_neighbors(current)
        if not neighbors:
            break
        
        # Find best neighbor
        best_neighbor = max(neighbors, key=problem.evaluate)
        
        if problem.evaluate(best_neighbor) <= problem.evaluate(current):
            break  # Local maximum reached
        
        current = best_neighbor
    
    return current

# Example: Maximize function f(x) = -x^2 + 10x
class FunctionOptimization:
    def initial_state(self):
        return random.uniform(-10, 10)
    
    def get_neighbors(self, x, step=0.1):
        return [x - step, x + step]
    
    def evaluate(self, x):
        return -x**2 + 10*x

problem = FunctionOptimization()
result = hill_climbing(problem)
print(f"Hill Climbing result: x={result:.2f}, f(x)={problem.evaluate(result):.2f}")

import heapq

def gbfs_path(adj, names, tone, start_idx, exit_idx):
    # Priority queue sorted by (tone, name, idx)
    pq = [(tone[start_idx], names[start_idx], start_idx)]
    seen = {start_idx}
    parent = [-1] * len(names)

    while pq:
        _, _, u = heapq.heappop(pq)

        if u == exit_idx:
            path = []
            while u != -1:
                path.append(names[u])
                u = parent[u]
            return path[::-1]

        for v in adj[u]:
            if v not in seen:
                seen.add(v)
                parent[v] = u
                heapq.heappush(pq, (tone[v], names[v], v))
    return None

def main():
    # --- Hardcoded sample ---
    N, M = 7, 8
    names = ["A", "B", "C", "D", "E", "F", "G"]
    tone  = [12,   7,   6,   5,   3,   9,   1]  # must be before function call

    edges = [
        ("A", "B"),
        ("A", "C"),
        ("B", "D"),
        ("C", "D"),
        ("C", "E"),
        ("D", "F"),
        ("E", "G"),
        ("F", "G"),
        ("A", "G"),  # extra edge
    ]

    # Build index map
    idx = {name: i for i, name in enumerate(names)}

    # Build adjacency list
    adj = [[] for _ in range(N)]
    for u, v in edges[:M]:  # only take first M edges
        ui, vi = idx[u], idx[v]
        adj[ui].append(vi)
        adj[vi].append(ui)

    start_name, exit_name = "A", "G"
    s, t = idx[start_name], idx[exit_name]

    if s == t:
        print(start_name)
        return

    path = gbfs_path(adj, names, tone, s, t)
    print(-1 if path is None else " ".join(path))

if name == "main":
    main()

# Timetable Scheduling Problem

def build_graph(N, edges):
    """Build adjacency list for N classes given conflict edges"""
    adj = [[] for _ in range(N)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return adj

def conflicts_with(u, slot_u, adj, assign):
    """Check if assigning class u -> slot_u conflicts with neighbors"""
    for v in adj[u]:
        if assign[v] != -1 and assign[v] == slot_u:
            return True
    return False

def pick_slot_for_class(u, S, adj, assign, fixed):
    """Pick a valid slot for class u"""
    if fixed[u] != -1:  # if fixed slot exists
        return fixed[u]
    for slot in range(S):
        if not conflicts_with(u, slot, adj, assign):
            return slot
    return -1  # should never happen if input is valid

def solve_case(N, S, edges, fixed_pairs):
    """Solve one test case"""
    adj = build_graph(N, edges)
    assign = [-1] * N
    fixed = [-1] * N

    # Apply fixed slots
    for x, k in fixed_pairs:
        fixed[x] = k
        assign[x] = k

    # Assign classes in order
    for u in range(N):
        if assign[u] == -1:
            assign[u] = pick_slot_for_class(u, S, adj, assign, fixed)

    return assign

def main():
    T = int(input("Enter number of test cases: "))
    for _ in range(T):
        N, S, M, F = map(int, input("Enter N S M F: ").split())

        edges = []
        print(f"Enter {M} conflict pairs (u v):")
        for _ in range(M):
            u, v = map(int, input().split())
            edges.append((u, v))

        fixed_pairs = []
        print(f"Enter {F} fixed pairs (x k):")
        for _ in range(F):
            x, k = map(int, input().split())
            fixed_pairs.append((x, k))

        ans = solve_case(N, S, edges, fixed_pairs)
        print("Output:", " ".join(map(str, ans)))

if name == "main":
    main()

import heapq

def solve(N, M, grid, start_x, start_y, crystal_x, crystal_y):
    if (start_x, start_y) == (crystal_x, crystal_y):
        print(0)
        return

    INF = 10**18
    dist = [[INF] * M for _ in range(N)]
    dist[start_x][start_y] = 0

    # Min-heap: (time_so_far, x, y)
    pq = [(0, start_x, start_y)]
    directions = [(1,0), (-1,0), (0,1), (0,-1)]

    while pq:
        g, x, y = heapq.heappop(pq)
        if g != dist[x][y]:
            continue

        if (x, y) == (crystal_x, crystal_y):
            print(g)
            return

        for dx, dy in directions:
            nx = x + dx,
            ny = y + dy
            if 0 <= nx < N and 0 <= ny < M and grid[nx][ny] != '#':
                if grid[nx][ny] == '.':
                  step = 1  
                else:
                  step=  3  # entering cost
                ng = g + step 
                if ng < dist[nx][ny]:
                    dist[nx][ny] = ng
                    heapq.heappush(pq, (ng, nx, ny))

    print(-1)  # unreachable


if name == "main":
    # Read inputs using input()
    N, M = map(int, input().split())
    grid = [input().strip() for _ in range(N)]
    start_x, start_y = map(int, input().split())
    crystal_x, crystal_y = map(int, input().split())

    solve(N, M, grid, start_x, start_y, crystal_x, crystal_y)