title: Infinite loop and recursion in Python
body: <p>I am working on implementing an iterative deepening depth first search to find solutions for the <a href="http://en.wikipedia.org/wiki/8-puzzle" rel="nofollow">8 puzzle problem</a>. I am not interested in finding the actual search paths themselves, but rather just to time how long it takes for the program to run. (I have not yet implemented the timing function).</p>
  
  <p>However, I am having some issues trying to implement the actual search function (scroll down to see). I pasted all the code I have so far, so if you copy and paste this, you can run it as well. That may be the best way to describe the problems I'm having...I'm just not understanding why I'm getting infinite loops during the recursion, e.g. in the test for puzzle 2 (p2), where the first expansion should yield a solution. I thought it may have something to do with not adding a "Return" in front of one of the lines of code (it's commented below). When I add the return, I can pass the test for puzzle 2, but something more complex like puzzle 3 fails, since it appears that the now the code is only expanding the left most branch...</p>
  
  <p>Been at this for hours, and giving up hope. I would really appreciate another set of eyes on this, and if you could point out my error(s). Thank you!</p>
  
  <pre><code>#Classic 8 puzzle game
  #Data Structure: [0,1,2,3,4,5,6,7,8], which is the goal state. 0 represents the blank
  #We also want to ignore "backward" moves (reversing the previous action)
  
  p1 = [0,1,2,3,4,5,6,7,8]
  p2 = [3,1,2,0,4,5,6,7,8]
  p3 = [3,1,2,4,5,8,6,0,7]
  
  def z(p):   #returns the location of the blank cell, which is represented by 0
      return p.index(0)
  
  def left(p):
      zeroLoc = z(p)
      p[zeroLoc] = p[zeroLoc-1]
      p[zeroLoc-1] = 0
      return p
  
  def up(p):
      zeroLoc = z(p)
      p[zeroLoc] = p[zeroLoc-3]
      p[zeroLoc-3] = 0
      return p
  
  def right(p):
      zeroLoc = z(p)
      p[zeroLoc] = p[zeroLoc+1]
      p[zeroLoc+1] = 0
      return p
  
  def down(p):
      zeroLoc = z(p)
      p[zeroLoc] = p[zeroLoc+3]
      p[zeroLoc+3] = 0
      return p
  
  def expand1(p):   #version 1, which generates all successors at once by copying parent
      x = z(p)
      #p[:] will make a copy of parent puzzle
      s = []  #set s of successors
  
      if x == 0:
          s.append(right(p[:]))
          s.append(down(p[:]))
      elif x == 1:
          s.append(left(p[:]))
          s.append(right(p[:]))
          s.append(down(p[:]))
      elif x == 2:
          s.append(left(p[:]))
          s.append(down(p[:]))
      elif x == 3:
          s.append(up(p[:]))
          s.append(right(p[:]))
          s.append(down(p[:]))
      elif x == 4:
          s.append(left(p[:]))
          s.append(up(p[:]))
          s.append(right(p[:]))
          s.append(down(p[:]))
      elif x == 5:
          s.append(left(p[:]))
          s.append(up(p[:]))
          s.append(down(p[:]))   
      elif x == 6:
          s.append(up(p[:]))
          s.append(right(p[:]))
      elif x == 7:
          s.append(left(p[:]))
          s.append(up(p[:]))
          s.append(right(p[:]))
      else:   #x == 8
          s.append(left(p[:]))
          s.append(up(p[:]))
  
      #returns set of all possible successors
      return s
  
  goal = [0,1,2,3,4,5,6,7,8]
  
  def DFS(root, goal):    #iterative deepening DFS
      limit = 0
      while True:
          result = DLS(root, goal, limit)
          if result == goal:
              return result
          limit = limit + 1
  
  visited = []
  
  def DLS(node, goal, limit):    #limited DFS
      if limit == 0 and node == goal:
          print "hi"
          return node
      elif limit &gt; 0:
          visited.append(node)
          children = [x for x in expand1(node) if x not in visited]
          print "\n limit =", limit, "---",children   #for testing purposes only
          for child in children:
              DLS(child, goal, limit - 1)     #if I add "return" in front of this line, p2 passes the test below, but p3 will fail (only the leftmost branch of the tree is getting expanded...)
      else:
          return "No Solution"
  
  #Below are tests
  
  print "\ninput: ",p1
  print "output: ",DFS(p1, goal)
  
  print "\ninput: ",p2
  print "output: ",DLS(p2, goal, 1)
  #print "output: ",DFS(p2, goal)
  
  print "\ninput: ",p3
  print "output: ",DLS(p3, goal, 2)
  #print "output: ",DFS(p2, goal)
  </code></pre>