initialState = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]
goalState = [2,3,4,0,1,6,7,8,5,10,11,12,9,13,14,15]

######################################
class Queue:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def enqueue(self, obj):
        self.in_stack.append(obj)

    def pop(self):
        if not self.out_stack:
            self.in_stack.reverse()
            self.out_stack = self.in_stack
            self.in_stack = []
        return self.out_stack.pop()

    def printQ(self):
    	display(self.in_stack[0])

    def first(self):
    	return self.in_stack[0]
'''
    def printAll(self):
    	for i in xrange(len(self.in_stack))
    		display(self.in_stack[i])
    		'''
######################################
class Node(object):
    def __init__(self, data=None, next_node=None):
        self.data = data
        self.next_node = next_node

    def get_data(self):
        return self.data

    def get_next(self):
        return self.next_node

    def set_next(self, new_next):
        self.next_node = new_next

######################################
def display(s):
        i = s
        print
        print "-------------"
        print "|",i[0],"|",i[1],"|",i[2],"|",i[3],"|"
        print "-------------"
        print "|",i[4],"|",i[5],"|",i[6],"|",i[7],"|"
        print "-------------"
        print "|",i[8],"|",i[9],"|",i[10],"|",i[11],"| "
        print "-------------"
        print "|",i[12],"|",i[13],"|",i[14],"|",i[15],"| "
        print "-------------"
        return
######################################
def move_down(current_state):
        index = 0
	for i in xrange(len(current_state)):
		if current_state[i] == 0:
			index = i
        newState = current_state

        if index not in [12, 13, 14, 15]:
                temp = newState[index + 4]
                newState[index + 4] = newState[index]
                newState[index] = temp
                return newState

        else:
                return None

######################################
def move_up(current_state):
        index = 0
	for i in xrange(len(current_state)):
		if current_state[i] == 0:
			index = i
        newState = current_state

        if index not in [0, 1, 2, 3]:
                temp = newState[index - 4]
                newState[index - 4] = newState[index]
                newState[index] = temp
                return newState

        else:
                return None

def check_up(current_state):
    index = current_state.index(0)

    if index not in [0,1,2,3]:
        return 1
    else:
        return 0

######################################
def move_left(current_state):
        index = 0
	for i in xrange(len(current_state)):
		if current_state[i] == 0:
			index = i

        newState = current_state

        if index not in [0, 4, 8, 12]:
                temp = newState[index - 1]
                newState[index - 1] = newState[index]
                newState[index] = temp
                return newState

        else:
                return None

######################################
def move_right(current_state):
        index = 0
	for i in xrange(len(current_state)):
		if current_state[i] == 0:
			index = i
        newState = current_state

        if index not in [3, 7, 11, 15]:
                temp = newState[index + 1]
                newState[index + 1] = newState[index]
                newState[index] = temp
                return newState

        else:
                return None

######################################
def new_node (current_state, parent, movement):
        return Node(current_state, movement)

######################################
def movement(s):
    movement = []
    index = 0
    for i in xrange(len(s)):
        if s[i] == 0:
            index = i

    if index not in [0, 4, 8, 12]:
        movement.append("Left")
    if index not in [0,1,2,3]:
        movement.append("Up")
    if index not in [3, 7, 11, 15]:
        movement.append("Right")
    if index not in [12, 13, 14, 15]:
        movement.append("Down")


    return movement
######################################

def possible_movements(s, movement):
    children = 0
    temp = []
    size = len(s)
    for i in xrange(size):
        temp.append(s[i])

    if movement == "Left":
        children = move_left(temp)
    if movement == "Up":
        children = move_up(temp)
    if movement == "Right":
        children = move_right(temp)
    if movement == "Down":
        children = move_down(temp)


    return children



############################################
def dfs(current_state, goal_state):
    stack = []
    visited = []
    m = []
    puzzle = current_state
    move = movement(puzzle)[::-1]
    size = 0
    depth = 0
    solved = 0

    visited.append(puzzle)
    if puzzle == goal_state:
        print "Initial State and Goal State are the Same"
        solved = 1


    while solved != 1:

        for i in xrange(len(move)):
            exist = 0
            for x in xrange(len(visited)):
                if possible_movements(puzzle, move[i]) == visited[x]:
                    exist = 1
            if exist == 1:
                stack.append(possible_movements(puzzle, move[i]))
                stack.pop()
            else:
                stack.append(possible_movements(puzzle, move[i]))



        depth = depth + 1

        size = len(stack)
        #print "STACK"
        #print(stack)
        #print "MOVE"
        #print(m)
        if stack[size-1] == goalState:
            puzzle = stack[size-1]
            print "Puzzle Solved"
            display(puzzle)
            display(goalState)
            solved = 1
        else:
            puzzle = stack[size-1]
            move = movement(puzzle)[::-1]
            visited.append(stack.pop())
            #print "VISITED"
            #print(visited)
        if depth > 1000:
            print "Solution is too far"
            solved = 1

############################################

def bfs(current_state, goal_state):
	q = Queue()
	q.enqueue(current_state)
	puzzle = current_state
	move = movement(puzzle)[::-1]
	visited = []

	while q.first() != goal_state:

		for i in xrange(len(move)):
			exist = 0
			for x in xrange(len(visited)):
				if possible_movements(puzzle, move[i]) == visited[x]:
                    exist = 1
			if exist == 1:
				q.enqueue(possible_movements(puzzle, move[i]))
				q.pop()
			else:
				q.enqueue(possible_movements(puzzle, move[i]))


############################################
#display(initialState)
#dfs(initialState, goalState)
l= Queue()
l.enqueue(initialState)
l.printQ()
#l.printAll()