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

visited = []

######################################
class Stack:
     def __init__(self):
         self.items = []
         self.children = []

     def isEmpty(self):
         return self.items == []

     def push(self, item):
         self.items.append(item)

     def pop(self):
         return self.items.pop()

     def peek(self):
         return self.items[len(self.items)-1]

     def size(self):
         return len(self.items)
######################################
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 range(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)
	if movement == None:
		children = 0

 	return children



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


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


	while solved != 1:
		#print(depth)

		#for loop that checks all the possible movements and put them in a stack
		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]))
				m.append(move[i])

		#increase depth
		depth = depth + 1

		#print "STACK"
		#print(stack)
		#print "MOVE"
		#print(m)
		#print "PUZZLE"
		#display(puzzle)
		#print(actualMove)
		#checks if the child is the solution
		if stack[len(stack)-1] == goalState:
			puzzle = stack[len(stack)-1]	#moves to the child
			actualMove.append(m.pop())		#mark the movement
			display(puzzle)					#display board state
			display(goalState)				#display goal state
			print(actualMove)				#display move
			print "Puzzle Solved in ", len(actualMove) , " steps"
			solved = 1

		#if child is not the solution
		else:
			puzzle = stack[len(stack)-1]	#puzzle becomes the child
			move = movement(puzzle)[::-1]	#move becomes the movement of the child
			visited.append(stack.pop())		#mark the previous state
			actualMove.append(m.pop())		#mark the movement
			#print "VISITED"
			#print(visited)
			#print "Movement"
			#print(actualMove)

		#maximum depth reached
		if depth == 30:
			actualMove.pop()
			while stack is not None:
				if len(stack) != 0:
					actualMove.pop()			#remove the last movement
					if len(m) == 1:
						puzzle = stack.pop() 		#remove the last movement
						visited.append(puzzle)		#current location is added to visited
					else:
						m.pop()
						puzzle = stack.pop() 		#remove the last movement
						visited.append(puzzle)		#current location is added to visited
					#print "DEPTH PUZZLE"
					#display(puzzle)
					if puzzle == goalState:
						actualMove.append(m.pop())	#mark the movement
						print "SOLVED"
						display(puzzle)
						display(goalState)
						print(actualMove)
						return
				else:
					print "Solution too deep"
					return

def make_stack(current_state):
	stack = Stack()
	child = []
	puzzle = current_state
	move = movement(puzzle)[::-1]
	stack.push(current_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:
				child.append(possible_movements(puzzle, move[i]))
				child.pop()
			else:
				child.append(possible_movements(puzzle, move[i]))

	stack.children = child
	return stack


def dfs_trial(current_state):
	puzzle = current_state
	temp = make_stack(puzzle)
	stack = []
	stack.append(temp.peek())
	depth = 0

	puzzle = stack[len(stack)-1]
	visited.append(puzzle)
	display(puzzle)

	while initialState != goalState:
		#print stack[len(stack)-1], " is getting Popped"
		stack.pop()
		for i in xrange(len(temp.children)):
			stack.append(temp.children[i])

		puzzle = stack[len(stack)-1]
		visited.append(puzzle)

		#print "STACK"
		#print(stack)

		temp = make_stack(puzzle)

		#print "Current Node Stack"
		#print(temp.peek())

		#print "Children Stack"
		#print(temp.children)

		depth = depth + 1
		if puzzle == goalState:
			print "Puzzle Solved"
			print "Solved in " ,depth, "steps"
			display(puzzle)
			display(goalState)
			return

		if depth == 1000:
			while stack is not None:
				depth = depth - 1
				stack.pop()
				puzzle = stack[len(stack)-1]
				visited.append(puzzle)
				if puzzle == goalState:
					print "Puzzle Solved"
					print "Solved in " ,depth, "steps"
					display(puzzle)
					display(goalState)
					return




############################################
#display(initialState)
#dfs(initialState)
dfs_trial(initialState)