#!/usr/bin/python3

import heapq

class state(object):
    __slots__ = ['zero', 'puzzle', 'moves', 'parent', 'key']
    def __init__(self, zero, puzzle, moves, parent=None):
        self.zero = zero
        self.puzzle = puzzle
        self.moves = moves
        self.parent = parent
        self.key = self.heuristics() + self.moves
    def heuristics(self):
        h = 0
        for i, p in enumerate(self.puzzle):
            if p != 0:
                r1, c1 = divmod(i, 3)
                r2, c2 = divmod(p - 1, 3)
                h += abs(r1 - r2) + abs(c1 - c2)
        return h
    def children(self):
        row, col = divmod(self.zero, 3)
        if row > 0: yield self.child(self.zero - 3)
        if row < 2: yield self.child(self.zero + 3)
        if col > 0: yield self.child(self.zero - 1)
        if col < 2: yield self.child(self.zero + 1)
    def child(self, newpos):
        p = list(self.puzzle)
        p[self.zero] = p[newpos]
        p[newpos] = 0
        return state(newpos, tuple(p), self.moves + 1, self)
    def ancestry(self):
        a = []
        s = self
        while s:
            a.append(s)
            s = s.parent
        return reversed(a)
    def __lt__(self, other):
        return self.key < other.key
    def __le__(self, other):
        return self.key <= other.key
    def __gt__(self, other):
        return self.key > other.key
    def __ge__(self, other):
        return self.key >= other.key
    def __str__(self):
        s = tuple((str(i) if i else ' ') for i in self.puzzle)
        return '{} {} {}\n{} {} {}\n{} {} {}'.format(*s)

def puzzle8(p):
    assert len(p) == 9
    assert frozenset(p) == frozenset(range(9))
    p = tuple(p)
    zero = None
    for i, pi in enumerate(p):
        if pi == 0:
            zero = i
            break
    assert p[zero] == 0
    queue = [state(zero, p, 0)]
    seen = dict()
    seen[queue[0].puzzle] = queue[0]
    goal = (1, 2, 3,
            4, 5, 6,
            7, 8, 0)
    while queue:
        s = heapq.heappop(queue)
        if (s.puzzle == goal):
            for a in s.ancestry():
                print(a)
                print('')
            print('Minimal number of moves: {}'.format(s.moves))
            print('')
            return
        for c in s.children():
            try:
                o = seen[c.puzzle]
                if o.key > c.key:
                    o.moves = c.moves
                    o.parent = c.parent
                    o.key = c.key
                    heapq.heapify(queue) # heapq has no decrease key op
            except KeyError:
                seen[c.puzzle] = c
                heapq.heappush(queue, c)

puzzle8([1, 3, 0,
         8, 4, 5,
         7, 2, 6])

puzzle8([3, 5, 1,
         6, 8, 0,
         7, 2, 4])