A* implementation of 8 puzzle
Okay, I realized what I was doing all wrong.
The Manhattan distance defined here is not admissible. Consider an initial state: 0 1 7 2 3 4 5 6 8. So the possible number of moves required to move 7 to its original position (i.e index 7) is 3 (down->down->left) but here the heuristic estimates it as 5 (i.e 7-2). So a better way of defining heuristic would be :

def manhattan(self):
        h = 0
        for i in range(3):
            for j in range(3):
                x, y = divmod(self.board[i][j], 3)
                h += abs(x-i) + abs(y-j)
        return h