#!/usr/bin/env python3
"""Auto-generated by AGI Loop cycle #1069
Task: Write a Python function that generates a random 15x15 maze and solves it with A* algorithm
Generated: 2026-02-12T18:59:26.608804
"""

import random
import heapq

def generate_maze(size=15):
    maze = [[1 for _ in range(size)] for _ in range(size)]
    directions = [(0, 2), (2, 0), (0, -2), (-2, 0)]
    visited = [(1, 1)]
    maze[1][1] = 0

    while visited:
        x, y = visited.pop()
        random.shuffle(directions)
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < size and 0 <= ny < size and maze[nx][ny] == 1:
                maze[nx][ny] = 0
                visited.append((nx, ny))
                maze[(x + nx) // 2][(y + ny) // 2] = 0
    return maze

def heuristic(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def a_star(maze, start, end):
    neighbors = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    open_set = [(0, start)]
    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, end)}

    while open_set:
        current = heapq.heappop(open_set)[1]
        if current == end:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            path.reverse()
            return path

        for dx, dy in neighbors:
            neighbor = (current[0] + dx, current[1] + dy)
            if 0 <= neighbor[0] < len(maze) and 0 <= neighbor[1] < len(maze[0]):
                if maze[neighbor[0]][neighbor[1]] == 0:
                    tentative_g_score = g_score[current] + 1
                    if neighbor not in g_score or tentative_g_score < g_score[neighbor]:
                        came_from[neighbor] = current
                        g_score[neighbor] = tentative_g_score
                        f_score[neighbor] = tentative_g_score + heuristic(neighbor, end)
                        heapq.heappush(open_set, (f_score[neighbor], neighbor))
    return None

def solve_maze():
    maze = generate_maze()
    start = (1, 1)
    end = (13, 13)
    path = a_star(maze, start, end)
    if path:
        print("Path found:", path)
    else:
        print("No path found")
    return maze, path

if __name__ == '__main__':
    maze, path = solve_maze()