Posted By

juanro on 03/21/16


Tagged

cco360


Versions (?)

8 Slide Puzzle


 / Published in: Python
 

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

  1. from copy import deepcopy
  2. # return cero position [position,lista]
  3. # done no errors found.
  4. def getin(position, mattwo):
  5. listpos = -1
  6. indexone = -1
  7. # - - - - - -
  8. for i in mattwo:
  9. listpos += 1
  10. for o in i:
  11. if o == position:
  12. indexone = i.index(o)
  13. return listpos, indexone
  14. # return a list with character location
  15. # done no errors found
  16. def retpostion(character, packone):
  17. listone = []
  18. for i in getin(character,packone):
  19. if i != None:
  20. listone.append(i)
  21. return listone
  22. # returns the states/movements in list[] of lists.
  23. # done no errors found.
  24. def statesmatrix(reposition, listsone):
  25. cero, placement = getin('0',listsone), getin(reposition,listsone)
  26. remod = deepcopy(listsone)
  27. remod[placement[0]][placement[1]] = '0'
  28. remod[cero[0]][cero[1]] = reposition
  29. return remod
  30. # recursive depth
  31. # done no errors
  32. def depthrec(start, goal, path=[]):
  33. path = path + [start]
  34. position = getin('0',start)
  35. for node in state(str(position[0]),str(position[1]),start):
  36. node = statesmatrix(node,start)
  37. if not node in path:
  38. path = depthrec(node, goal, path)
  39. return path
  40. # return a list with all the posible movements.
  41. # done no errors found.
  42. def state(vertice, position, mat):
  43. posiblemoves = []
  44. # - - - - - -
  45. if (vertice == '0' and position == '2'):
  46. posiblemoves.append(mat[0][1])
  47. posiblemoves.append(mat[1][2])
  48. # - - - - - -
  49. elif (vertice == '0' and position == '1'):
  50. posiblemoves.append(mat[0][0])
  51. posiblemoves.append(mat[1][1])
  52. posiblemoves.append(mat[0][2])
  53. elif (vertice == '0' and position == '0'):
  54. posiblemoves.append(mat[0][1])
  55. posiblemoves.append(mat[1][0])
  56. # - - - - - -
  57. elif (vertice == '1' and position == '0'):
  58. posiblemoves.append(mat[0][0])
  59. posiblemoves.append(mat[1][1])
  60. posiblemoves.append(mat[2][0])
  61. elif (vertice == '1' and position == '1'):
  62. posiblemoves.append(mat[0][1])
  63. posiblemoves.append(mat[1][0])
  64. posiblemoves.append(mat[1][2])
  65. posiblemoves.append(mat[2][1])
  66. elif (vertice == '1' and position == '2'):
  67. posiblemoves.append(mat[0][2])
  68. posiblemoves.append(mat[1][1])
  69. posiblemoves.append(mat[2][2])
  70. # - - - - - -
  71. elif (vertice == '2' and position == '0'):
  72. posiblemoves.append(mat[1][0])
  73. posiblemoves.append(mat[2][1])
  74. elif (vertice == '2' and position == '1'):
  75. posiblemoves.append(mat[2][0])
  76. posiblemoves.append(mat[1][1])
  77. posiblemoves.append(mat[2][2])
  78. elif (vertice == '2' and position == '2'):
  79. posiblemoves.append(mat[1][2])
  80. posiblemoves.append(mat[2][1])
  81. # - - - - - -
  82. return posiblemoves
  83. # - - - - - -
  84.  
  85. def depth(start, goal, counter, path=[]):
  86. path = path + [start]
  87. position = getin('0',start)
  88. # - - - - - -
  89. counter += 1
  90. for node in state(str(position[0]),str(position[1]),start):
  91. childs = statesmatrix(node,start)
  92. if goal in path:
  93. print "reached", counter
  94. break
  95. if not childs in path:
  96. path = depth(childs, goal, counter, path)
  97. return path
  98.  
  99. start1 = [['5','4','0'],
  100. ['6','1','8'],
  101. ['7','3','2']]
  102. # - - - - - -
  103. goalmat = [['1','2','3'],
  104. ['8','0','4'],
  105. ['7','6','5']]
  106.  
  107.  
  108. start = [['0','1','3'],
  109. ['8','2','4'],
  110. ['7','6','5']]
  111.  
  112.  
  113. originalstart = [['5','4','0'],
  114. ['6','1','8'],
  115. ['7','3','2']]
  116.  
  117.  
  118. originalgoal = [['1','2','3'],
  119. ['8','0','4'],
  120. ['7','6','5']]
  121. # - - - - - -
  122. # depth recursive
  123. # max recursion exceded
  124. # - - - - - -
  125. # depth
  126. # done but never find the goal
  127. # - - - - - -
  128.  
  129. path, counter = [], 0
  130. stack = [originalstart]
  131. while stack:
  132. stackpop = stack.pop(0)
  133. position = getin('0',stackpop)
  134. if stackpop not in path:
  135. path = path + [stackpop]
  136. for posmove in state(str(position[0]),str(position[1]),stackpop):
  137. childs = statesmatrix(posmove, stackpop)
  138. stack = [childs] + stack
  139. counter += 1
  140. if (goalmat in path or goalmat in stack):
  141. print "reached", counter
  142. break
  143.  
  144. print "done"
  145.  
  146.  
  147. #depth(start,goalmat,0)
  148.  
  149. #recursive_dfs(start,start1,0)
  150.  
  151.  
  152.  
  153. #print "paths: ", paths

Report this snippet  

You need to login to post a comment.