___________________________________________________

## Implement A* algorithm for shortest path problem 8queens
___________________________________________________

import heapq

class PuzzleState:
    def __init__(self, board, parent=None, move=""):
        self.board = board
        self.parent = parent
        self.move = move
        self.g = 0 if parent is None else parent.g + 1
        self.h = self.manhattan_distance()
        
    def __lt__(self, other):
        return (self.g + self.h) < (other.g + other.h)
    
    def __eq__(self, other):
        return self.board == other.board
    
    def __hash__(self):
        return hash(tuple(tuple(row) for row in self.board))
    
    def manhattan_distance(self):
        distance = 0
        for i in range(3):
            for j in range(3):
                if self.board[i][j] != 0:
                    x, y = divmod(self.board[i][j]-1, 3)
                    distance += abs(x - i) + abs(y - j)
        return distance
    
    def get_blank_pos(self):
        for i in range(3):
            for j in range(3):
                if self.board[i][j] == 0:
                    return i, j
                
    def get_successors(self):
        successors = []
        i, j = self.get_blank_pos()
        
        moves = {
            'UP': (i-1, j),
            'DOWN': (i+1, j),
            'LEFT': (i, j-1),
            'RIGHT': (i, j+1)
        }
        
        for move, (x, y) in moves.items():
            if 0 <= x < 3 and 0 <= y < 3:
                new_board = [row[:] for row in self.board]
                new_board[i][j], new_board[x][y] = new_board[x][y], new_board[i][j]
                successors.append(PuzzleState(new_board, self, move))
                
        return successors
    
    def get_path(self):
        path = []
        current = self
        while current:
            path.append((current.move, current.board))
            current = current.parent
        return path[::-1]


def a_star_8_puzzle(initial, goal):
    open_set = []
    closed_set = set()
    
    start_state = PuzzleState(initial)
    goal_state = PuzzleState(goal)
    
    heapq.heappush(open_set, start_state)
    
    while open_set:
        current = heapq.heappop(open_set)
        
        if current.board == goal_state.board:
            return current.get_path()
        
        closed_set.add(current)
        
        for successor in current.get_successors():
            if successor in closed_set:
                continue
                
            if successor not in open_set:
                heapq.heappush(open_set, successor)
            else:
                for i, state in enumerate(open_set):
                    if state == successor and state.g > successor.g:
                        open_set[i] = successor
                        heapq.heapify(open_set)
                        break
    
    return None


initial = [
    [1, 2, 3],
    [4, 0, 6],
    [7, 5, 8]
]

goal = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 0]
]

solution = a_star_8_puzzle(initial, goal)
if solution:
    for step in solution:
        print(f"Move: {step[0]}")
        for row in step[1]:
            print(row)
        print()
else:
    print("No solution found")


________________________________

## A* Algorithm for path finding
_________________________________

from heapq import heappush, heappop

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

def astar(grid, start, goal):
    neighbors = [(0,1),(0,-1),(1,0),(-1,0)]
    close_set = set()
    came_from = {}
    gscore = {start:0}
    fscore = {start:heuristic(start, goal)}
    oheap = []
    heappush(oheap, (fscore[start], start))

    while oheap:
        current = heappop(oheap)[1]

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

        close_set.add(current)
        for i, j in neighbors:
            neighbor = current[0] + i, current[1] + j
            tentative_g_score = gscore[current] + 1
            if 0 <= neighbor[0] < len(grid):
                if 0 <= neighbor[1] < len(grid[0]):
                    if grid[neighbor[0]][neighbor[1]] == 1:
                        continue
                else:
                    continue
            else:
                continue

            if neighbor in close_set and tentative_g_score >= gscore.get(neighbor, float('inf')):
                continue

            if tentative_g_score < gscore.get(neighbor, float('inf')) or neighbor not in [i[1] for i in oheap]:
                came_from[neighbor] = current
                gscore[neighbor] = tentative_g_score
                fscore[neighbor] = tentative_g_score + heuristic(neighbor, goal)
                heappush(oheap, (fscore[neighbor], neighbor))
    return None


grid = [
    [0,0,0,0,0],
    [0,1,1,1,0],
    [0,0,0,0,0],
    [0,1,0,1,0],
    [0,0,0,0,0]
]

start = (0,0)
goal = (4,4)
path = astar(grid, start, goal)
print(path)


__________

## 3
___________

import heapq
def a_star(graph, start , goal , heuristic):
    open = [(heuristic[start], 0 , start, [start])]
    visited = set()
    while open:
        f ,g , node ,path = heapq.heappop(open)
        if node == goal:
            return path, g
        if node in visited:
            continue
        visited.add(node)
        for neighbor, cost in graph[node].items():
            if neighbor not in visited:
                g_new = g+cost
                f_new = g_new + heuristic[neighbor]
                heapq.heappush(open, (f_new, g_new, neighbor, path+[neighbor]))
    return None, Float('inf')

graph = {
    'a' : {'b':1 , 'c':4},
    'b': {'a': 1, 'c': 2, 'd': 5},
    'c': {'a': 4, 'b': 2, 'd': 1},
    'd': {'b': 5, 'c': 1},
}

heuristic = {
    'a':7,
    'b':6,
    'c':2,
    'd':0
}

start, goal = 'a','d'
path, cost = a_star(graph, start , goal , heuristic)
print("SHORTEST PATH:", path)
print("TOTAL COST:", cost)




