## Posted By

juanro on 03/21/16

# 8 Slide Puzzle

/ Published in: Python

Uses both iterative and recursive depth searches to try and solve an 8 slide puzzle game.

`from copy import deepcopy# return cero position [position,lista]# done no errors found.def getin(position, mattwo):	listpos = -1	indexone = -1	# - - - - - -	for i in mattwo:		listpos += 1		for o in i:			if o == position:				indexone = i.index(o)				return listpos, indexone# return a list with character location# done no errors founddef retpostion(character, packone):	listone = []	for i in getin(character,packone):		if i != None:			listone.append(i)	return listone# returns the states/movements in list[] of lists.# done no errors found.def statesmatrix(reposition, listsone):	cero, placement = getin('0',listsone), getin(reposition,listsone)	remod = deepcopy(listsone)	remod[placement[0]][placement[1]] = '0'	remod[cero[0]][cero[1]] = reposition	return remod# recursive depth# done no errorsdef depthrec(start, goal, path=[]):	path = path + [start]	position = getin('0',start)	for node in state(str(position[0]),str(position[1]),start):		node = statesmatrix(node,start)		if not node in path:			path = depthrec(node, goal, path)  	return path# return a list with all the posible movements.# done no errors found.def state(vertice, position, mat):	posiblemoves = []	# - - - - - -	if (vertice == '0' and position == '2'):		posiblemoves.append(mat[0][1])		posiblemoves.append(mat[1][2])	# - - - - - -	elif (vertice == '0' and position == '1'):		posiblemoves.append(mat[0][0])		posiblemoves.append(mat[1][1])		posiblemoves.append(mat[0][2])	elif (vertice == '0' and position == '0'):		posiblemoves.append(mat[0][1])		posiblemoves.append(mat[1][0])	# - - - - - -	elif (vertice == '1' and position == '0'):		posiblemoves.append(mat[0][0])		posiblemoves.append(mat[1][1])		posiblemoves.append(mat[2][0])	elif (vertice == '1' and position == '1'):		posiblemoves.append(mat[0][1])		posiblemoves.append(mat[1][0])		posiblemoves.append(mat[1][2])		posiblemoves.append(mat[2][1])	elif (vertice == '1' and position == '2'):		posiblemoves.append(mat[0][2])		posiblemoves.append(mat[1][1])		posiblemoves.append(mat[2][2])	# - - - - - -	elif (vertice == '2' and position == '0'):		posiblemoves.append(mat[1][0])		posiblemoves.append(mat[2][1])	elif (vertice == '2' and position == '1'):		posiblemoves.append(mat[2][0])		posiblemoves.append(mat[1][1])		posiblemoves.append(mat[2][2])	elif (vertice == '2' and position == '2'):		posiblemoves.append(mat[1][2])		posiblemoves.append(mat[2][1])    # - - - - - -	return posiblemoves	# - - - - - - def depth(start, goal, counter, path=[]):	path = path + [start]	position = getin('0',start)	# - - - - - -	counter += 1	for node in state(str(position[0]),str(position[1]),start):		childs = statesmatrix(node,start)		if goal in path:			print "reached", counter			break		if not childs in path:			path = depth(childs, goal, counter, path)  	return path start1 = [['5','4','0'],		 ['6','1','8'],		 ['7','3','2']]# - - - - - -goalmat = [['1','2','3'],		   ['8','0','4'],		   ['7','6','5']]  start = [['0','1','3'],		   ['8','2','4'],		   ['7','6','5']]  originalstart = [['5','4','0'],		 ['6','1','8'],		 ['7','3','2']]  originalgoal = [['1','2','3'],		   ['8','0','4'],		   ['7','6','5']]# - - - - - -# depth recursive# max recursion exceded# - - - - - -# depth# done but never find the goal# - - - - - - path, counter = [], 0stack = [originalstart]while stack:	stackpop = stack.pop(0)	position = getin('0',stackpop)	if stackpop not in path:		path = path + [stackpop]		for posmove in state(str(position[0]),str(position[1]),stackpop):			childs = statesmatrix(posmove, stackpop)			stack = [childs] + stack	counter += 1	if (goalmat in path or goalmat in stack):		print "reached", counter		break print "done"  #depth(start,goalmat,0) #recursive_dfs(start,start1,0)   #print "paths: ", paths`