#graph class
class Puzzle:

    #init constructor
    def __init__(self, list, finish, G):
        assert(len(list) == 9)
        self.list = list
        self.finish = finish
        self.graph = [[list[0], list[1], list[2]], [list[3], list[4], list[5]],[list[6], list[7], list[8]]]
        self.goal = [[finish[0], finish[1], finish[2]], [finish[3], finish[4], finish[5]],[finish[6], finish[7], finish[8]]]
        self.G = G
        self.H = self.getH()
        self.F = self.H + self.G
    def __lt__(self, other):
        return self.F < other.F

    #get summation hueristic values of current graph
    def getH(self):
        totalDist = 0
        for ya in range(len(self.graph)):
            for xa in range(len(self.graph[ya])):
                value = self.graph[ya][xa]
                location = self.getLocation(self.goal, value)
                xb = location[0]
                yb = location[1]
                deltaX = abs(xa-xb)
                deltaY = abs(ya-yb)
                dist = deltaX + deltaY
                totalDist += dist
                ##print("(", xa, ",", ya, "), (", xb, ",", yb, ") Dist: ", dist, sep= '')
        ##print("Total Dist: ", totalDist)
        return totalDist

    #return of list of graphs of possible moves from current graph
    def getChildren(self):

        x = self.getBlankLocation()[0]
        y = self.getBlankLocation()[1]
        print("Blank Tile: (", x, ",", y, ")", sep = '')
        children = []

        if x != 2: ##
            newGraph = Puzzle(self.list, self.finish, self.G+1)
            children.append(newGraph.moveBlank("right"))
        if x != 0:
            newGraph = Puzzle(self.list, self.finish, self.G+1)
            children.append(newGraph.moveBlank("left"))
        if y != 2:
            newGraph = Puzzle(self.list, self.finish, self.G+1)
            children.append(newGraph.moveBlank("down"))
        if y != 0:
            newGraph = Puzzle(self.list, self.finish, self.G+1)
            children.append(newGraph.moveBlank("up"))
        return children

    def moveBlank(self, direction):
        blankLocation = self.getBlankLocation()
        x = blankLocation[0]
        y = blankLocation[1]

        if(direction == "right"):
            newLocation = (x+1, y)
            newValue = self.getValue(newLocation)
            self.setValue(blankLocation, newValue)
            self.setValue(newLocation, 0)
        if(direction == "left"):
            newLocation = (x-1, y)
            newValue = self.getValue(newLocation)
            self.setValue(blankLocation, newValue)
            self.setValue(newLocation, 0)
        if(direction == "up"):
            newLocation = (x, y-1)
            newValue = self.getValue(newLocation)
            self.setValue(blankLocation, newValue)
            self.setValue(newLocation, 0)
        if(direction == "down"):
            newLocation = (x, y+1)
            newValue = self.getValue(newLocation)
            self.setValue(blankLocation, newValue)
            self.setValue(newLocation, 0)

    def getValue(self, location):
        return self.graph[location[1]][location[0]]

    def setValue(self, location, value):
        self.graph[location[1]][location[0]] = value

    def getLocation(self, graph, value):
        for y in range(len(graph)):
            for x in range(len(graph[y])):
                if graph[y][x] == value:
                    return (x,y)
    def getBlankLocation(self):
        for y in range(len(self.graph)):
            for x in range(len(self.graph[y])):
                if self.graph[y][x] == 0:
                    return (x,y)

    #prints the graphs, replaces the 0 to blank
    def printGraphs(self, counter):
        a = self.graph[0]
        b = self.graph[1]
        c = self.graph[2]
        x = self.goal[0]
        y = self.goal[1]
        z = self.goal[2]

        output = []
        if counter == 1:
            print("=Initial=      =Goal=")
        else:
            print("=Current=      =Goal=")
        print(str(a).replace("0", " "), "  ", str(x).replace("0", " "), "  Step: ", counter)
        print(str(b).replace("0", " "), "  ", str(y).replace("0", " "), "     H: ", self.H )
        print(str(c).replace("0", " "), "  ", str(z).replace("0", " "), "     G: ", self.G)

#graphs (0 is the blank tile)
start = [2,8,3,1,6,4,7,0,5]
goal =  [1,2,3,8,0,4,7,6,5]
puzzle = Puzzle(start, goal, 0)
from queue import PriorityQueue
q = PriorityQueue()
q.put(puzzle)

puzzle.printGraphs(0)

children = puzzle.getChildren()
children[0].printGraphs(0)
#children2 = children[0].getChildren()
#for child in children2:
#    child.printGraphs(0)

def main():
    step = 0
    while not q.empty():
        step += 1
        if step > 4:
            break
        current = q.get()
        current.printGraphs(step)
        children = current.getChildren()
        for child in children:
            if child.H == 0:
                return
            q.put(child)

##main()