
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