class State():
 
    def __init__(self, plist=None):
 
        if plist == None:
            plist = [
                [1,2,3],
                [4,5,6],
                [7,8,0]
            ]
 
        self.plist = plist
 
    def show(self):
        for r in self.plist:
            for c in r:
                if c == 0:
                    print '.',
                else:
                    print c,
            print
 
 
    def is_goal(self):
        "returns True if it's goal."
        goal = ((1,2,3),(4,5,6),(7,8,0))
 
        for i in range(3):
            for j in range(3):
                if (self.plist[i][j] !=
                    goal[i][j]):
                    return False
        return True
 
 
    def current_pos(self):
        for i in range(3):
            for j in range(3):
                if self.plist[i][j] == 0:
                    return (i,j)
 
 
    def list_actions(self):
        i,j = self.current_pos()
        actions = []
        if j > 0:
            actions.append('left')
        if j < 2:
            actions.append('right')
        if i > 0:
            actions.append('up')
        if i < 2:
            actions.append('down')
 
        return actions
 
 
    def clone(self):
        nlist = []
        for r in self.plist:
            nlist.append(list(r))
        return State(nlist)
 
 
    def move_space(self, action):
        movement = { 'left': (0,-1),
                     'right': (0,1),
                     'up': (-1,0),
                     'down': (1,0) }
 
        i,j = self.current_pos()
        di, dj = movement[action]
        ni = i + di
        nj = j + dj
 
        # swap (i,j) and (ni,nj)
        a,b = self.plist[i][j], self.plist[ni][nj]
        self.plist[i][j], self.plist[ni][nj] = b,a
 
 
    def successor_function(self):
        successors = []
 
        for action in self.list_actions():
            successor = self.clone()
            successor.move_space(action)
            successors.append((action,successor))
 
        return successors