import random

goalState = [1,2,3,4,5,6,7,8,0]
startState = []
frontier = [[startState]]
currState = []
rand = 0
temp = 0
swap = 0
index = 0



def createPuzzle():
        max = len(goalState)
        for eachPass in xrange(max):
                rand = random.randint(0,8)
                if rand not in startState:
                        startState.append(rand)

                elif rand in startState:
                        while rand in startState:
                                rand = random.randint(0,8)
                        startState.append(rand)



        print startState[0], startState[1], startState[2]
        print startState[3], startState[4], startState[5]
        print startState[6], startState[7], startState[8]




def goal(state):
        if state == [1,2,3,4,5,6,7,8,0]:
                return True
        else:
                return False

def swap(a,b,currState):

        print currState

        currState[a], currState[b] = currState[b], currState[a]
        return currState

def addFrontier(state, frontier):

        if not frontier == []:
                global currState
                currState = frontier[0]
        else:
                global currState
                currState = startState

        if state[0] == 0:

                swap(0,1)
                frontier.append(currState)

                swap(0,3)
                frontier.append(currState)

        elif state[1] == 0:

                swap(1,0,currState)
                frontier.append(currState)

                swap(1,2,currState)
                frontier.append(currState)

                swap(1,4,currState)
                frontier.append(currState)


        elif state[2] == 0:

                swap(2,1,currState)
                frontier.append(currState)


                swap(2,5,currState)
                frontier.append(currState)


        elif state[3] == 0:

                swap(3,0,currState)
                frontier.append(currState)

                swap(3,4,currState)
                frontier.append(currState)


                swap(3,6,currState)
                frontier.append(currState)


        elif state[4] == 0:

                swap(4,1,currState)
                frontier.append(currState)


                swap(4,3,currState)
                frontier.append(currState)


                swap(4,5,currState)
                frontier.append(currState)


                swap(4,7,currState)
                frontier.append(currState)


        elif state[5] == 0:

                swap(5,2,currState)
                frontier.append(currState)

                swap(5,4,currState)
                frontier.append(currState)


                swap(5,8,currState)
                frontier.append(currState)

        elif state[6] == 0:

                swap(6,3,currState)
                frontier.append(currState)


                swap(6,7,currState)
                frontier.append(currState)


        elif state[7] == 0:

                swap(7,4,currState)
                frontier.append(currState)


                swap(7,6,currState)
                frontier.append(currState)

                swap(7,8,currState)
                frontier.append(currState)

        elif state[8] == 0:

                swap(8,5,currState)
                frontier.append(currState)


                swap(8,7,currState)
                frontier.append(currState)

def search(state,frontier):

                addFrontier(state, frontier)
                print frontier



def main():
        createPuzzle()
        addFrontier(startState, frontier)
        search(startState, frontier)


main()