"""

 Name: A* on 8 puzzle

 Author: Eugen Sawin <sawine@informatik.uni-freiburg.de>

 """

 import heapq

 def main():    

     goal = (1, 2, 3, 

             8, 0, 4, 

             7, 6, 5)

     init = (2, 8, 3, 

             1, 6, 4, 

             7, 0, 5)

     print "heuristic: none"

     search(init, goal, Heuristic(goal))

     print "\nheuristic: misplaced tiles"

     search(init, goal, MisplacedTiles(goal))

     print "\nheuristic: manhattan distance"

     search(init, goal, ManhattanDist(goal))

 def search(init, goal, h): 

     frontier = []

     print init

     print goal

     heapq.heapify(frontier)

     node = Node(init, None, 0, 0)

     heapq.heappush(frontier, (0, node))

     explored = set()   

     while len(frontier):

         k, node = heapq.heappop(frontier)

         print k

         explored.add(node.state) 

         if node.state == goal:

             print "goal found in %i steps" % len(explored)

             break         

         for child in expand(node, h):  

             #print child

             #print

             heapq.heappush(frontier, (child.h_cost, child))

 def expand(node, h):

     def swap(i1, i2):

         state = list(node.state)       

         a = state[i1]

         b = state[i2]

         state[i1] = b

         state[i2] = a

         return tuple(state)  

     children = []

     cost = node.cost + 1

     for i, v in enumerate(node.state):

         if v == 0:

             if i > 0:

                 s = swap(i, i-1)

                 children.append(Node(s, node, cost,  h(s) + 1))

             if i < 8:

                 s = swap(i, i+1)               

                 children.append(Node(s, node, cost,  h(s) + 1)) 

             if i > 2: 

                 s = swap(i, i-3)              

                 children.append(Node(s, node, cost,  h(s) + 1))  

             if i < 6:

                 s = swap(i, i+3)

                 children.append(Node(s, node, cost,  h(s) + 1))             

     return children      

 class Node(object):

     def __init__(self, state, parent, cost, h_cost):

         self.state = state

         self.parent = parent

         self.cost = cost 

         self.h_cost = h_cost

     def __less__(self, node):

         return self.h_cost < node.h_cost

     def __str__(self):

         return "\n".join((str(self.state[:3]), 

                           str(self.state[3:6]), 

                           str(self.state[6:])))

 class Heuristic(object):

     def __init__(self, goal):

         self.goal = goal

     def __call__(self, state):

         return 0

 class MisplacedTiles(Heuristic):

    def __call__(self, state):       

        h = 0

        for i, s in enumerate(state):

            if self.goal[i] != s:

                h += 1       

        return h

 class ManhattanDist(Heuristic):

    def __call__(self, state):       

        h = 0

        for i, s in enumerate(state):

            for i2, s2 in enumerate(self.goal):

                if s == s2:

                    d = abs(i-i2)

                    h += d%3 + int(d/3)      

        return h

 from argparse import ArgumentParser

 def parse_arguments():

     parser = ArgumentParser(description="8 puzzle")   

     return parser.parse_args()

 if __name__ == "__main__":

     main()