Program 1: Demonstrate basic problem-solving using Breadth-First Search on a simple grid.

from collections import deque

def bfs_grid(grid, start, goal):
    """
    Find shortest path in a grid using BFS.
    0 = walkable, 1 = obstacle
    """
    rows, cols = len(grid), len(grid[0])
    queue = deque([(start, [start])])
    visited = {start}
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    while queue:
        (x, y), path = queue.popleft()
        
        if (x, y) == goal:
            return path
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if (0 <= nx < rows and 0 <= ny < cols and 
                grid[nx][ny] == 0 and (nx, ny) not in visited):
                visited.add((nx, ny))
                queue.append(((nx, ny), path + [(nx, ny)]))
    
    return None

# Main execution
print("BFS on Grid:")
grid = [
    [0, 0, 0, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 0],
    [0, 0, 1, 0]
]
path = bfs_grid(grid, (0, 0), (3, 3))
print(f"Path from (0,0) to (3,3): {path}\n")

from collections import deque

def bfs_grid(grid, start, goal):
    """
    Find shortest path in a grid using BFS.
    0 = walkable, 1 = obstacle
    """
    rows, cols = len(grid), len(grid[0])
    queue = deque([(start, [start])])
    visited = {start}
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    
    while queue:
        (x, y), path = queue.popleft()
        
        if (x, y) == goal:
            return path
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if (0 <= nx < rows and 0 <= ny < cols and 
                grid[nx][ny] == 0 and (nx, ny) not in visited):
                visited.add((nx, ny))
                queue.append(((nx, ny), path + [(nx, ny)]))
    
    return None

# Main execution
print("BFS on Grid:")
grid = [
    [0, 0, 0, 0],
    [0, 1, 1, 0],
    [0, 0, 0, 0],
    [0, 0, 1, 0]
]
path = bfs_grid(grid, (0, 0), (3, 3))
print(f"Path from (0,0) to (3,3): {path}\n")