Program 5: Apply the A* Search algorithm to find the shortest path in a 4x4 grid.

import heapq

def a_star_simple(grid, start, goal):
    # Manhattan distance heuristic
    def h(a, b):
        return abs(a[0] - b[0]) + abs(a[1] - b[1])

    open_list = []
    heapq.heappush(open_list, (0, start))

    visited = {}
    visited[start] = None

    while open_list:
        cost, current = heapq.heappop(open_list)

        if current == goal:
            path = []
            while current:
                path.append(current)
                current = visited[current]
            return path[::-1]

        for dx, dy in [(0,1), (1,0), (0,-1), (-1,0)]:
            next_cell = (current[0] + dx, current[1] + dy)

            if (0 <= next_cell[0] < 4 and
                0 <= next_cell[1] < 4 and
                grid[next_cell[0]][next_cell[1]] == 0 and
                next_cell not in visited):

                priority = cost + 1 + h(next_cell, goal)
                heapq.heappush(open_list, (priority, next_cell))
                visited[next_cell] = current

    return None

# Example
grid = [
    [0, 0, 0, 0],
    [0, 1, 0, 0],
    [0, 0, 0, 1],
    [0, 0, 0, 0]
]

print("Simple A* Path:")
print(a_star_simple(grid, (0, 0), (3, 3)))

import heapq

def a_star_simple(grid, start, goal):
    # Manhattan distance heuristic
    def h(a, b):
        return abs(a[0] - b[0]) + abs(a[1] - b[1])

    open_list = []
    heapq.heappush(open_list, (0, start))

    visited = {}
    visited[start] = None

    while open_list:
        cost, current = heapq.heappop(open_list)

        if current == goal:
            path = []
            while current:
                path.append(current)
                current = visited[current]
            return path[::-1]

        for dx, dy in [(0,1), (1,0), (0,-1), (-1,0)]:
            next_cell = (current[0] + dx, current[1] + dy)

            if (0 <= next_cell[0] < 4 and
                0 <= next_cell[1] < 4 and
                grid[next_cell[0]][next_cell[1]] == 0 and
                next_cell not in visited):

                priority = cost + 1 + h(next_cell, goal)
                heapq.heappush(open_list, (priority, next_cell))
                visited[next_cell] = current

    return None

# Example
grid = [
    [0, 0, 0, 0],
    [0, 1, 0, 0],
    [0, 0, 0, 1],
    [0, 0, 0, 0]
]

print("Simple A* Path:")
print(a_star_simple(grid, (0, 0), (3, 3)))